I’ve been getting lots of mail from readers about a
href="http://knol.google.com/k/are-real-numbers-uncountable#">new article on Google’s Knol about
Cantor’s diagonalization. I actually wrote about the authors argument href="http://scienceblogs.com/goodmath/2009/01/the_continuum_hypothesis_solve.php">once
before about a year ago.
But the Knol article gives it a sort of new prominence, and since
we’ve recently had one long argument about Cantor cranks, I think it’s
worth another glance.
It’s pretty much another one of those cranky arguments where they say “Look! I found a 1:1 mapping between the natural and the reals! Cantor was a fool!”
As I’ve said before, one of the things that constantly comes
up in crackpot arguments is a kind of profound ignorance, where
they claim to refute an argument by showing a “counterexample”
which isn’t a counterexample, and never actually addresses the
The Cantor cranks are the canonical example of this. Cantor’s
argument is a classic proof by contradiction. It wants to prove
that there is no possible one-to-one mapping between the
natural numbers and the real numbers. So what it does is show that
given any mapping, you can create a real number which
is not included in the mapping. Therefore it isn’t a one-to-one
mapping between the naturals and the reals, because it omits
at least one real number.
To reiterate the important part: for any mapping, it produces a
The vast majority of Cantor cranks claim to refute Cantor by showing
what they believe to be a one-to-one mapping between the naturals
and the reals. But they don’t address Cantor’s proof at all: they just
claim that they found a perfect mapping, and that therefore Cantor’s
proof is wrong. But if you take the diagonalization from Cantor’s proof,
and apply it to their mapping? Boom. It produces a counterexample.
Cantor’s proof is a constructive proof. It works for all
mappings to produce a concrete counterexample. You can’t just say
“look, I found a mapping!”, and expect to be taken seriously. You can’t
just rant about how Cantor was an idiot, or about how wonderful your
mapping is. You need to address why Cantor’s proof won’t work
for your mapping.
The knol article is a perfect example of this. Once you strip out all of
the “Cantor was an idiot”, “Cantor was a moron”, and similar stuff, what’s
left is supposedly a complete enumeration of the reals. Since Cantor says you
can’t do that, therefore Cantor must be wrong. But the enumeration
is subject to attack by the diagonalization argument in Cantors
proof, and the author never bothers to address that – he’d rather just
keep shouting “It’s obvious! Cantor was an idiot!”.
His enumeration is based on trees. You can create an infinite tree of the
decimal representation of the numbers between zero and one. You start with at
the decimal point – exactly 0, which is the first number in the enumeration.
Then as children of zero, you put 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – representing
0.0, 0.1, 0.2, etc. Then as the children of each of those, you again put 0
through 9. Taken to infinity, this produces a tree containing every single
possible decimal representation of a real number between zero and one.
Therefore Cantor was wrong. The basic construction of this tree is illustrated
Except for one minor, trivial problem. Considered as an enumeration or as
a mapping from natural numbers to real numbers, the tree doesn’t even contain
all of the rational numbers, much less the irrationals. As an
enumeration, it will never produce the value 1/3, or 1/7th. It well never
produce π or e.
The catch – and it’s a huge catch – is that the tree defines a
representation, not an enumeration or mapping. As a representation,
taken to infinity, it includes every possible real number. But that doesn’t
mean that there’s a one-to-one correspondence between the natural numbers and
the real numbers. There’s no one-to-one correspondence between the natural
numbers and the nodes of this infinite tree. It doesn’t escape Cantor’s
diagonalization. It just replaces “real number” with “node of this infinite
tree”. The infinite tree contains uncountably many values – there’s a
one-to-one correspondence between nodes of the infi
To see the distinction, let’s look at it as an enumeration. In an enumeration
of a set, there will be some finite point in time at which any member
of the set will be emitted by the enumeration. So when will you get to 1/3rd,
which has no finite representation as a base-10 decimal? When will you get to
If you start at the root, and enumerate by climbing down the tree breadth
first, you’ll never get to anything with an infinite decimal representation.
If you try to do depth-first, you’ll never enumerate anything. Any
traversal of the tree, any attempt to actually enumerate the
values will run into exactly the same problem as you’d have enumerating
the reals. The tree solves nothing: you can just re-formulate
Cantor’s diagonalization to show that any attempt to
produce an enumeration or one-to-one mapping between the natural
numbers and nodes of the tree will miss nodes.
You can’t refute Cantor’s proof using an enumeration
without addressing Cantor’s proof. This is just yet another
stupid attempt to refute Cantor without bothering to actually understand