Mr. Turing’s amazing machines - The Computing Universe: A Journey through a Revolution - page 109

a one-to-one correspondence in Cantor's theory of infinities establishes that in
a technical sense the number of objects in the top row is the same as the num-
ber of objects in the bottom row. Thus the number of integers is the same as
the number of natural numbers, although both are infinite. Sets that can be
put into one-to-one correspondence with the natural numbers are said to be
“countable.” Similarly, we can arrange for all the rational numbers to be in a
one-to-one correspondence with the natural numbers so they, too, are count-
ably infinite. But what about the real numbers? Here the situation is very dif-
ferent and Cantor proved this using his “diagonal slash” method that was later
used by both Gödel and Turing. Using this technique Cantor was able to show
that the number of real numbers must be greater than the number of natural
numbers and is therefore not countable.
Let us see how the technique works. We begin by assuming the opposite -
namely that we can pair off the real numbers with the natural numbers in
some way. We make a list of all the real numbers we can think of and associate
each decimal number with a natural number as follows:

Natural Real

0 0. 1 24 . . .

1 0.0 1 5 . . .

2 0.53 6 92 . . .

3 0.800 3 444 . . .

4 0.3341 0 5011 . . .

5 0.34256 7 8 . . .

The exact assignment of real numbers to the natural numbers is arbitrary:
all we need to do is to assign one real number per natural number so that all the
real numbers are accounted for. But this cannot be so! To see why, Cantor showed
how to find another real number that cannot be already on our list. In the pre-
ceding list, we underline the first digit of the first number, the second digit of the
second, the third of the third, and so on. This gives us the sequence:

1, 1, 6, 3, 0, 7, . . .

The diagonal slash procedure is to construct a new real number from this
sequence that differs from the digits of this number in each corresponding
place. We make this new number by ensuring that the nth digit of this new
number differs from the nth digit in this sequence. For example we can define
a new real number by adding one to each of the underlined digits (with the rule
that 9 + 1 = 0) to get:

0.227418 . . .

What have we achieved? By construction, this number differs from the first
number in the first decimal place, from the second number in the second
place, from the third number in the third place, and so on. By construction
this number is different from any of the real numbers on our original list.
Hence we have found a real number that cannot be on our list. This contra-
diction establishes the fact that there cannot be a one-to-one correspondence