12 1. Let’s Count!
subset is “encoded” by a string of length 3, consisting of 0’s and 1’s. If we
specify any such string, we can easily read off the subset it corresponds to.
For example, the string 010 corresponds to the subset{b}, since the first
0 tells us thatais not in the subset, the 1 that follows tells us thatbis in
there, and the last 0 tells us thatcis not there.
Now, such strings consisting of 0’s and 1’s remind us of thebinary rep-
resentationof integers (in other words, representations in base 2). Let us
recall the binary form of nonnegative integers up to 10:
0=0 2
1=1 2
2=10 2
3=2+1=11 2
4 = 100 2
5=4+1=101 2
6=4+2=110 2
7=4+2+1=111 2
8 = 1000 2
9 = 8 + 1 = 1001 2
10 = 8 + 2 = 1010 2(We put the subscript 2 there to remind ourselves that we are working in
base 2, not 10.)
Now, the binary forms of integers 0, 1 ,...,7 look almost like the “codes”
of subsets; the difference is that the binary form of an integer (except for
0) always starts with a 1, and the first 4 of these integers have binary
forms shorter than 3, while all codes of subsets of a 3-element set consist
of exactly 3 digits. We can make this difference disappear if we append 0’s
to the binary forms at their beginning, to make them all have the same
length. This way we get the following correspondence:
0 ⇔ 02 ⇔ 000 ⇔∅
1 ⇔ 12 ⇔ 001 ⇔{c}
2 ⇔ 102 ⇔ 010 ⇔{b}
3 ⇔ 112 ⇔ 011 ⇔{b, c}
4 ⇔ 1002 ⇔ 100 ⇔{a}
5 ⇔ 1012 ⇔ 101 ⇔{a, c}
6 ⇔ 1102 ⇔ 110 ⇔{a, b}
7 ⇔ 1112 ⇔ 111 ⇔{a, b, c}So we see that the subsets of{a, b, c}correspond to the numbers 0, 1 ,...,7.
What happens if we consider, more generally, subsets of a set withn
elements? We can argue just as we did above, to get that the subsets of