Poor Georg Cantor.
During his life, he suffered from dreadful depression. He was mocked by
his mathematical colleagues, who didn’t understand his work. And after his
death, he’s become the number one target of mathematical crackpots.
As I’ve mentioned before, I get a lot of messages either from or
about Cantor cranks. I could easily fill this blog with nothing but
Cantor-crankery. (In fact, I just created a new category for Cantor-crankery.) I generally try to ignore it, except for that rare once-in-a-while that there’s something novel.
A few days ago, via Twitter, a reader sent me a link to a new monstrosity
that was posted to arxiv, called href="http://arxiv.org/abs/1001.2874">Cantor vs Cantor. It’s novel and amusing. Still wrong,
of course, but wrong in an amusingly silly way. This one, at least, doesn’t quite
fall into the usual trap of ignoring Cantor while supposedly refuting him.
You see, 99 times out of 100, Cantor cranks claim to have
some construction that generates a perfect one-to-one mapping between the
natural numbers and the reals, and that therefore, Cantor must have been wrong.
But they never address Cantors proof. Cantors proof shows how, given any
purported mapping from the natural numbers to the real, you can construct at example
of a real number which isn’t in the map. By ignoring that, the cranks’ arguments
fail: Cantor’s method still generates a counterexample to their mappings. You
can’t defeat Cantor’s proof without actually addressing it.
Of course, note that I said that he didn’t quite fall for the
usual trap. Once you decompose his argument, it does end up with the same problem. But he at least tries to address it.
Enough preliminaries. Let’s dive in and see what he did. His abstract
gives about a coherent a description as anything else in the paper, so
we’ll start with that.
Cantor’s diagonal argument makes use of a hypothetical table
T containing all real numbers within the real interval (0,1). That table
can be easily redeﬁned in order to ensure it contains at least all rational
numbers within (0,1). In these conditions, could the rows of T be reordered
so that the resulting diagonal and antidiagonal were rational numbers? In
that case not only the set of real numbers but also, and for the same reason,
the set of rational numbers would be nondenumerable. And then we would
have a contradiction since Cantor also proved the set of rational numbers is
denumerable. Should, therefore, Cantor’s diagonal argument be suspended
until it be proved the impossibility of such a reordering? Is that reordering
possible? This paper address both questions.
To understand this, let’s do a quick review of Cantor’s diagonalization.
Cantor is trying to prove that the set of real numbers is strictly larger than
the set of natural numbers. He uses proof by contradiction: he starts by
supposing that the naturals and the reals have the same size, then shows how
that inevitably leads to a contradiction.
If the set of real numbers is the same size as the set of natural numbers,
then there is a one-to-one mapping f from the natural numbers to the real
numbers in the range (0, 1). So he uses that to lay out a table, where the
first row is f(0), the second row is f(1), etc. In the table, the first column
is the first digit; the second column is the second digit, and so on.
If the mapping is really one-to-one, then every real number must be in the
table. But Cantor shows how you can easily create a new real number which is
not in the table. All you do is look at the digit in position (1,1)
in the grid – and change it. Then look at the digit in position (2,2), and
change that. Then the digit in (3,3). And so on: for row N in the table, you
change digit #n. What that procedure does is generate a number which is
different from every number in the table in at least one digit. Therefore it’s
not in the table. That’s a contradiction: we said that every real number had to
be in the table, but we’ve just constructed a real number which isn’t.
What our author is proposing is to take Cantor’s diagonalization,
and do two things to it.
First, he changes it so that it’s a mapping from the natural numbers
to the rationals instead of the natural numbers to the reals.
Then, he looks at the diagonal of the and re-arrange the rows of it.
He re-arranges the rows of the table until the number in the diagonal is
a rational. Now he’s got a table which contains all of the rationals, and whose
Cantor diagonal is a rational number. So it looks like he’s got a counter-example
for the idea that there’s a one-to-one map between the naturals and the
rationals. If that were the case, then Cantor would be in real trouble: Cantor
also wrote a well-known proof that there’s a one-to-one mapping between the
natural numbers and the rationals. So if our intrepid author is correct, then
either Cantor is wrong about there being no mapping between the
naturals and the reals; or he’s wrong about there being a mapping between the
naturals and the rationals; or his entire system of comparing the cardinality
of infinite sets is completely inconsistent.
Looked at naively, it seems sort of compelling: if we can build
a Cantor table that shows that the rationals aren’t countable, then
Cantor is wrong. So what’s wrong with this proof?
Remember: in this proof, we start with a standard Cantor diagonal over the
rationals. That is, we start with an enumeration of rationals, lay it out in a
table, and then read off a number which isn’t in the set of rational numbers.
In other words, we’ve used a Cantor table to produce an irrational number. At
this point, there’s nothing remotely compelling: we know that there
are irrational numbers, and all that the construction did at this level is
generate one. This is neither surprising nor particularly interesting, and
it’s certainly no threat to Cantor’s famous proof.
Once he’s got the construction of the irrational, he re-arranges
the rows of the table. He tries to re-arrange it so that the number that reads
down the diagonal of the table is a rational. This is exactly the problem: he
can’t do that.
Why not? Because the construction of the re-ordering is invalid. To
quote the paper:
If it were possible to reorder the rows of T in such a way that a rational antidiagonal
could be defined, then we would have two contradictory results: the set Q of
rational numbers would and would not be denumerable
That is, the re-ordering is absolutely critical to his argument. But
the re-ordering is, itself, self-contradictory.
The argument for the existence of the re-ordering is that
even irrational numbers generally have some probabilistic properties
about their digits. Using those, we can define an initial table
where its counter-example number has a desired set of properties
in the distribution of its digits. (You could use a variety of
properties – but, for example, if the distribution of digits is
uniform, then you could conceptually re-order the rows to produce
So far so good. Now, you re-order the rows, so that the diagonal is
a rational number.
Here’s the problem: you’re constructing a chosen rational
number. That is, you know what rational number you’re re-ordering the
rows to create. Since it’s a rational, it’s got to be in the table. And since
you know what rational it is, you’ve got to know what row in the table
it’s going to be. So go look at that row.
By the definition of the diagonalization, the value of the diagonal must
be different from the value of any of the rows by at least one digit. So the
rational number that you’re forming must be different from itself by
at least one digit.
Bzzt. No good. The re-ordered rational diagonalization is self-contradictory.
In fact, it’s a classic self-referential foulup.
This is an obvious problem, and it’s appalling that the author
of the paper, who is supposedly a math professor, couldn’t see it. For all
of the crazy rigamarole he goes through to construct his re-ordering, he never
bothers to look at this simple problem. What kind of mathematician could build
a construction like this and never consider the self-referential case?
I’ll give the author one thing: at least he actually addressed Cantor’s
proof. Most authors never bother to do that. Still, he doesn’t really appear to understand
the way that it works – else he’d have have noticed the self-reference problem.
Back at the beginning of the post, I said he almost avoids the usual problem of ignoring the diagonalization. The catch is that, as we’ve seen above,
he got it wrong, because he didn’t remember to consider the key
property of the diagonalization: that it’s different from every row in the
table. By trying to construct a diagonal that is equal to a row in the table,
he’s doing something self-contradictory. But he ignores that property – and then when
doing something self-contradictory results in a contradiction, he tries to claim that
it shows that one of history’s most profound and important mathematical results is