What If Cantor’s Proof Is Wrong?
Believing impossible things
The Red Queen—I do not know her full name—is one of the most colorful characters in Lewis Carroll’s Through the Looking-Glass. She is known for her many wild statements and strange conversations—here is one with Alice:
“I can’t believe THAT!” said Alice.
“Can’t you?” said the Queen in a pitying tone. “Try again: draw a long breath, and shut your eyes.”
Alice laughed. “There’s no use trying,” she said, “one can’t believe impossible things.”
“I daresay you haven’t had much practice,” said the Queen. “When I was your age, I always did it for half-an-hour a day. Why sometimes I believed as many as six impossible things before breakfast!”
Today I want to talk again about Georg Cantor’s famous proof that the reals are uncountable.
Cantor’s proof reminds me of the above conversation: sometimes I feel like Alice and sometimes like the Red Queen. For many Cantor’s proof is impossible to believe, while for others it is impossible not to believe. Cantor’s proof is correct, but if you have trouble understanding it, or know it is wrong, please keep reading. Please. I would like to engage you.
Actually, there is a fundamental reason to doubt it. Statements asserting the uncountability of certain sets can be formalized in the first-order logic of set theory. But every consistent first-order logic has a model with a countable universe—thus one within which no uncountable sets actually exist. In such a model, everything we think we are saying about the real numbers is translated into an equally meaningful assertion about a set that is actually countable. This is ultimately because in a logical language we can say only countably many things before breakfast, and in a first-order language we can talk about only one thing at a time. We cannot actually say—or believe—uncountably many things before breakfast.
Approaching Cantor’s Proof
Cantor’s proof is strange. It is short, brilliant, important, and yet not believed by some. I find this intriguing: what makes this proof so disputed? What makes it the most discussed proof on the web? In short why is it so hard to believe? See here, here, here, or here for some examples.
But I will say that it is one great results of all time, in my opinion. So I am one of those who do believe in the proof, yet I think we can still discuss this belief, so please keep reading.
The result is of great importance, has a wonderful proof, and has led to many further insights. For instance, the famous result of Alan Turing on the undecidability of the Halting Problem, would be impossible without Cantor’s diagonal method. The same with Kurt Gödel’s Incompleteness Theorems.
Yet Cantor’s proof is special. For such a short proof it certainly has generated a huge amount of controversy. Many people do not believe it, call it nonsense, or worse. Some call people in this category nasty names—I do not think this is right, and I would never do that. I think rather there is something deep going on here. I wonder if the reason so many do not get the proof, is a symptom that we do not explain the proof well. I have tried several times before to discuss this result—see here and here and here.
In the remaining discussion let’s call those who believe the proof Uncounts and those that do not Counts. The names are selected to reflect what they believe: Uncounts believe that the reals are uncountable and Counts that the reals are countable. I am an Uncount, but being a Count is pretty good.
I am always very sensitive to those who misunderstand something: if this happens in one of my classes, I almost always assume it is my fault, not theirs. I once carried this perhaps too far, while teaching a class on complexity theory. We were about halfway through the semester, when a student asked a question that was essentially: what is a Turing Machine? I immediately said: oh, good question—my usual first words. Then as I started to answer the clearly very confused student, the rest of the class yelled:
Are you kidding?
They were mad that a student could ask such a question after hours of lectures on Turing Machines.
I will not repeat the famous diagonal proof. See here for a nice explanation. I assume both Counts and Uncounts know the proof. Of course the former do not believe it and the latter do.
Beyond The Proof
As an experiment let us assume that the reals are countable—that is, that Cantor is wrong. That there is a function
that is onto; recall this means that the range of the function is all of . Thus there is a list
that includes every real number at least once. The list includes all the rationals, the number , the number , and every real number you can think of and more. The list, the range of , contains all real numbers. This seems like a pretty cool situation. In this world where the reals are countable, let’s call it the Non-Cantor-World (NCW), what happens?
What I am curious about is what would it allow us to do? Would it really matter, or would it not change our understanding of real numbers, of analysis, of mathematics? Perhaps this is one of the reasons that people do not think that the proof is correct?
As stated above, we know there is an NCW if first-order set theory is consistent. If. We have recently covered the even simpler doubt about Peano Arithmetic being consistent. If we can overcome that doubt, what is easy to say about NCW’s?
Henri Lebesgue defined his famous measure on sets of real numbers, which is quite constructive, see here for a quick overview. Technically this measure is a map from certain sets of real numbers to non-negative real numbers . The measure has the following critical property:
for any disjoint measurable sets of real numbers. This is the property of countable additivity. The construction of Lebesgue measure starts by defining the measure of an interval to be , what else. Then it uses a clever extension method to define this for many more sets of real numbers. It is easy to show that this implies the inequality
where the sets need not be disjoint, but must be measurable.
Now this is a problem for Counts, because this leads to a contradiction. The key is that for any single point : this follows by the definition for intervals, . Recall
are all the real numbers. This shows that
But this is impossible since is easily seen to be . If you wish to avoid infinities, then just pick the subsequence of reals that lie in , call it . Then again
This seems to be a spot of trouble for Counts. If you claim that the reals are countable, then you must reject Lebesgue measure. But there is no diagonal proof inside the construction of the measure. This seems to be a problem—what does measure theory look like in an NCW?
Baire Category Theorem
A basic result about the structure of the reals is called the Baire Category Theorem. It is named after René-Louis Baire who proved it in his 1899 Ph.D. thesis.
A set of reals is called first category if it is a countable union of nowhere dense sets; otherwise it is of the second category. Thus if the reals are countable, then they form a set of first category. This follows since the sets are nowhere dense, and
But, Baire’s theorem is:
Theorem: The set of all the reals is of second category.
This follows since the reals form a complete metric space.
Again this seems to be a spot of trouble. If you are a Count, then this theorem must be false. Or it must be false that the reals are a metric space, or that the reals are complete. But the reals have a simple metric, the distance from to is just . And by definition the reals are a complete space, that is what makes the reals useful. Any convergent sequence converges to a real number. Note, the rationals do not form a complete metric space.
The Counts have one very neat positive result that cannot be proved in basic set theory. They can prove that the real numbers are well ordered. A set is well ordered by an ordering provided every non-empty subset has a least element. The natural numbers are well ordered by . Any non-empty set of natural numbers has a least element.
In the NCW the Counts can prove this immediately. Let and be two real numbers, then there are unique smallest and so that and . Define provided . This is easily seen to be a well ordering for the reals.
Thus, the real numbers have a well ordering: it is just the above . This usually is viewed with some surprise. The real number line seems to have the property that it should not have such an ordering. All proofs of this must use some powerful axioms beyond basic set theory. This is another possible spot of trouble for the Counts: How can it be so easy to prove that the reals are well ordered?
Does this help? Have I shed any new light on the issues? I doubt that any Count is now converted to an Uncount, but I certainly hope that I have not converted any Uncount to a Count.