Skip to main content

Cantor's diagonalization argument

Kurt gödel.jpg

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.

Comments

Popular posts from this blog

Hume's Cutlery

David Hume is renowned for two pieces of cutlery, the guillotine and the fork.

Hume's guillotine is the sharp cut he makes between "is" statements and "ought" statements, to make the point that the former never ground the latter.

His "fork" is the division between what later came to be called "analytic" and "synthetic" statements, with the ominous observation that any books containing statements that cannot be assigned to one or the other prong should be burnt.

Actually, I should acknowledge that there is some dispute as to how well or poorly the dichotomy Hume outlines really maps onto the analytic/synthetic dichotomy. Some writers maintain that Hume meant something quite different and has been hijacked. Personally, I've never seen the alleged difference however hard they've worked to point it out to me.

The guillotine makes for a more dramatic graphic than a mere fork, hence the bit of clip art above.

I'm curious whe…

A Story About Coleridge

This is a quote from a memoir by Dorothy Wordsworth, reflecting on a trip she took with two famous poets, her brother, William Wordsworth, and their similarly gifted companion, Samuel Taylor Coleridge.



We sat upon a bench, placed for the sake of one of these views, whence we looked down upon the waterfall, and over the open country ... A lady and gentleman, more expeditious tourists than ourselves, came to the spot; they left us at the seat, and we found them again at another station above the Falls. Coleridge, who is always good-natured enough to enter into conversation with anybody whom he meets in his way, began to talk with the gentleman, who observed that it was a majestic waterfall. Coleridge was delighted with the accuracy of the epithet, particularly as he had been settling in his own mind the precise meaning of the words grand, majestic, sublime, etc., and had discussed the subject with William at some length the day before. “Yes, sir,” says Coleridge, “it is a majestic wate…