Cantor's Diagonal Argument is a powerful but subtle technique for proving certain theorems about countability. A lot of people's first exposure to this argument is when it is used to 'prove' that the set of real numbers is uncountable. I think this is a misguided use of the argument because it requires you to bring a highly developed understanding of countability issues to the table in the first place. (In effect you must already accept what the proof is supposed to prove!)

It Doesn't Work in the Finite Case

The sheer counterintuitiveness of the 'proof' for reals is that it manifestly doesn't work in the finite case. And yet when we extend it to the infinite case required to complete the proof, we must somehow accept that this is not a problem! I explain how it is broken in this section. (The argument is usually based around decimal fractions of infinite length, so I present examples based around decimal fractions of finite length.)

Consider an enumeration of decimal fractions of finite length. For example, let us consider all of the decimal fractions with just 1 digit in them. Here is my simple enumeration scheme for these numbers (being a computer scientist, I'm starting at 0... actually I do so because it simplifies my argument later):

Now let us apply Cantor's Diagonal technique to this. We start at the top right and get the digit '0', and we add 1 to it, forming '1'. We have to stop here as we are only considering single digit decimal fractions. So the number formed by this technique is '0.1'. But that's in my enumeration already - it's entry 1!

I can extend my enumeration to work for longer number of digits. Suppose I want to enumerate all 3-digit decimal fractions. Well I shall just write my entry numbers with three digits (Entry 0 becomes 000, Entry 1 becomes 001, 2 becomes 002 etc), invert the order of the digits, and place them behind the decimal point, like so:

and so on. Note that a pleasing feature of this system is that the first 10 entries are exactly the same as they were for the 1 digit enumeration. In fact this system can easily be extended by just carrying on up with the entry numbers - pick any decimal fraction of any finite length, and I can tell you what entry number it will have in my enumeration.

But sticking with the 3-digit case, let's apply Cantor's Diagonal mechanism again. The first digit in the first entry is '0', the second in the second is '0', and the third in the third is also '0'. Adding one to each, as the mechanism requires gives us the number '0.111'. This is entry number 111 in my scheme.

In fact we can generalize this to decimal fractions of any positive integer length (any N-digit decimal fraction, where N is a positive integer). The number that Cantor's Diagonal argument will always be N '1' digits with a decimal point right at the front. And this number will always have an entry in the enumeration, and that number is given by the sum from 0 to (N-1) of 10^N. (I.e. it is the number which is N '1' digits in a row, and if it makes you happy you can stick a decimal point after them.)

It's easy to see why this is happening. Cantor's mechanism is supposed to generate a number we don't have in the sequence by confounding us at every turn - by making every digit it chooses one it didn't find. This works fine, so long as the array of numbers you are choosing from is either square, or is wider than it is long. So the following square enumeration of 3-digit decimals:

is clearly subject to Cantor's mechanism - that generates the number '0.111' which is evidently not in the list. Likewise this enumeration:

is equally prone - Cantor's diagonal only gets as far as the number '0.25' but again this is clearly not in the sequence. The situation in which the diagonal fails to generate a new number however is where it runs off the side too quickly - if the matrix of numbers is narrow and tall, the algorithm doesn't have time to generate a new number. To put it another way, in a thin narrow matrix (such as the ones I started with) we can list every single possible combination of digits for a given maximum length of decimal fraction. And the enumeration scheme previously demonstrated, will generate such matrices for binary fractions of arbitrary integral length.

The reason this is so often missed on popular presentations of Cantor's argument is the way that ellipses are drawn at both sides of the table. These are just supposed to show that the table carries in in both directions (for ever!), but they are drawn in a fashion that leads you to assume that of course any such table listing possible fractions is bound to be square. But the enumeration presented above shows that any finite enumeration is a very long way from being square: it's tall and thin (and hence any finite enumeration is not a victim of Cantor's diagonal argument).

So Am I a Heretic?

No I'm not. I have seen convincing proofs that real numbers are not countable. I accept the existence of irrationals, and I even accept (despite how it may appear) that Cantor's Diagonal Argument is valid and useful, if applied appropriately. So how do I resolve this with the argument I have presented so far? It's simple. To accept the popular use of Cantor's Diagonal argument in demonstrating the existence of irrational numbers, you have to accept on trust this axiom:

• It is meaningful to talk about a decimal fraction with an infinite number of digits.

Any decimal fraction is mathematically equivalent to a sum of the value of all of the digits¹. In fact it's a geometric progression - the value of a digit is d10^(-i) where 'd' is the digit itself, and 'i' is the position of the digit. For a decimal of finite length this is fine - we just do the sum and that's the value. But for one of infinite length, we suddenly have to accept that we can do a sum over infinity of a geometric progression. As I understand it this is more or less the definition of a real number.

So we are being asked to accept as an axiom that real numbers exist. What were we trying to prove again? Oh yes, that real numbers exist and that they're different from the rationals. Evidently this application of Cantor's Diagonal Argument leads to a circular argument.

Don't misunderstand me. I know that it is possible to prove that there are reals which are not rationals. (I have often being accused of pig-headedness or ludditism as people assume that I am just rejecting the existence of the reals. This is a profound mischaracterisation of my argument.) And given a sufficiently subtle understanding of countability and infinities, then there's nothing intrinsically wrong with this diagonal demonstration, but the point is that it doesn't prove anything - the one thing it sets out to prove is something that you already need to have understood and accepted in advance! So I would describe it not so much a proof as an interesting mathematical curiosity.

So I don't have a problem with the diagonal argument as such, but I believe it's considerably more subtle than most people give it credit for, precisely because of the deep understanding of infinities that is required to make effective use of it. The key demonstration here is this: In every single finite version of this argument, Cantor's Diagonal method fails to provide a number which wasn't listed further down in the enumeration. When we move to an infinite version, this behaviour vanishes as if by magic; somehow the matrix of numbers effectively becomes square, even though it never was in any of the finite cases. If anything this demonstration should make anyone not already happy with the uncountability of the reals highly suspicious! And that's what I don't like about this, the canonical use of Cantor's Diagonal Argument.