1.3 The Number of Subsets 11contains the third (and in this case last) question you have to answer to
determine the subset: Iscan element ofS? Giving an answer and following
the appropriate arrow we finally get to a node that does not represent a
question, but contains a listing of the elements ofS.
Thus to select a subset corresponds to walking down this diagram from
the top to the bottom. There are just as many subsets of our set as there
are nodes on the last level. Since the number of nodes doubles from level
to level as we go down, the last level contains 2^3 = 8 nodes (and if we had
ann-element set, it would contain 2nnodes).
Remark.A picture like this is called atree. (This is not a formal definition;
that will follow later.) If you want to know why the tree is growing upside
down, ask the computer scientists who introduced this convention. (The
conventional wisdom is that they never went out of the room, and so they
never saw a real tree.)
We can give another proof of Theorem 1.3.1. Again, the answer will be
made clear by asking a question about subsets. But now we don’t want to
select a subset; what we want is toenumeratesubsets, which means that
we want to label them with numbers 0, 1 , 2 ,...so that we can speak, say,
about subset number 23 of the set. In other words, we want to arrange the
subsets of the set in a list and then speak about the 23rd subset on the list.
(We actually want to call the first subset of the list number 0, the second
subset on the list number 1 etc. This is a little strange, but this time it is
the logicians who are to blame. In fact, you will find this quite natural and
handy after a while.)
There are many ways to order the subsets of a set to form a list. A fairly
natural thing to do is to start with∅, then list all subsets with 1 element,
then list all subsets with 2 elements, etc. This is the way the list (1.5) is
put together.
Another possibility is to order the subsets as in a phone book. This
method will be more transparent if we write the subsets without braces
and commas. For the subsets of{a, b, c}, we get the list
∅, a, ab, abc, ac, b, bc, c.These are indeed useful and natural ways of listing all subsets. They have
one shortcoming, though. Imagine the list of the subsets of 10 elements,
and ask yourself to name the 233rd subset on the list, without actually
writing down the whole list. This would be difficult! Is there a way to make
it easier?
Let us start with another way of denoting subsets (anotherencodingin
the mathematical jargon). We illustrate it on the subsets of{a, b, c}.We
look at the elements one by one, and write down a 1 if the element occurs in
the subset and a 0 if it does not. Thus for the subset{a, c}, we write down
101, sinceais in the subset,bis not, andcis in it again. This way every