Discrete Mathematics for Computer Science

Countable and Uncountable Sets 271

(c) If real numbers x and y have the same decimal expansion, they are equal.

(d) If a real number has two decimal expansions, then one of them terminates in an infinite

string of O's and the other in an infinite string of 9's.

Of course, not all finite sets have the same cardinality, but by now, the reader is surely

wondering how two infinite sets could have different cardinalities. We are about to prove

that the cardinality of the open interval (0, 1) of real numbers is strictly greater than the

cardinality of N or, in other words, that (0, 1) is uncountable. We will do this follow-

ing Template 1.10, based on the fact that if (0, 1) were countable, we would be able to

list all its elements in a (countable) sequence without omitting any or duplicating any.

Let us assume that some function F defined on N lists all the decimal expansions of the

numbers in (0, 1). For the sake of developing the example to illustrate the idea of the

proof, let us suppose the function F, with F(0) = 0.254257..., F(1) = 0.751999...,

F(2) = 0.485259.•., F(3) = 0.254157.•., and continuing until our list contained every

element of (0, 1).

We need to show that such a list cannot contain all real numbers. We first display our

countably infinite sequence in a table whose diagonal elements-the first decimal digit of

F(0), the second decimal digit of F(l). the nth decimal digit of F(n - 1)-appear in

boxes:

F(0) 0.04157 ...

F(l) = 0.75]1999...

F(2) = 0.48]259...

F(3) = 0.000[J08...

We now show how to construct a number d = O.dld 2 d 3 ... that is not on the above

countably infinite list. Since we want to avoid having d = F(0), we decide to make the first

digit of d different from the first digit of F(0)-that is, we choose dl # 2. To be definite,

let us take dj = 5. Now, the second digit of F(l) is 5, so to avoid having d = F(l), we

take the second digit of d to be, say, 4. We continue in this fashion, taking care that dn-
the nth digit of d-is always different from the nth digit of F(n - 1). To be systematic,
we always choose d,, = 5 unless the nth digit of F(n - 1) is 5, in which case we choose
dn = 4. (So, in our example, we have d = 0.5445--..)
Thus, we have created a number d = 0.djd 2 d 3 ... E (0, 1), the decimal expansion of
which is different from all the decimal expansions on this countably infinite list. Further-
more, since we avoided using O's and 9's in d, we know by Theorem 8(d) that even when
some real number has a second decimal expansion, that decimal expansion cannot be d.
So, we have achieved a contradiction: We have created a real number d that could not pos-

sibly be on the countable list F(0), F(l), F(2) ... , which supposedly included all real

numbers. This example shows that the function chosen, F, did not work. The proof that
the reals are uncountable must show that no such function exists.
The proof of the next theorem formalizes this intuitive argument using an arbitrary
function. The argument is called Cantor's second diagonal argument.

Theorem 9. (Cantor) R is uncountable.