Patching A Diagonalization
Fixing a flaw with less fuss?
Dana MacKenzie is the author of a terrific book, The Universe in Zero Words. Actually the book has many words, 216 pages of them, but is a brilliant history of mathematics as told through equations.
Today I want to talk about one of his chapters that discusses the equation .
This equation expresses Georg Cantor’s Continuum Hypothesis. Building on his proof that the reals are uncountable, Cantor believed that they are not only uncountable, but are exactly equal to the next “size” possible for sets, . We now know that this statement is independent of the standard axioms of set theory, thanks to the work of Kurt Gödel and Paul Cohen.
I just returned from visiting QCRI, a new research lab in Qatar, and read the whole book cover to cover during the sixteen hour plus flight home to Atlanta. It did not take the full trip to read, but it helped pass the time: I also ate, slept, and watched many movies.
Mackenzie has written a unique and beautiful book. He has the ability to explain math ideas in a few sentences that give a non-expert at least some idea what the idea is about. I strongly recommend the book as a great read—even if you are not on a very long flight.
As you might guess he presents the famous proof of Cantor that the real numbers are uncountable. One issue that he skips in the main text he addresses in a rather long footnote:
This argument has a slight flaw in it due to the fact that some numbers have two decimal representations, for example
He goes on to explain more about this issue in the footnote.
I have seen this issue raised many times before in regard to the proof and thought it might be worth a bit of discussion. The following is a small contribution to this “slight flaw.” Note I am only addressing those who believe that Cantor’s proof is correct—not those who still think the reals are countable. Recall we have discussed this issue a few times before—see here and here for more details.
Mackenzie presents the classic proof that takes any countable list of decimal numbers of the form and proves that there is another decimal number of the same form that is not in the list. He does this by building the diagonal number: he adds to each digit on the diagonal with the rule that wraps back to .
Let’s be a bit more mathematical. Given a countable list of infinite decimals
say the Cantor diagonalizer is the number defined by the rule: the th digit is . The theorem is of course that for all lists , the decimal is not in the list .
The difficulty, the difficulty Mackenzie calls a “slight flaw,” is that while is not in the list it could represent a number that is in the list. The issue is the generalization of the fact that
Call decimals that represent the same real number twins. A number can have at most one twin, and that only happens if the number ends in all ‘s or all ‘s.
The problem is that this could be the list:
The diagonal number is which is not in the list, but its twin, is in the list.
Fixing The Slight Flaw
One way to avoid the flaw is to use a better local rule. Ken and I, when we teach this argument use a better rule. Ken sends all digits to , except that he sends to . Thus, in the example we just gave,
The diagonalizer would be which works fine. The trick is to avoid those pesky ‘s and ‘s.
What I realized during the long flight is there is another way to keep the standard “add one to digit rule,” but still make the theorem work. This avoids changing the rule. It is not fundamentally better than the above rule change, but seems like a useful remark. It is based on the fact that in order to get into trouble the list must be strange.
Lemma: If is a countable list of decimals that contains a representative of every rational number, then the Cantor diagonalizer is not in the list , nor is its twin.
Proof: Suppose has a twin. There are two cases: one where ends in all ‘s and one where ends in all ‘s. Let’s look at the first case, since the other is handled by the same argument.
for some finite string of decimal digits . Let be the length of . Now since contains all rational numbers, it must contain each of
Since each of the above decimals is in the list, one of them appears at a position that is greater than . But then in the -th place, contains a or a , not a . This is a contradiction, and the lemma is proved.
No Pigeons Were Harmed In This Proof
If you examine the numbers again, you’ll see that members of the list have a in positions and higher. Since at most of those can come in the first entries of the overall list , it follows that at least one of them is still waiting to be diagonalized when we get past the part of . Thus in fact does have at least one in it.
This stronger inference uses the pigeonhole principle. We seem to have mentioned this only once, briefly, on this blog. Although it was coined as the Schubfachprinzip (“Principle of the Drawers”) by Johann Dirichlet as early as 1834, the first use of “pigeonhole” for it in English appears to be a paper by Raphael Robinson published in 1941. Ken thinks the term must be older and must refer not to “pigeons in holes” but rather to the racks of mail slots still called pigeonholes today in the colleges that make up Oxford and Cambridge and some other universities. If there are Fellows and letters arrive, some lucky Fellow will receive at least two letters
The pigeonhole principle is not trivial to teach, and there have been beautiful papers in proof complexity that quantify its power. If letters arrive, or , or exponentially many, the inference that someone gets two becomes progressively easier. If infinitely many letters arrive, at least one of the Fellows will receive infinitely many letters.
But our proof above needs none of these inferences. It is only saying that out of those infinitely many rational numbers with s, at least one will occur after the given finite number of places. We would be curious to know if this principle has a standard name. In any event, we feel it is transparent enough not to teach as a “topic.”
Is this simple observation useful in some context? I do like, personally, that we can keep the simple “add one” rule and avoid the flaw. What do you think?