238
Sets, Combinatorics, and Probability
ExamplE 23
We will show that the set of all the real numbers between 0 and 1 is uncountable.
We will write such numbers in decimal form; thus any member of the set can
be written as
0.d 1 d 2 d 3 …
Now let us assume that our set is countable. Therefore some enumeration of the
set exists. A number such as 0.24999999 … can be written in alternative form as
0.2500000 … (see Exercise 102 for an explanation of why these are alternative
representations of the same number). To avoid writing the same element twice in
our enumeration, we will choose (arbitrarily) to always use the former representation and not the latter. We can depict an enumeration of the set as follows, where
d ij is the jth decimal digit in the ith number in the enumeration:
0.d 11 d 12 d 13
0.d 21 d 22 d 23
0.d 31 d 32 d 33
We now construct a real number p = 0.p 1 p 2 p 3 … as follows: p i is always chosen
to be 5 if d ii ∙ 5 and 6 if d ii = 5. Thus p is a real number between 0 and 1. For
instance, if the enumeration begins with
0.342134 . . .
0.257001 . . .
0.546122 . . .
0.716525 . . .
then d 11 = 3, d 22 = 5, d 33 = 6, and d 44 = 5, so p 1 = 5, p 2 = 6, p 3 = 5, and p 4 = 6.
Thus p begins with 0.5656 … .
If we compare p with the enumeration of the set, p differs from the first number
at the first decimal digit, from the second number at the second decimal digit, from
the third number at the third decimal digit, and so on.
0. 3 4 2 1 3 4 . . .
0. 2 5 7 0 0 1 . . .
0. 5 4 6 1 2 2 . . .
0. 7 1 6 5 2 5 . . .
Therefore p does not agree with any of the representations in the enumeration. Furthermore, because p contains no 0s to the right of the decimal, it is not the alternative representation of any of the numbers in the enumeration. Therefore p is a real
number between 0 and 1 different from any other number in the enumeration, yet
the enumeration was supposed to include all members of the set. Here, then, is the
contradiction, and the set of all real numbers between 0 and 1 is indeed uncountable. (You can see why this proof is called a “diagonalization method.”)
Sets, Combinatorics, and Probability
ExamplE 23
We will show that the set of all the real numbers between 0 and 1 is uncountable.
We will write such numbers in decimal form; thus any member of the set can
be written as
0.d 1 d 2 d 3 …
Now let us assume that our set is countable. Therefore some enumeration of the
set exists. A number such as 0.24999999 … can be written in alternative form as
0.2500000 … (see Exercise 102 for an explanation of why these are alternative
representations of the same number). To avoid writing the same element twice in
our enumeration, we will choose (arbitrarily) to always use the former representation and not the latter. We can depict an enumeration of the set as follows, where
d ij is the jth decimal digit in the ith number in the enumeration:
0.d 11 d 12 d 13
0.d 21 d 22 d 23
0.d 31 d 32 d 33
We now construct a real number p = 0.p 1 p 2 p 3 … as follows: p i is always chosen
to be 5 if d ii ∙ 5 and 6 if d ii = 5. Thus p is a real number between 0 and 1. For
instance, if the enumeration begins with
0.342134 . . .
0.257001 . . .
0.546122 . . .
0.716525 . . .
then d 11 = 3, d 22 = 5, d 33 = 6, and d 44 = 5, so p 1 = 5, p 2 = 6, p 3 = 5, and p 4 = 6.
Thus p begins with 0.5656 … .
If we compare p with the enumeration of the set, p differs from the first number
at the first decimal digit, from the second number at the second decimal digit, from
the third number at the third decimal digit, and so on.
0. 3 4 2 1 3 4 . . .
0. 2 5 7 0 0 1 . . .
0. 5 4 6 1 2 2 . . .
0. 7 1 6 5 2 5 . . .
Therefore p does not agree with any of the representations in the enumeration. Furthermore, because p contains no 0s to the right of the decimal, it is not the alternative representation of any of the numbers in the enumeration. Therefore p is a real
number between 0 and 1 different from any other number in the enumeration, yet
the enumeration was supposed to include all members of the set. Here, then, is the
contradiction, and the set of all real numbers between 0 and 1 is indeed uncountable. (You can see why this proof is called a “diagonalization method.”)