Of all of the work in the history of mathematics, nothing seems to attract so much controversy, or even outright hatred as Cantor's diagonalization. The idea of comparing the sizes of different infinities - and worse, of actually concluding that there are different infinities, where some infinities are larger than others - drives some people absolutely crazy. As a result, countless people bothered by this have tried to come up with all sorts of arguments about why Cantor was wrong, and there's only one infinity.
Today's post is another example of that. This one is sort of special. Unless I'm very much mistaken, the author of this sent me his argument by email last year, and I actually exchanged several messages with him, before he concluded, roughly "We'll just have to agree to disagree." (I didn't keep the email, so I'm not certain, but it's exactly the same argument, and the authors name is vaguely familiar. If I'm wrong, I apologize.)
Anyway, this author actually went ahead and wrote the argument up as a full technical paper, and submitted it to arXiv, where you can download it in all it's glory. I'll be honest, and admit that I'm a little bit impressed by this. The proof is still completely wrong, and the arguments that surround it range from wrong to, well, not even wrong. But at least the author has the Chutzpah to treat his work seriously, and submit it to a place where it can actually be reviewed, instead of ranting about conspiracies.
For those who aren't familiar with the work of Cantor, you can read my article on it here. A short summary is that Cantor invented set theory, and then used it to study the construction of finite and infinite sets, and their relationships with numbers. One of the very surprising conclusions was that you can compare the size of infinite sets: two sets have the same size if there's a way to create a one-to-one mapping between their members. An infinite set A is larger than another infinite set B if every possible mapping from members of B to members of A will exclude at least one member of A. Using that idea, Cantor showed that if you try to create a mapping from the integers to the real numbers, for any possible mapping, you can generate a real number that isn't included in that mapping - and therefore, the set of reals is larger than the set of integers, even though both are infinite.
This really bothers people, including our intrepid author. In his introduction, he gives his motivation:
Cantor's theory mentioned in fact that there were several dimensions for infinity. This, however, is questionable. Infinity can be thought as an absolute concept and there should not exist several dimensions for the infinite.
Philosophically, the idea of multiple infinities is uncomfortable. Our intuitive notion of infinity is of an absolute, transcendent concept, and the idea of being able to differentiate - or worse, to be able to compare the sizes of different infinities seems wrong.
Of course, what seems wrong isn't necessarily wrong. It seems wrong that the mass of something can change depending on how fast it's moving. It seems even more wrong that looked at from different viewpoints, the same object can have different masses. But that doesn't change the fact that it's true. Reality - and even worse, abstract mathematics - isn't constrained by what makes us comfortable.
Back to the paper. In the very next sentence, he goes completely off the rails.
As a matter of fact, if the set N is an infinite set it should be of same power as the set R. This has not been proven so far. We knew by several arguments, and in particular by the argument of Cantor's diagonal, that the set R and N do not have the same cardinality and that there is no bijection between these two sets. In this paper, I show that there is a bijection between the set of integers and the set of real numbers. I show that the set R is countable and that there is only one dimension for infinite sets, ℵ.
(In this quote, N and R are the set of natural numbers, and the set of real numbers, respectively.) "This has not been proven so far" is a classic line. In fact, not only has in "not been proven so far", it's been disproven, as he admits in the next sentence. So, he goes on to say that Cantor proved that there is no possible bijection (total, onto, one-to-one mapping) between the natural numbers and the reals; and that he's going to show us one.
If someone wanted to show that one of the most well-known, respected, widely analyzed and accepted proofs in all of mathematics is wrong, you'd think that they'd show just why the proof is wrong. In particular, Cantor's proof shows you that given any purported mapping between the integers and the reals, you can create a member of the reals that isn't included in the mapping. It doesn't show you that for one particular mapping; it shows a procedure that can defeat any possible mapping. So you'd think that the author of the paper would show why Cantor's proof wouldn't apply to his proposed mapping. But he doesn't. He just ignores Cantor's proof, because his mapping is, apparently, so obviously correct that it doesn't need to address Cantor.
So what's his argument?
Basically that he can construct a mapping based on trees. He starts by defining a tree over the set of all possible natural numbers (he says "integers", but his construction doesn't include negatives.) The basic structure is what we CS people call a Trie. The root of the tree is "0". "0" has ten children: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09. Each of those has ten children. And so on, forever.
In this tree, every possible number is associated with one node of the tree. For any possible number n in N, there is exactly one path in the tree that leads to n. What he neglects to notice is that for any possible member n of N, the path from the root of the tree to n is finite.
The set of finite length paths in this number-trie corresponds exactly with the set of natural numbers - it's a perfect bijection between nodes of the tree, and members of N.
Next, he goes on to show that the cardinality of N is supposedly equal to 10ℵ0. The argument really doesn't make a lot of sense:
Proof :Each integer is a node of the tree. The set of the nodes in the tree is bijective with the set of integers. When N is large, counting the number of nodes is the same as counting the number of paths (to infinity) in the tree. The cardinality of the set of the nodes of this infinite tree is 10 ℵ0 counted 9 times. Indeed, we see in Figures 1 and 2 that the set N is of cardinality (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) N counted 9 times. This implies that the cardinality of the set N is 10ℵ0 As ℵ0 represents the cardinal of N, which is by definition the cardinal of the set of the nodes in the tree (bijective with N), we get 10ℵ0 = ℵ0. Note already that this implies that 2ℵ0. This proposition shows that the cardinality of N, ℵ0 , is equal to 10ℵ0. In the next proposition, I compute the cardinality of the powerset of N.
The nonsensical part (or rather, the most obvious nonsensical part) is that he talks about "When N is large", even though N is the set of all integers... The set of all integers doesn't get large.
The basic error, though, is the same as above: he's got an enumeration of all finite length paths. Everything that he says is talking about the set of finite-length paths. Because natural numbers are all finite-length. An infinite-length string of digits isn't a natural number, or an integer. And so everything else in that "proof" breaks down.
You can probably guess where he's going next.
For the real numbers, he also constructs a tree. It's sufficient to show that there is a bijective mapping between the set of real numbers between 0 and 1 and the set of natural numbers - because the size of the set of reals between 0 and 1 is the same as the size of the set of all positive reals, and the set of all positive reals is the same size as the set of all reals.
So, he constructs another tree. This time, instead of the tree starting with "01", "02", "03", ..., it starts with "0.1", "0.2", "0.3", ... . This tree will, he asserts, eventually include all possible real numbers. There's obviously a bijection between the nodes of this tree, and the nodes of the integer tree - and therefore, a bijection between the integers and the reals.
The key question to seeing the error here is to ask: what's the member of the natural numbers tree that corresponds to π?
And the answer is: there isn't one.
The integers are all, necessarily, represented by finite length paths in the tree. But π isn't finite-length. Any natural number from the natural numbers tree will correspond to a finite prefix of π, but no integer will ever correspond to π. In fact, you can only ever see the node representing the value of π after you've build ω levels to the tree - that is, after you've built a tree whose depth is the same as the cardinality of the set of integers, and you're on the step after that - that is, you're on the ω+1th step of tree construction. But if you're on the ω+1th step, then you've got an infinity which is strictly larger than ω!
After that, he uses it to show that there's only one infinity, and that's it! He's done! Not a mention of Cantor's diagonalization, or why his construction is immune to it. Even if the finite/infinite length path issue wasn't so glaringly obvious, the fact remains that Cantor's diagonalization shows how to produce a counterexample to any possible mapping from the naturals to the reals. If Cantor's proof is correct, then even if he showed a compelling looking construction, it wouldn't matter - because without showing an error in Cantor's proof, without showing how his construction escapes from Cantor's trap, the diagonalization shows that his construction is invalid. But he never addresses that at all. He just pretends that it's not there, that there's no problem.
And so, we're forced to conclude, we're looking at just another crackpot who's convinced that he must be right, because it's obvious that there can't be anything larger than infinity.