Outer Limits of Reason (16 page)

Cantor considered the subset of the real numbers between 0 and 1. This subset is denoted (0,1)
³
and contains numbers like 0.43905346 . . . , 0.5, 0.373468 . . . , etc. He tried to find a correspondence between the natural numbers
N
and the set (0,1). He was looking for some type of trick similar to the zigzag or necklace proofs that worked so well in the last section. Maybe we can have the natural numbers “snake” their way through every point in (0,1), as depicted in
figure 4.4
.

The numbers on top of the line are the natural numbers and the numbers below are the real numbers that correspond to them. This correspondence could be written as follows:

But this supposed correspondence did not work. In fact, every trick that Cantor tried in order to show that the natural numbers correspond to (0,1) failed. He always found that there were some elements of (0,1) that are missed in an attempted pairing.

Cantor failed to find a correspondence but he proved something far more interesting: that
no such correspondence could possibly exist.
⁴
Rather than stating that he was not clever enough to find a correspondence, he showed that
no one
, with any amount of cleverness, will ever find such a correspondence because such a correspondence cannot exist. By showing that a correspondence between the natural numbers and the set (0,1) does not exist, Cantor demonstrated that the set (0,1) is strictly larger than the set
N
. The elegant and simple proof will be presented shortly in all its glory.

Infinite sets that are equinumerous to the natural numbers are called
countably infinite
. We can at least start counting such sets. The correspondence with the natural numbers will help us count these sets. We saw in the last section that the sets
N, E, P, Z, N
×
N
, and
Q
are all countably infinite. Following that line of reasoning, infinite sets that cannot be put in correspondence with the natural numbers are called
uncountably infinite.
One cannot even begin to list the elements of an uncountably infinite set. We will prove that (0,1) is uncountably infinite. Sets that are uncountably infinite are vastly larger than sets that are countably infinite.

Cantor's result is the first proof that there are different types or levels of infinity. This is extremely counterintuitive. After all, who would have thought that there are different types of “going on forever and ever”? But in fact, there are. By simply following the logical definition of what it means for two sets to be the same size, Cantor came to this radical conclusion. Again—and this cannot be stressed enough—these distinctions between the different levels of infinities are used in modern calculus texts. With this knowledge in mind, engineers and physicists build bridges and rockets. It would be foolhardy to cross a modern suspension bridge if you knew that the engineer did not believe in Cantor's work. As counterintuitive as it seems, the different levels of infinity are fundamental to our understanding of the universe.

The actual proof is a proof by contradiction. In order for Cantor to show that no such correspondence between
N
and all of (0,1) exists, he assumes (wrongly) that such a correspondence does exist and arrives at a contradiction. Following the format introduced in
chapter 1
, we write:

There is a correspondence between
N
and (0,1) ⇒ contradiction.

The contradiction derived is a real number between 0 and 1 that is not paired off with any element of the proposed correspondence. Since we assumed that the correspondence pairs off
every
real number between 0 and 1, we have a contradiction.

Informally, the proof proceeds by describing a real number between 0 and 1 as

This real number is not in the given correspondence.

Or, to be more precise,

This real number is different from every other number in the given correspondence.

The proof is called a
diagonalization proof
and works as follows. Assume that there is some type of fancy correspondence between the natural numbers and every element of the set (0,1). We might illustrate such a correspondence as in
figure 4.5
.

On the left are the natural numbers and on the right we write what number in (0,1) it is paired with. With this alleged correspondence, we describe a number that is not on this list. The number will be a real number between 0 and 1 and denoted as
D
(for “diagonal”).
D
is derived from the diagonal of the alleged correspondence presented in
figure 4.5
.

• The 0th digit of
D
will be 6 because that is one more than the 5 in the 0th position of the 0th number of the alleged correspondence.

• The 1st digit of
D
will be 4 because that is one more than the 3 in the 1st position of the 1st number of the alleged correspondence.

• The 2nd digit of
D
will be 0 because that is different from the 9 in the 2nd position of the 2nd number of the alleged correspondence.

• The 3rd digit of D will be . . .

And the description goes on. We can eliminate the unimportant part of
figure 4.5
and see the description of the number
D
as in
figure 4.6
.

So the number
D
is 0.640914187. . . . This number is clearly within (0,1). However, it is not in this correspondence. Let's look for it:

• Number
D
cannot correspond to
0
because number
0
in position
0
is a
5
and number
D
in position
0
is a
6
.

• Number
D
cannot correspond to
1
because number
1
in position
1
is a
3
and number
D
in position
1
is a
4.

• Number
D
cannot correspond to
2
because number
2
in position
2
is a
9
and number
D
in position
2
is a
0.

• Number
D
cannot correspond to
3
because number
3
in position
3
is an
8
and number
D
in position
3
is a
9.

• etc.,

• Number
D
cannot correspond to
d
₀
because number
d
₀
in position
d
₀
is an
x
and number
D
in position
d
₀
is not
x.

• etc., . . .

Since
D
is not in this correspondence, we conclude that the purported correspondence is not a correspondence at all. In fact, what we did was to describe
D
as different from every row in the purported correspondence. Notice that
D
is not the only number that fails to show up in the correspondence. To find other such numbers, all you have to do is systematically go through every row and change some digit. By doing this, we are finding numbers that cannot be the same as any row. In the above, we changed every row by altering every element along the diagonal, but we could have done it in other ways. Furthermore, we altered it by adding 1 to the digit (except to the digit 9, which we made a 0). There are, however, many other ways to alter the digits.

One might try to describe another potential correspondence in which the number
D
does occur. However, the same trick can be done with that correspondence as well. There will be another number,
D′,
between 0 and 1 that should be in the correspondence but is not. Any potential correspondence will be missing elements of (0,1).
⁵

We conclude by saying that there are vastly more numbers in (0,1) that are not matched in any given correspondence than those that are matched. That is, the set (0,1) is much, much larger than the set of natural numbers. Uncountably infinite sets are immense compared to countably infinite sets. Throughout this book, we will come back to this fact over and over. Many sets will be shown to be countably infinite, which is minuscule compared to a larger set that is uncountably infinite. In fact, when we “subtract” a countably infinite set from an uncountably infinite set, we are still left with an uncountably infinite set.

There are many other uncountable sets. Consider the powerset of the natural numbers,
(
N
)—that is, the set of all subsets of
N
. We saw that for finite sets with
n
elements, the size of
(
N
) is 2
ⁿ
.
One might think that there is some trick for an infinite set that would show that a correspondence exists between a set and its powerset. This is not true. A correspondence between a set and its powerset cannot exist.