### Subsets

Let’s suppose that set \(S\) contains a full deck of playing cards. Therefore, \(|S|=52\). We can split the cards into four suits: \(♠,♣,♥,♦\). Let’s make a set \(T\) that contains only the clubs suit from that deck:

\[T=\{A♣,2♣,3♣,4♣,5♣,6♣,7♣,8♣,9♣,10♣,J♣,Q♣,K♣\}\]

The number of elements inside set \(T\) is \(|T|=13\). We call set \(T\) *a subset* of the set \(S\). Every element inside of set \(T\) is *also* an element inside of set \(S\). It’s important to note that set \(S\) still contains *all* 52 cards. Set \(T\) is simply showing you what is inside set \(S\) – it hasn’t removed those cards. Set \(T\) could contain any of the 52 playing cards and it would be a valid subset, for example:

\[T=\{4♦,J♣,8♠,4♠,A♦,Q♥\}\]

The combinatorical way of writing that \(T\) is a subset of \(S\):

\[T \subseteq S\]

We can also say that \(S\) is the* super-set* of \(T\):

\[S \supseteq T\]

A subset is a set in its own right and obeys the same rules as for sets. A subset can also contain every element that is in its super-set. Therefore, \(T=S\) iff (if and *only* if) \(T \subseteq S\) *and* \(S \subseteq T\).

### The Power Set

Here’s a set of two playing cards:

\[S=\{K♠,Q♦\}\]

Remember that sets are unordered, so \(\{K♠,Q♦\}\) is the same as \(\{Q♦,K♠\}\). How many subsets can we make from set \(S\)? A* direct enumeration* gives us:

\[\{K♠\},\{Q♦\},\{K♠,Q♦\}\]

There appears to be three, but this answer is only partly true.

We can count all of the subsets by the use of the *power set rule*. It looks like this:

\[\wp(S)\]

Which represents all of the possible subsets of the set \(S\). We want to *count the size* (all of the groups of elements) of the power set which will count all of the subsets, thus:

\[|\wp(S)|=2^{|S|}\]

### The Empty Set

I said that the number of subsets for our card set is three and that’s partly true. To see why, we need to calculate the size of the power-set. First, \(|S|=2\) therefore:

\[|\wp(S)|=2^2=4\]

(Remember, in mathematics a *superscript* n \(x^n\) means to *raise x to the power of n*. Or, multiply x by itself n number of times. In this case \(x=2,n=2\), therefore \(x*x=2*2=4\)).

According to the power-set rule we should have counted *four* subsets and not three.

Where’s the missing subset?

The answer lies with something called the *empty set*. As the name obviously implies, it’s a set with nothing in it:

\[S=\{\}\]

Hold on. How can I count nothing? An *easy* way to think of it is as something that didn’t happen but possibly could have happened.

We might decide to not place a card on the table, for example. A lottery ticket is easier to think about. Suppose I don’t match any numbers on my ticket (happens all too often!)? It’s still a lottery ticket. Does it not count?

I can count all of the tickets that match one, two, three etc. numbers. What about all of the tickets that match none?

The power-set of the card set \(S=\{K♠,Q♦\}\) looks like this:

\[\wp(S)=\{\emptyset,\{K♠\},\{Q♦\},\{K♠,Q♦\}\}\]

Where \(\emptyset=\{\}\). The size of the empty set (its cardinality) is zero, \(|\emptyset|=0\). But it does count as one subset. So the number of card subsets is now four.

If we take the cardinality of the power-set given the empty-set, we get this:

\[|\wp(\emptyset)|=2^{|\emptyset|}=1\]

Which means it is a subset of itself. And just to make matters more confusing, *all* sets have an empty subset and every set is a subset of itself!

To appreciate the potential size of all the subsets from a given set, consider four cards:

\[S=\{J♠,Q♣,K♥,A♦\}\]

According to the power-set rule there should be \(2^{|S|}=2^4=16\) subsets.

Let’s directly enumerate them by placing all of the card subsets on a virtual table (remember, the order does not count):

First, we can put down just one card at a time: \(\{J♠\},\{Q♣\},\{K♥\},\{A♦\}\). That’s four subsets.

Second, we can put them down in pairs: \(\{J♠,Q♣\},\{J♠,K♥\},\{J♠,A♦\},\{Q♣,K♥\},\{Q♣,A♦\},\{K♥,A♦\}\). That’s six subsets.

Third, we can put them down in triplets: \(\{J♠,Q♣,K♥\},\{J♠,Q♣,A♦\},\{J♠,K♥,A♦\},\{Q♣,K♥,A♦\}\). That’s four subsets.

Forth, we can put all of our cards on the table: \(\{J♠,Q♣,K♥,A♦\}\). That’s one subset.

Lastly, we can choose not to put any cards on the table, the empty-set \(\emptyset\). That’s one subset. This gives us a total of sixteen subsets, \(4+6+4+1+1=16\). We’ll see later that these numbers form a part of something called* Pascal’s triangle*.

As a challenge, try to directly enumerate (count) all 52 playing cards’ subsets. The power-set rule states that you’d need quite a few lifetimes to do so:

\[2^{52}=4,503,599,627,000,000\]

In English – Four quadrillion, five-hundred-and-three-trillion, five-hundred-and-ninety-nine-billion and six-hundred-and-twenty-seven-million different subsets.

Happy counting.

© Doc Mike Finnley 2019