May 02, 2004
Cantor's diagonal proof

Imagine you had listed all infinite series of digits in an infinite list of rows. Like this
1. 12376487648764234
2. 23479072756827345
n. 234...8344574534534
(the underlined 7 is in the n'th position)

Then if you took out the numbers I've marked underline bold and shifted them by one (1->2, ..., 9->0) and built the series of these digits
then that would be different from any series in the original list. We carefully built the list with one digit from each list in exactly the right place, but shifted by 1.
So there is a series not in the list of series - and this is true no matter how we list the set of series. There simply is no way to list them. The upshot of that: There are more infinte series than there are integers, even though there's an infinite supply of both integer numbers and infinite series. It's possible to be more infinite than the set of integers.

This is the heart of Cantor's celebrated diagonal proof about the noncountability of the real numbers. I first learned of this marvelously simple idea in high school (gymnasiet, altså) when I read one of the classics of expository math, Gödel, Escher, Bach by Douglas Hofstadter. I remember feeling exhilerated when the penny dropped. To think that you could get so dramatic conclusions from such a simple argument. That's when I knew I liked mathematics. This was really a bounty to go for, that kind of gearing for your thoughts - the world literally expanding before your very eyes, and not just by miles or light years, but infinitely, and not just that, but transinfinitely.

The power of the diagonal proof has also been proven by its use, in more technical guises, to prove all kinds of wonderful and mindboggling things. Among them the analogous results of Turing and Gödel on the stopping problem and the completeness of mathematical theories.

Posted by Claus at May 02, 2004 02:29 AM | TrackBack (0)
Comments (post your own)

The so-called diagonal "proof" proves nothing. It is impossible to imagine a full representation of even one "real" number. PI extended to Aleph-nought decimal places in a ribbon of nano point type would over-fill the universe, if, of course, there were sufficent time to produce it. A "complete" table of them is no less unimaginable and any manipulation of said table is meaningless. Infinity is infinity period ... there are no orders of all.

Posted by: alex hay on October 28, 2007 5:57 PM

Sorry Alex - but that's just plain nonsense - or at the very least philosophizing irrelevant to mathematics. At best you're engaging in some kind of constructivist exercise that is not very fruitful in the long run.

Cantor proves that the mathematical version of the commonplace notions of "size" and "equal size" admits an infinite number of different sizes of sets. No bones about it.

For a good mathematical view on mathematical philosophy see

Posted by: Claus Dahl on October 28, 2007 5:59 PM

Claus - a "fruitful" approach might begin by constructing the table of reals in ascending order. The smallest real greater than 0 would, of course, be 1/Aleph-nought represented by 1 in the Aleph-nought decimal place (regardless of number base). Can you find one less than the smallest? According to the proof, we would expect to find an infinity of them yet I can't imagine even one ... unless, of course, Aleph-nought + 1 > Aleph-nought, which by Cantor's definition is not true.

Posted by: alex hay on October 30, 2007 6:00 PM

Alex, what you're saying makes no sense. Aleph-nought is not a number. You cannot divide by it. 1/Aleph-nought is an ill defined nonsensical concept - until you provide a definition of division that makes sense.
Whatever you say after this - meaningless - construction is therefore also quite meaningless, so I can't realy comment on your construction, other than say that you're not talking about concepts we use in mathematics and consequently aren't saying anything meaningful about Cantor's diagonal proof.

Oh and by the way - unless you're using another ordering than the usual one, 1/2*(1/aleph-nought) (whatever the latter number is chosen to mean) is a real smaller than aleph-nought. To get a notion of "smallest real larger than zero" you need to provide another ordering - which you haven't.

Posted by: Claus Dahl on October 30, 2007 6:05 PM

Claus - nice chatting with you, I really have no more to say which is to say, I am finally speechless.

I reccomend


Posted by: alex hay on October 30, 2007 7:55 PM

I see your reference contains no mathematics. I am not surprised.
Like I said from the outset: I can appreciate if you're trying to say that you're a constructionist (I'm unsure if you're familiar with the term - but the complaint you link to is a constructionist complaint). I am not a constructionist. Non-constructionist mathematics is both productive of new ideas *and* of utility. That ends the argument for me.

I implore you to visit the sincere and complete reply to constructionist and philosophical complaints expressed by Dieudonne in the link I gave above:

(btw: The closing line about "actual infinity" not being "more ridiculous" than eating meat clinches it for me, if the math doesn't. I'm a carnivore, fully in favor of the mass killing of animals to satisfy my appetite.)

Posted by: Claus Dahl on October 30, 2007 7:56 PM


We agree that:

1) Aleph-nought represents the smallest number which is beyond representation.
2) Cantor/you would say that there are larger numbers/entities which are beyond representation.
3) All reals are contained in the interval 0-1.

Yet, it seems we disagree.

We seem to argue the meaning of representation and I here try to male[sic] myself clear.

In reference to 3) above:

0 represents that which does not exist, the absence of (any and) all; 1 (Aleph-nought) represents that which cannot be reasonably imagined, the set of (any and) all.

IMO, 0 is the nearest approximation of Aleph-nought, a mere (the) place-holder for 1.

Cantor managed to convince himself (and a seemingly significant following) that there exists “something” outside of nothing and everything+1.

Wild and crazy guys and gals.


Posted by: alex hay on November 16, 2007 5:34 AM

I don't agree with you on any of the points you give above. Please see the Dieudonne reference I give for what I believe in terms of the philosophy of mathematics. As for the language of mathematics, I believe in Cantor.

Posted by: Claus Dahl on November 16, 2007 5:41 AM
Help the campaign to stomp out Warnock's Dilemma. Post a comment.

Email Address:


Type the characters you see in the picture above.

(note to spammers: Comments are audited as well. Your spam will never make it onto my weblog, no need to automate against this form)


Remember info?