Was Cantor Wrong?

Are the real numbers countable?

Cantor’s diagonalization argument has always bothered me, and until recently I wasn’t able to put my finger on exactly why. I was reading this excellent crash course in the mathematics of infinite sets that was posted in Hacker News when I was finally able to verbalize why diagonalization seems fishy to me.

A countable set is always shown to be countable by construction, by providing a mapping between the natural numbers and the set. An uncountable set is always shown to be uncountable by contradiction, by first assuming that the set is countable and then showing that this assumption leads to a contradiction. The argument used to reach the contradiction is always diagonalization or something similar to it.

The diagonalization argument for the real numbers goes something like this:

Assume that the real numbers are countable, and let’s represent the real numbers between 0 and 1 as infinite binary strings 0.0110101.. etc. all real numbers between 0 and 1 can be represented like this. By assumption, all possible strings can be paired up with a natural number. But, the argument goes, we can construct a new string from all the other strings by taking one digit from each string and flipping it to its opposite. So to construct our new string we go through the set of all natural numbers, and we take the nth digit from the string associated with the natural number n and use its opposite in our new string. When we are done constructing it we know that the new string is different from the first one on the first bit, from the second one on the second bit, etc. Therefore the new string is different from all the strings that we constructed it from, so it could not have been one of the strings in the original set. This new string represents a new real number between 0 and 1 that was not in the set we used to generate it. Since we assumed that all strings representing all real numbers between 0 and 1 were already in the set, this leads to a contradiction, and the assumption that the real numbers is countable is false.

To illustrate my problem with this argument, let me apply it to a set we know to be countable, the positive even numbers. Using a similar argument I can “show” that the positive even numbers are not countable:

Assume the positive even numbers to be countable. Then by assumption all possible positive even numbers can be paired with a natural number. Let me construct a new positive even number as follows. Take the first positive even number, then add the second positive even number, then add the third positive even number, etc. My new number can’t be the nth positive even number because it was constructed by adding the nth number plus some other positive even numbers, so it is strictly larger than the the nth positive even number for all n. Since it can’t be any of the numbers we used to construct it, it was not in the set to begin with. Since it is a sum of positive even numbers it is positive and even, but we assumed that all positive even numbers were in the set. So this is a contradiction, and the assumption that the positive even numbers is countable is false.

So using a diagonalization-like argument, I was able to show that the positive even numbers is not a countable set, and this is clearly false since we can show this set is countable by construction, by taking the positive integers and multiplying each one of them by 2.

So where is the problem? Both the diagonalization argument for the real numbers and my argument for the positive even numbers have an unstated assumption. They assume that one can use every element in an infinite set to construct another element in the set. But in practice how could anybody or any algorithm use every single element of an infinite set? As soon as we have used what we thought were all the elements, we can always create another element, that is the essence of infinite sets, they never end. A Turing machine constructed to do this would never halt. This in itself is not proof that we can’t do that, but it should give us pause before assuming that we can.

To prove that we can’t actually do this, we could assume that we can and show that this assumption leads to a contradiction, but that is what I just did! I assumed that I could use every element of an infinite set to construct another element different from each of the elements in the set, and using that assumption I concluded that a countable set is an uncountable set, a contradiction. Therefore my assumption was wrong, and it proves that we can’t use every element of an infinite set to construct another element in the set. This implies that diagonalization is not valid, and we can’t use it to prove the reals are uncountable.

If diagonalization is not valid, does that mean that the reals are countable? Is there a proof that the reals are uncountable that does not rely on diagonalization or something like it? I haven’t seen any proof that doesn’t use a diagonalization-like argument, but maybe someone more knowledgeable in math can point me in the right direction.

Of course even if the proof that the reals are not countable were to be invalid, it doesn’t mean that the reals are countable. For that we would have to show by construction, by counting, that we can enumerate all the real numbers. Cantor was able to show that the rationals are countable by setting them in a grid. Once they are in a grid an integer can be assigned to each element of the grid. I can’t put the real numbers in a grid, but I can put them in a binary tree and assign one integer to each node of the tree:

To show the real numbers between 0 and 1 are countable, we can use the same representation of real numbers as in the diagonalization argument above. Each number between 0 and 1 can be represented as a binary string 0.01100… etc. Each one of these strings can also be represented as a path in an infinite binary tree. For example the number 0.101 would be represented by going down 1, then 0, and then 1 in the binary tree. We can enumerate the tree by traversing it breadth first, and assigning one natural number to each of its nodes as far down as we care to go. Any string of 0s and 1s can be represented in this tree. Since the tree is infinite we can represent any infinite string, even if the string was constructed through diagonalization there will always be a path in the tree for that string. Since we can enumerate the nodes of the tree, that means that we can assign a natural number to each real number. This shows that we can map the natural numbers to the real numbers and therefore the real numbers are countable.

A rigorous proof that the reals are countable using the argument above would have to be more careful and cross all the t’s dot all the is. For instance, it would have to say something about the fact that it doesn’t matter that some of the real numbers are repeated in the binary tree because that shows the cardinality of the reals is at most that of the integers, but knowing that the integers is a subset of the reals that’s enough to prove that they have the same cardinality.

I am interested on what people think of the argument in general, is this completely wrong? If so why? Please discuss in Hacker News.