1.3 The Number of Subsets 13ann-element set correspond to integers, starting with 0 and ending with
the largest integer that hasndigits in its binary representation (digits in
the binary representation are usually calledbits). Now, the smallest number
withn+1 bits is 2n, so the subsets correspond to numbers 0, 1 , 2 ,..., 2 n−1.
It is clear that the number of these numbers in 2n, and hence the number
of subsets is 2n.
Now we can answer our question about the 233rd subset of a 10-element
set. We have to convert 233 to binary notation. Since 233 is odd, its last
binary digit (bit) will be 1. Let us cut off this last bit. This is the same as
subtracting 1 from 233 and then dividing it by 2: We get (233−1)/2 = 116.
This number is even, so its last bit will be 0. Let us cut this off again; we
get (116−0)/2 = 58. Again, the last bit is 0, and cutting it off we get
(58−0)/2 = 29. This is odd, so its last bit is 1, and cutting it off we get
(29−1)/2 = 14. Cutting off a 0, we get (14−0)/2 = 7; cutting off a 1, we
get (7−1)/2 = 3; cutting off a 1, we get (3−1)/2 = 1; cutting off a 1,
we get 0. So the binary form of 233 is 11101001, which corresponds to the
code 0011101001.
It follows that ifa 1 ,...,a 10 are the elements of our set, then the 233rd
subset of a 10-element set consists of the elements{a 3 ,a 4 ,a 5 ,a 7 ,a 10 }.
Comments.We have given two proofs of Theorem 1.3.1. You may wonder
why we needed two proofs. Certainly not because a single proof would not
have given enough confidence in the truth of the statement! Unlike in a legal
procedure, a mathematical proof either gives absolute certainty or else it
is useless. No matter how many incomplete proofs we give, they don’t add
up to a single complete proof.
For that matter, we could ask you to take our word for it, and not give
any proof. Later, in some cases this will be necessary, when we will state
theorems whose proofs are too long or too involved to be included in this
introductory book.
So why did we bother to give any proof, let alone two proofs of the same
statement? The answer is that every proof reveals much more than just the
bare fact stated in the theorem, and this revelation may be more valuable
than the theorem itself. For example, the first proof given above introduced
the idea of breaking down the selection of a subset into independent deci-
sions and the representation of this idea by a “decision tree”; we will use
this idea repeatedly.
The second proof introduced the idea of enumerating these subsets (la-
beling them with integers 0, 1 , 2 ,...). We also saw an important method of
counting: We established a correspondence between the objects we wanted
to count (the subsets) and some other kinds of objects that we can count
easily (the numbers 0, 1 ,..., 2 n−1). In this correspondence:
— for every subset, we had exactly one corresponding number, and
— for every number, we had exactly one corresponding subset.