Cantor's Diagonal Argument

1 Conversation

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.

1Here we consider only numbers between 0 and 1 for convenience. However, the same argument will apply for all real numbers.

Bookmark on your Personal Space


Conversations About This Entry

Entry

A383915

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry


Written and Edited by

Disclaimer

h2g2 is created by h2g2's users, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the Not Panicking Ltd. Unlike Edited Entries, Entries have not been checked by an Editor. If you consider any Entry to be in breach of the site's House Rules, please register a complaint. For any other comments, please visit the Feedback page.

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more