Cantor’s Non-Diagonal Proof
Cantor’s first proof that the reals are uncountable
Georg Cantor created set theory, a paradise that David Hilbert declared: “no one shall expel us from ” Hilbert’s full quote is: “No one shall expel us from the paradise that Cantor has created for us.”
“No one” referred to Leopold Kronecker who thought Cantor a “corrupter of youth”, and to Henri Poincaré who thought Cantor’s set theory a malady that would one day be cured. Even great scientists can be wrong about new directions–perhaps something we should all remember. If Cantor’s work was going on today, would he get funded or even get his papers into the top conferences? I wonder.
Cantor created set theory to solve problems in Fourier series, especially looking for conditions that imply that a Fourier series uniquely determines a function. This led him to consider actual infinite processes, which was a giant conceptual step beyond any previous work. Infinities had been used before in mathematics, but never studied in a way that Cantor did. While set theory may seem to be the most abstract of theories, its roots were based on concrete questions from function theory.
We all know the famous diagonal proof of Cantor, that proves that the reals are uncountable, so I will not repeat the argument here. If you need a refresher, or have not seen the proof before, there are many good expositions available.
The diagonal proof has been used over and over in mathematics. In the beginning of complexity theory, Alan Turing used a diagonal argument for his proof that the Halting Problem is undecidable. Later, time and space hierarchies were proved using Cantor’s method, with additional insights into Turing machine simulations. There are countless–bad pun–applications of Cantor’s diagonal proof method.
What you may not know is that Cantor discovered his wonderful proof in 1891. However, almost twenty years earlier, in 1874, he first proved that the reals were uncountable. His earlier proof (EP) is not based on diagonalization, does not seem to generalize, and is not well known.
The proof apparently was discovered in December 1873 and published in 1874 as “On a Property of the Collection of All Real Algebraic Numbers.” The main consequence that Cantor noted, at the time, was the existence of transcendental numbers in any interval. This had been proved earlier in 1844 by Joseph Liouville using constructive methods. The reason for the strange title was that Cantor was worried about opposition from Kronecker and others: yet his main result is that the reals are uncountable, not that there are transcendental numbers.
Today I would like to present the earlier proof, which I think you might enjoy seeing for two reasons. First, it is very different from the diagonal proof, and shows how Cantor’s thinking evolved over time. It also shows how deep the simple diagonal proof is: if it took the master almost twenty years to find it, one could argue that it really is deep. As I have said before, often things that seem trivial today were once impossible, were once unknown.
Second, I think the EP is an instance of an important principle on how we prove that objects exist. There are many ways that you can try to prove that some mathematical object exists. An obvious method, that sometimes works, is to “write down” the object in closed form. I will not be precise on what closed form means, but I hope you get the general idea. For example, when asked for a number that is not rational, you could write down . Or when asked for a function that is periodic you can give as an example.
Often, however, there is no simple way to write down what you want: the object that you are trying to construct is too complex. In this case a powerful method is to construct the object as a limit of simpler objects. This is exactly what Cantor’s EP does. I wonder about his EP, and whether or not it could help solve some of our open problems. More on that later.
The Earlier Theorem and Proof
Theorem: The real numbers are uncountable.
Cantor’s earlier proof (EP) assumes that
is a list of reals all in the interval . He then constructs, by a limiting process, a real number that is in the interval and satisfies, for all , . This of course shows that the reals are uncountable, but the proof seems more concrete, to me, than the diagonal proof.
Let . We will follow Cantor and construct a series of proper intervals
Suppose that we have constructed for , then we will construct the next interval as follows. Let . Select so that
and is not equal to . Then, is in at most one of the two intervals:
Let be the first interval that does not contain .
We claim that the nested intervals tend to an interval , which can be degenerate. Let be any point in . By construction, is in . Moreover, cannot be equal to any . This follows since at step we selected so that . But, since , it follows that is not in
Note, the fact that nested closed intervals tend to a limit interval is the place where Cantor uses the fact that the reals are complete. That is any bounded increasing (decreasing) sequence of reals has a limit point.
I hope you like Cantor’s proof. I find it more intuitive than the diagonal proof, perhaps that is why Cantor found the EP first?
An obvious open question is: can Cantor’s EP method be used to solve some theory problem? Is it just a curiosity, or is there something that is fundamentally useful about the method? What would the notion of limit be? In complexity theory we have used the diagonal method over and over, could it be possible that the EP method could have some advantage in solving some problems?