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

original argument.

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

counterexample.

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

below.

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

it.