Are The Reals Really Uncountable?
A discussion of Cantor’s famous diagonal method
Georg Cantor discovered his famous diagonal proof method, which he used to give his second proof that the real numbers are uncountable. In an earlier discussion I have given the first proof that Cantor discovered years earlier.
Today I want to talk about what I plan to cover this week in my complexity class: the diagonal method of Cantor.
In my teaching experience, students find it hard to believe Cantor’s diagonal method. Perhaps it is my fault, but I have talked to others who teach the same result, and I hear the same comments. The diagonal method is elegant, simple, and is deep. Students usually follow the method line by line, but I am sure that many really fail to get it. Perhaps that it is a proof by contradiction makes it hard to follow? But, they seem to get other proofs by contradiction. Or is the key problem that it is about infinities?
Here is an interesting quote by the logician Wilfrid Hodges:
I dedicate this essay to the two-dozen-odd people whose refutations of Cantor’s diagonal argument have come to me either as referee or as editor in the last twenty years or so. Sadly these submissions were all quite unpublishable; I sent them back with what I hope were helpful comments. A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument — what had it done to make them angry with it? So I started to keep notes of these papers, in the hope that some pattern would emerge. These pages report the results.
You might enjoy his essay—it is a careful treatment of some of the issues that people have in following Cantor’s famous argument.
Let’s turn to prove the famous result.
I will give two different proofs that the reals are not countable. Actually, I will prove the statement that no countable list of infinite sequences of –‘s can include all such sequences.
This is enough because of two observations. First, it is enough to show that the interval is uncountable. Second, the reals in the interval have the same cardinality as the set of all of infinite – sequences.
The first proof is essentially the famous diagonal proof, with a slight—very slight—twist. The second, is a proof based on probability theory.
A Variant of The Classic Proof:
Consider the following triangular array of bits that has an infinite number of rows:
where each is a or a .
Our plan is to construct an infinite sequence that is different from each row. Let’s construct . We need that is different from so there is no choice: set equal to . Note, there was no choice here: often the lack of choice is a good thing. In a proof if there is no choice, then you should be guided to the right choice. Henry Kissinger once said:
The absence of alternatives clears the mind marvelously.
Thanks to our friends at Brainy Quote.
Next we must make different from . We could be lucky and
But, we must be prepared for the worst case. So we set equal to . This forms a pattern: the simple rule is to set to .
Look at the triangular array again and we see that is just equal to the negation of the diagonal elements:
We want to construct a so that it is different from each row. Just forget about the extra part of the array: use only one from the first row, two from the second row, and so on. The above just becomes our old friend:
But, we just constructed a that is different from each row. I claim that works with the array that has rows of infinite length. The key observation is trivial: if differs from the start of a row, it certainly is different from the whole row. That is it.
A Probability Based Proof:
In this proof we use the probabilistic method. We just pick a random – sequence and claim with positive probability that it is not equal to any sequence in the list Thus, such a must exist.
Let be the following event:
The key is the event defined as
The probability of is at most
which is equal to
Thus, the probability of the complement event is .
But, is true implies is not equal to any . For suppose that was equal to . Then, it must be the case that
for any . In particular, the event must be true, which is a contradiction since
Even though the methods look different, if you look closely you would
notice that they both have Cantor’s diagonal method at their heart.
There are many other papers on alternative approaches to proving the reals are uncountable. Matt Baker has a great explanation in his paper: definitely take a look at his version. It is closer to the first proof that Cantor found.
Did you always believe the classic proof that the reals are uncountable? Or did this discussion help? I hope it increased your understanding, rather than decreased it.