Cantor's Diagonal Argument
Created | Updated Jan 28, 2002
Cantor wondered if it is possible to make a list of all the real numbers. Sure, this list would be very long, but is it at least theoretically possible?
He created the following argument, which, for reasons that will become obvious, is called Cantor's Diagonal Argument.
Suppose for the sake of argument that it is possible to create such a list of all the real numbers. Such a list might look something like this1:
Entry 1: 0 . 1 2 3 4 5 6 7 8 9 ...
Entry 2: 0 . 7 9 2 6 1 4 6 3 8 ...
Entry 3: 0 . 4 4 2 9 7 2 5 1 8 ...
Entry 4: 0 . 3 1 4 1 5 9 2 6 5 ...
Entry 5: 0 . 2 7 1 8 2 8 1 8 3 ...
Entry 6: 0 . 1 2 0 2 4 5 6 1 4 ...
Entry 7: 0 . 9 5 1 3 8 2 7 7 3 ...
Entry 8: 0 . 4 1 4 2 1 3 6 9 9 ...
Entry 9: 0 . 1 2 1 6 2 3 2 4 3 ...
etc.
Now create a new number n. What digits shall n have? Well, let's take the first digit of entry 1 as n's first digit, but we'll add one to it (if it's a 9, then we'll make the new digit 0).
OK, the first digit of entry 1 is '1'. So we'll make the first digit of n '2'. Let's do the same for the second digit. The second digit of entry 2 is '9', so we'll make the second digit of n '0'.
Here's the list of entries we have, with all the digits that we are going to select highlighted:
Entry 1: 0 . 1 2 3 4 5 6 7 8 9 ...
Entry 2: 0 . 7 9 2 6 1 4 6 3 8 ...
Entry 3: 0 . 4 4 2 9 7 2 5 1 8 ...
Entry 4: 0 . 3 1 4 1 5 9 2 6 5 ...
Entry 5: 0 . 2 7 1 8 2 8 1 8 3 ...
Entry 6: 0 . 1 2 0 2 4 5 6 1 4 ...
Entry 7: 0 . 9 5 1 3 8 2 7 7 3 ...
Entry 8: 0 . 4 1 4 2 1 3 6 9 9 ...
Entry 9: 0 . 1 2 1 6 2 3 2 4 3 ...
etc.
(Note that the digits are all on the leading diagonal of the list... that's why this argument is called the Diagonal Argument.)
The digits that we are going to use from the list are, in order: 1, 9, 2, 1, 2, 5, 7, 9, 3.
After we've added one to each digit, our new number n will look like this: 0.203236804... .
What can we say about n? Well, the first digit of n does not match the first digit of entry 1, therefore n is not entry 1 in the list. The second digit of n does not match the second digit of entry 2, therefore n is not entry 2 in the list.
The argument can be extended to cover every entry in the list. Whichever entry we look at, we know that it does not equal n because at least one digit must be different.
But at the start, we assumed that this was a list of all the real numbers. We have now constructed another number that we know is not in that list. Therefore the list is not complete.
We could stick n on to the end of the list, but then we would be able to use the same procedure to create yet another number that is not in the new list.
So no matter how long the list, we know that it is not possible for it to contain all the real numbers.
And this is what Cantor proved with his Diagonal Argument.