Cantor's diagonalization argument

Yesterday's post as gotten me into one of my rare stern-logician frames of mind, so I think I'll stick with that today.

I wonder if I've ever discussed Cantor's "diagonal" proof in my blogging. If not, I'll make good on that now. Cantor refuted the common idea that "infinity" is a single all-inclusive category. Once we get beyond enumeration we've gotten to "infinity" and there is nothing more to be said. Or, at least, so we're inclined to think.

Yes there is, though, Cantor replies, much more to be said. Because for example not every infinity is equal to every other. Some "trans-finite" numbers are bigger than others. The number of real numbers is a larger transfinite number than the number of integers.

Why? Well, diagonals! The question is -- could we in principle create a one-to-one correspondence between every real number and every integer that would allow room for every one of each to show up, eventually, corresponding to the other? No answer is "no," because a skeptic about the value of our correspondence could always use a diagonal technique to prove its incompleteness.

So our effort at demonstrating correspondence may include this:

1 ~ 0.1254364
2 ~ 0.1254372
3 ~ 0.1297478
4 ~ 0.1597523
5 ~ 0.2145678
6 ~ 0.2732589
7 ~ 0.3001233
8 ~ 0.3112589


-----------------------
 Now obviously there is an arbitrary seeming starting point and there are gaps in the list of reals numbers and there are no gaps in the list on the left hand side of the page of the list of integers. That will always be the case. BUT we might suppose that our theorist claims he has a system that will allow the ordering to double back (and triple back ...) and fill in all those gaps in the fullness of time as the infinite scroll unrolls.

The skeptic will reply, "no you don't either." because  we can always look at the list diagonally and create a number in which the Nth digit of our new number is different from the corresponding Nth digit of the Nth number on the list.

Looking at the above list diagonally as indicated by the bold facing gives us this: 0.1295539. So in the corresponding number we construct, the first digit would be any digit OTHER THAN 0. The second digit would be anything OTHER THAN 1, the third digit OTHER THAN 2 and so forth. We could end up with this

0.2308794.

Which, you'll notice, is not on the list. The point is that however long the list is, and whatever method is used to create it, it will always be possible to defeat the real or alleged system by creating, through such a diagonalization, a number that differs from each digit of the official list in at least one spot, the Nth spot, defined by that official digit's place in the ordering.

For a much better explanation, get George Gamow's book, One, Two, Three ... Infinity, and turn to page 20.

Why should we care that there are trans-finite numbers of different values? Because this diagonal proof has proven fruitful, indeed foundational in a lot of subsequent developments, including the "Turing Halting Problem" in computer science, and the Gödel Incompleteness Theorem showing the limits of formal logic itself.                             

As a convenient parting thought, let's remember that one of the most important places in the magical world of Harry Potter, the street with all the shops where he buys magic books and wands and such school supplies, is called "Diagon Alley," which is pronounced a lot like "diagonally." A magical place, indeed!

That's Kurt Gödel above, though his glasses look a bit like Harry's.