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, 
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.
The Argument
Mackenzie presents the classic proof that takes any countable list of decimal numbers of the form 
Let’s be a bit more mathematical. Given a countable list of infinite decimals
say the Cantor diagonalizer is the number 
The difficulty, the difficulty Mackenzie calls a “slight flaw,” is that while
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
The problem is that this could be the list:
The diagonal number is 
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 
The diagonalizer would be 
Another Way
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
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
Proof: Suppose 
Thus,
for some finite string of decimal digits 
Since each of the above decimals is in the list, one of them appears at a position 
No Pigeons Were Harmed In This Proof
If you examine the numbers again, you’ll see that 
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 
The pigeonhole principle is not trivial to teach, and there have been beautiful papers in proof complexity that quantify its power. If 
But our proof above needs none of these inferences. It is only saying that out of those infinitely many rational numbers with
Open Problems
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?
How about modifying the original list so that whenever a number appears its twin also appears? From the original list L, create a new list L’ which has this property by adding a number’s twin, if it exists, right after it in the list. Now use diagonalization against L’.
The n’th digit in two twins are either the same or differs by at most 1. So instead of “add one mod 10” you could simply use “add two mod 10”.
What happens when someone comes along and starts counting reals in the following way?:
Let real(1) = the first element of the set: 0<x<1;
Let real(2) = the first element of the set: real(1)<x<1:
……………
Let real(m+1) = the first element of the set: real(m)<x<1.
Egads, you’re right! My god, you have overturned a century of mathematics. You -must- publish!
Tomas,
You might have missed the point by a couple thousands of years, but who is counting anyway.
Like the rest of us, Cantor inherited the Euclidean point. If he has a scalpel sharp enough to cut a single point from a continuous line, the scalpel should be sharp enough to start chopping end points off line segments.
Just a metaphysical observation, not meant to be taken too seriously. 🙂
Heh heh, what do you mean by first? Cool, for R(2) it must be of the form 0.yyyyy… Please write down how many leading zero’s the number has after the decimal and its first few leftmost non-zero digits. For any actual listing (Counting) you have to be able to do this.
Not only are the real numbers not well-ordered, but also a well-ordered set can easily be uncountable. So this doubly doesn’t work.
It’s more accurate to say that the _standard_ ordering of the reals isn’t a well-ordering. Of course if you assume Choice then there must be _some_ well-ordering of the reals, but that’s a separate matter entirely. (On the other hand, it’s a well-known theorem that any sequence of reals compatible with the ‘standard’ order type must have countable order type itself, no matter how many reals there actually are, so this procedure can’t work in yet another way…)
‘Pigeonhole’ meaning ‘compartment for giving/receiving documents’ is standard usage in British English, not just at certain universities. (I’ve heard it in Australia as well, so it’s not even specific to the UK.)
The example in question strikingly highlights that Cantor’s diagonal construction of an unlisted real < 1 from the assumed enumeration runs the risk of confusing denotation with connotation.
Thus the expression `.4999…' is not a real number, but only the denotation of a real number. The real number denoted by `.4999…' is the limit of the Cauchy sequence of rational numbers `.4, .49, .499, .4999, …'. This limit is the real number denoted by `.5'.
So the first constraint on Cantor's assumed enumeration ought to be that it must list only non-rational real numbers < 1.
Now, for Cantor's construction to yield a non-rational real < 1 that is not in such an enumeration, it must be possible to assert for any such enumeration that the diagonal construction will not yield a recurring `9' after some point (as this would merely yield a rational number that is not in the enumeration by definition).
Prima facie, it would seem that such an assertion can only be made axiomatically.
Although such assertion may be possible in ZF or ZFC, to treat it as self-evident—as Cantor's diagonal argument appears to do—seems more theological than mathematical.
Sorry! That was a hasty response, and obviously wrong!
I have a high IQ and like math, but I cannot, no matter how much I might try, get my brain around this stuff. However, I have a son who eats this for breakfast, so he can carry the heavy load for me. Whew!
The more there is discussion about uncountability of reals the less intuitive the picture become. Initially, it was clear that it is possible to write a number that would be different from every number because at least one digit (on diagonal) is different. This intuition comes from the finite sets (and as such the Cantor argument seem to be the psychological trick). It is not clear, after all discussions, why the same logic should work for infinite sets. In particular, lets write the sequence
, e.g. 
reverse binary representation of 
. Since we have infinite numbers, infinitely many numbers are infinitely long. I understand argument that for every finite N, and nN+1 tells that we need to add countably many rows (numbers), equal to the size of the set at step N, and add “1” to the added part at the end. Therefore, for all countably many N the size of the set of all numbers with N digits (including infinitely many) is countable. The Cantor diagonalization argument would only say that for every n the constructed number is below diagonal. And by the definition of infinity, it does not matter how many diagonal digits (equals to tested numbers in the list) we tested there always at least one more. The power set arguments seem to be more convincing, unless we would have more discussion on it.
The only point I want to make is that Cantor argument by itself is not very convincing. It is based on assumption that we can write infinitely many digits, and test infinitely many digits at once, which is possible the reason of artificial superpower of real computation.
As usual half of the comment is cut. Sorry for disturbance.
How do we know that the only numbers with twins are of the form 0.x9999?
For bonus points, propose a fix that works when the real numbers are written in binary, rather than decimal expansion (it can be done).
‘Not the list of all real numbers but some special list of them can have a diagonalizer ending with all
‘s or 
‘s’ is that what your lemma prove?
Please ignore my previous comment. It was incorrectly formatted. Here is the correct one:
‘Not the list of all real numbers but some special list of them can have a diagonalizer ending with all
‘s or 
‘s’ is that what your lemma proves?
f.nasim
That is essentially right.
Another metaphysical observation: This one taken from the Wikipedia article about Cantor:
While extending the notion of number by means of his revolutionary concept of infinite cardinality, Cantor was paradoxically opposed to theories of infinitesimals of his contemporaries Otto Stolz and Paul du Bois-Reymond, describing them as both “an abomination” and “a cholera bacillus of mathematics”.[34] Cantor also published an erroneous “proof” of the inconsistency of infinitesimals.[35]
Did he sense the diagonal argument might need some patching down the road?
There is a simple way to counter this problem – use binary notation, and instead of changing a single digit of each number in the list, simply take each consecutive pair of digits and change them according to the following rule:
Change 10 to 01 and change every other pair of digits to 10.
So, the diagonal number must be different to every number in the list. And in this way, the diagonal number cannot be a number that ‘ends’ in infinitely many 1s. Furthermore, since the diagonal number does not terminate, it cannot have a dual representation, so that it cannot be a finite representation of a number in the list that ‘ends’ in infinitely many 1s.