Thursday, January 21, 2010

a most loved and hated theorem

There is a concept which corrupts and upsets all others. I refer not to Evil, whose limited realm is that of ethics; I refer to the Infinte.
- Jorge Luis Borges, Avatars of the Tortoise

Young man, in mathematics you don't understand things. You just get used to them.
- John von Neumann

There have been a lot of nice posts recently about favorite theorems (at f(t), SumIdiot, and Research in Practice, for example).

I found it interesting that one of them (Kate Nowak of f(t)'s favorite), the uncountability of the Real Numbers via Cantor's Diagonalization Argument, also seems to be one of some people's most hated theorems.

Witness the raging debate that ensued just a short while ago when Mark CC of Good Math, Bad Math did the public service of explaining why a recent Cantor-denier crank was mistaken. More recently, over at P=NP there is an excellent post about Cantor's diagonal method that is also generating plenty of comments.

Cranks aside, a good number of smart people have been troubled by Cantor's argument, and how it is used. Ludwig Wittgenstein was not a Cantor denier, but my reading of his Remarks on the Foundations of Mathematics is that he felt that the way that we talk about the results of the argument causes us to skirt close to mathematical and linguistic nonsense. Wittgenstein refers to the diagonalization method as a "puffed up proof" because people claim that it shows more than it really does - to him, it shows us that "the concept real number has much less analogy with the concept natural number than we, being mislead by certain analogies, are inclined to believe" and that we are further mislead to believe that it reveals a property of the set of real numbers, rather than a limitation of the concept of "set." Wittgenstein put much greater limitations on mathematical discourse (and on sets) than most practicing mathematicians would, but his discomfort at the idea of 'larger' infinities should be noted, and we should realize that others who share this discomfort are in good company.

Cantor's diagonal argument is certainly one of my favorites, and over time I've come to appreciate it more as I have slowly understood (or gotten used to) its centrality to a surprising ecosystem of theorems and proofs that include the undecidability of the Halting Problem (which I think gets a vote for one of my  favorite theorems, whichever proof you use), fixed point theorems, Godel's incompleteness theorem, and Russell's paradox. (There is an interesting and accessible development of Cantor's diagonal argument in the context of fixed point theorems via category theory in the book Conceptual Mathematics by Lawvere and Schanuel; the less accessible version of the same is here.)

We can gain a lot of perspective on the Cantor-haters by reading an interesting paper by Wilfrid Hodges (mentioned by Richard Lipton of the P=NP blog). Hodges recounts his experience fielding dozens of papers attacking Cantor's diagonal argument while he was a journal editor. (Hodges paper is in postscript here, and here is a pdf.)

An observation by Mark CC  in his post, mentioned above, is also noted by Hodges: "many of our authors failed to realize that to attack an argument, you must find something wrong in it. Several authors believed that you can avoid a proof simply by doing something else." Or as Mark puts it: "You can't refute Cantor's proof using an enumeration without addressing Cantor's proof. This is just yet another stupid attempt to refute Cantor without bothering to actually understand it."

But why do some people react so badly to the non-countability of the Reals via Cantor's diagonalization method? Perhaps it is the same reason that some react to it so favorably. Hodges suggests:

It's nothing more than a guess, but I do guess that the problem with Cantor's argument is as follows. This argument is often the first mathematical argument that people meet in which the conclusion bears no relation to anything in their practical experience or their visual imagination... and even now we accept it because it is proved, not for any other reason.

It seems that we are often limited in our appreciation of what mathematics can prove, how proof works, and what we should expect to completely comprehend. Cantor's argument tests the limits of all of these, and sometimes we don't pass the test.


  1. Lawvere's paper is taken much further in this paper.
    Its great.

    E.V. Bazarov

  2. Thanks for the link! looking forward to reading it.

  3. Well, I am certainly not a Cantor hater, but I have also problems - like others - to comprehend his proof. This has certainly to do with constructing the infinite limit (?)

    I agree, that if I use a list with a finite amount of real numbers between 0 and 1 like
    This list of 3 elements shall be called ListR_0
    I'm able to construct an element which has not been counted yet, say
    Now I can use complete induction to show the same thing for any list of real numbers {ListR_i}.

    But why exactly does this fail for natural numbers.
    This shall be called ListN_0.
    I construct at new element by NewE=Max(ListN_0)+1=4. I can tell that maximum e.g. by reordering ListN_0 from smaller to larger elements.
    With complete induction I can also show that I can _always_ construct a new element for any ListN_i! Are now natural numbers N also uncountable?

    Or is my implicit assumption erroneous, that the construction of a new element is the crucial point of Cantors 2nd argument proof?

    Please help me understand, I am extremely interested in comments.

  4. Cantor's proof involves using the entire decimal expansion of each real number. The new number you construct that is not supposed to be in the list is defined by making the ith decimal place of the new number different from the ith decimal place of the ith number in the list. You can certainly apply that to list of natural numbers, each of which has 0 in every decimal place. (3 is 3.0000..., etc). You will get a real number that is not in the list of natural numbers. Of course, this is not surprising.