How Diagonalization Fails

In his work on basic set theory, Georg Cantor claimed to have discovered infinities greater than what we normally think of as infinity. He claimed that the infinity of the decimal fractions (which infinity he called Aleph One) is greater than the infinity of the natural numbers (Aleph Null). He proved and apparently verified that claim by using what mathematicians call his diagonalization process.

Diagonalization starts with Cantor inviting us to imagine listing all of the natural numbers (positive integers) and then putting a different decimal fraction next to each natural number. We feign asserting that we have used up all of the decimal fractions and that the two lists contain the same number of elements, even though they form infinite sets. Then we show that there exist decimal fractions that we did not put on the list. We can produce each of those left-off fractions by following a diagonal path down the list in order to contrive the new fraction: take the first digit of the first fraction on the list, change it, and make it the first digit of the new fraction; take the second digit of the second fraction on the list, change it, and make it the second digit of the new fraction; and so continue on. The new fraction is thus guaranteed to differ from every fraction on the original list in at least one decimal place. We see, then, that the new fraction (and we can generate them endlessly) did not exist on the original list, so our new list of decimal fractions must extend beyond the list of the natural numbers. Or so Cantor told us.

Now we need to explicate one of our tacit assumptions. In our place-notation depiction of numbers we tacitly understand that the number of places to the right of the decimal point constitutes an infinite set. If we were to write out the decimal version of one quarter, for example, we would have an infinite string of zeroes extending to the right of the five. A similar comment applies to the left side of the decimal point: an infinite set of zeroes extends to the left of each and every natural number.

That last fact enables us to apply diagonalization to the natural numbers, so we can extend our original list of natural numbers in the same way that we extended our list of decimal fractions. So now we can’t use diagonalization to tell which list is longer than the other; we can’t determine whether the set of the natural numbers has more or fewer elements than does the set of the decimal factions. However, we do actually have a process that enables us to make that determination – the process of reflection.

We apply that process by reflecting a decimal fraction, such as, for example, 0.866, through the decimal point. We get 668, which is a natural number. That pairing, of 0.866 with 668, is perfectly unique and it gives us a one-to-one relationship between a natural number and a decimal fraction. If we use that process, there is no natural number that we cannot uniquely associate with a decimal fraction and there is no decimal fraction that we cannot uniquely pair with a natural number. Those two facts oblige us to infer that the two sets contain exactly the same number of elements, so the infinity of the decimal fractions is the same as the infinity of the natural numbers.

Perhaps there’s another way to get a bigger infinity? What can we say about infinity squared? In this case we want to compare the set of the real numbers with the set of the natural numbers. A real number consists of a natural number associated with a decimal fraction. Each and every natural number can be associated, one element at a time, with the full set of the decimal fractions, so to calculate the size of the set of the real numbers we multiply together the sizes of the set of the natural numbers and the set of the decimal fractions – infinity squared. Surely, we think, that product must be bigger than the infinity of the natural numbers.

We can test that proposition easily enough. Again we apply the reflection process to produce a unique one-to-one matching between the real numbers and the natural numbers, unconsciously expecting to have real numbers left over. In this case, if we reflect the decimal part, we interleave the digits of the fraction among the digits of the integer. For example, depending on whether we put the fraction’s digits in the odd-numbered places or the even-numbered places to the left of the decimal point, we would transform 271.829 into either 297218 or 922781. There is no real number to which we cannot apply that process and get a perfectly unique natural number, so if we apply that rule consistently, then we obtain a perfect one-to-one matching between the set of the natural numbers and the set of the real numbers. Infinity squared equals infinity.

Reversing that reflection-interleaving process converts any natural number into a real number. There is no natural number to which we cannot apply that reverse process and, as noted, there is no real number to which we cannot apply the original process. Thus, we prove and verify the statement that we have a perfect, unique, one-to-one matching between the set of the natural numbers and the set of the real numbers. The infinity of the real numbers, then, is exactly the infinity of the natural numbers.

So how did Cantor go wrong? How did he fail to see the invalidity of the diagonalization argument?

Look again at our place-value notation. When we write down a decimal fraction we understand, tacitly perhaps, that an infinite string of zeroes extends to the right of the last non-zero digit. Those zeroes mark places where non-zero digits could appear, as in, say, the decimal representation of one third. We are not so aware of the implicit zeroes that extend to the left of the first non-zero digit of a natural number. In our minds those places don’t exist, ready to be filled. Thus, Cantor could see easily that he could use diagonalization to extend the set of the decimal fractions indefinitely, but he missed seeing that he could do the same thing with the set of the natural numbers.

Another factor refers to the Sapir-Whorf hypothesis of linguistics, the proposition that words shape our concepts of whatever reality we face. When people speak of Cantor’s Alephs they say bigger than or greater than, thereby placing the Alephs into a conceptual hierarchy. We already think of numbers as conforming to a hierarchy and we conceive infinity as a kind of number, so we conceive nothing inherently wrong with a hierarchy of multiple infinities. But suppose that someone had worded the comparison as infinities more infinite than infinity (or endlessnesses more endless than endlessness)? That expression gives us a clear absurdity and it might have inspired mathematicians to take a closer look at the diagonalization procedure with the intent of seeing how it might be misleading them. Someone almost certainly would have discovered the reflection process prior to 2003, when I discovered it.

As we extend our thoughts into the more aetherial realms of conception, we must take care to keep our logic well refined. Clarifying our descriptions of things takes a long first step toward fitting them into a proper logical pattern.

habg