Numbers | A History of Numbers | Propositional Logic | Logical Completeness | The Liar's Paradox
Logical Consistency | Basic Methods of Mathematical Proof | Integers and Natural Numbers
Rational Numbers | Irrational Numbers | Cantor's Diagonal Argument | Imaginary Numbers | The Euler Equation

Also known as Cantor's Diagonal Method, Cantor's Diagonal Process and Cantor's Diagonal Proof.

Introduction

We humans often have problems understanding concepts that have to do with infinity or infinitely large quantities. For example, something that startles many the first time they hear it is that two quantities, both infinite, do not have to be the same 'size'.

One example of this is the integers versus the real numbers. The integers are what we call a countable set, because it is possible to count them all.¹ This can be done by starting from 0, then going on with -1, 1, -2, 2, -3, 3, etc. The integers (or rather the positive integers) are sometimes even called counting numbers.

This kind of process is not possible among the real numbers, however. If we think about it, we quickly realise why: We could of course start from 0, but what would our next number be? 0.1? No, surely something smaller. 0.0000001 perhaps? There is no way of knowing, as we could have an arbitrary amount of zeroes before the 1, and it would still be possible to insert yet another one. As we cannot count all the real numbers, we say that they constitute an uncountable set.

As is always the case in mathematics, it is unfortunately not enough to realise that something is the case. It always has to be proven. This particular theorem was proven around the turn of the 20th century by a German mathematician named Georg Cantor. His proof is generally referred to as Cantor's Diagonal Argument.

Before looking at the actual proof, which is an example of an indirect proof (proof by contradiction), there is one thing we need to make sure that we understand: there are just as many real numbers in the interval [0,1]² as there are from minus infinity to plus infinity or, in other words, that the numbers in this interval are also uncountably many. It is necessary to be aware of this, as Cantor's proof deals only with the real numbers between 0 and 1, but the result applies to the whole set of real numbers.
The proof that [0,1] is equivalent to all the real numbers can be found under the entry on Cardinality and will therefore not be quoted here. However, if we think in the same way as we did when trying to understand that the real numbers are uncountable, we should be able to more or less grasp the concept.

The Proof

What Cantor started out with was the assumption that the real numbers between 0 and 1 are countable (remember that we are dealing with an indirect proof). If they are countable, it should be possible to make a list of all of them. Such a list could begin like this³:

0 . 1 2 3 4 5 6 7 8 9 ...
0 . 7 9 2 6 1 4 6 3 8 ...
0 . 4 4 2 9 7 2 5 1 8 ...
0 . 3 1 4 1 5 9 2 6 5 ...
0 . 2 7 1 8 2 8 1 8 3 ...
0 . 1 2 0 2 4 5 6 1 4 ...
0 . 9 5 1 3 8 2 7 7 3 ...
0 . 4 1 4 2 1 3 6 9 9 ...
0 . 1 2 1 6 2 3 2 4 3 ...

The ellipses (...) signify that the numbers have more than nine decimals, but that we won't bother to write them out, as they are infinitely many (and we don't need to know them all anyway). Also remember what we said above: that the list could begin like this; the list itself will, naturally, also be infinitely long.

What we want to do now is to prove that, if all the real numbers in [0,1] are really in this list, there must be an absurdity or contradiction somewhere. We will do this by looking at the diagonal which is formed by the first decimal of the first number in the list, the second decimal of the second number, and so on. It is the use of this diagonal that has given the proof its name.

The following table shows our nine first numbers again, this time with the diagonal in question highlighted:

0 . 1 2 3 4 5 6 7 8 9 ...
0 . 7 9 2 6 1 4 6 3 8 ...
0 . 4 4 2 9 7 2 5 1 8 ...
0 . 3 1 4 1 5 9 2 6 5 ...
0 . 2 7 1 8 2 8 1 8 3 ...
0 . 1 2 0 2 4 5 6 1 4 ...
0 . 9 5 1 3 8 2 7 7 3 ...
0 . 4 1 4 2 1 3 6 9 9 ...
0 . 1 2 1 6 2 3 2 4 3 ...

Using this diagonal, we construct a new number that we shall call a. We then get that a=0.192125793... There is nothing particular about a - according to our assumption that all real numbers between 0 and 1 are in this list, so is a (somewhere further down).

What we will do next is to use a to create another number, b. Let us look at the first decimal of a. If it is a 2, let the first decimal of b be a 1. If it is not a 2, let the first decimal of b be a 2. Now look at the the second decimal of a, and according to the same rules decide what the second decimal of b should be. Repeat this for all decimals in a and b. In proper notation, we write this as:

Let us look at our example. The first decimal of a is a 1 and the second us a 9 (neither of which are 2), so our first two decimals of b will therefore be 2s. The third decimal of a is, however, a 2, why the third decimal of b will be a 1. Eventually we will arive at the result b=0.221212222.

Why is b interesting? If we compare it to every number in the list we will understand why. We can see that b cannot possibly be the first number in the list, as there is at least one decimal (the first one) that is different. We also know that it cannot be the second number, as at least the second decimal is different. This will be true for every number in the list. So what have we proved? We have proved that b is not on the list - but we started out by assuming that every real number in [0,1] was in the list! In other words, we have reached a contradiction, meaning that our assumption - that it is possible to make a list of all the real numbers between 0 and 1 - was false.

There is one last question that we might want to ask ourselves before we accept that our proof is entirely correct. What would happen if we added this new number b to the end of the list? Would we not then have a list of all the real numbers in the interval? No, as we could repeat the entire procedure again, and then get a number c that is exactly equal to b, except for one decimal. It would not be equal to any other number in the list either, and we would have to add this number to the list, too. No matter how many times we repeated the procedure, our list would never be complete.

Conclusion

We can now conclude: It is not possible to make a list of all the real numbers in the interval [0,1], and therefore they are not countable. The same is true for all the real numbers (as we realised in our introductory discussion). Therefore, in a sense that it is rather difficult to understand right away, there are 'more' real numbers than integers.

References

For a closer look at what is meant by the size of a set, read about Cardinality.
Another very interesting uncountable set is the Cantor Set.

---

¹ Given an infinitely long period of time, of course.
² This means "all real numbers greater than or equal to 0 and smaller than or equal to 1".
³ It is not important in which order we write the numbers. What is important here is that we assume that we have written all the real numbers in this list.