Supertasks: Revisiting Cantor’s Diagonal

Aleph Nought symbolI have been studying a lot of theoretical stuff lately, which is generally not good for my well-being (I keep remembering the famous Brazilian children stories of the Picapau Amarelo, whose erudite and science-loving Viscount of Corncob once almost dies from an ‘algebra congestion’).

As I browse through more and more advanced material, the small inconsistences accumulate and the whole building starts  showing dangerous crevices. For example: as the emphasis progresses towards solid contructive concepts like computability and decidability, why do we continue to put up with explosive can of worms like supertasks, cardinals, diagonalization and the axiom of choice ?

Take that famous proof of the existence of uncountable infinite sets, by Cantor, the (in)famous diagonal argument (I will be quoting heavily from that Wikipedia article). I love that proof, and I remember how wonderful I found it when I saw it for the first time. But the more I think about it, the less watertight it starts to look.

Basically it ask us to put all the infinite binary sequences in one-to-one correspondence to the natural numbers, like below, and invites us to build another sequence D, by taking the ith bit of the ith sequence (in boldface) and negating it:

s0 = (0, 0, 0, 0, 0, 0, 0, …)
s1 = (1, 1, 1, 1, 1, 1, 1, …)
s2 = (0, 1, 0, 1, 0, 1, 0, …)
s3 = (1, 0, 1, 0, 1, 0, 1, …)
s4 = (1, 1, 0, 1, 0, 1, 1, …)
s5 = (0, 0, 1, 1, 0, 1, 1, …)
s6 = (1, 0, 0, 0, 1, 0, 0, …)
(…)
D  = (1, 0, 1, 1, 1, 0, 1, …)

As it goes, the arguments says, D clearly is not in the list, which pretended to contain all sequences. So there can be no such list, and therefore no bijection between the sequences and the natural numbers. Consequently, the set of those sequences in uncountable. QED. *applause*

But, of course, I am not so happy, otherwise I would be seeping my tea and watching reruns of ‘Sex and the city’ instead of puzzling over established 19th century math. The crux of my insatisfaction is that the proof is not “computationally effective”, because building D is a supertask.

Here’s a troubling though experiment. Take the same list above, and now sort it in reverse-lexicographic order (with 0 before 1). Now, we have obviously:

s0 = (0, 0, 0, 0, 0, 0, 0, …)
s1 = (1, 0, 0, 0, 0, 0, 0, …)
s2 = (0, 1, 0, 0, 0, 0, 0, …)
s3 = (1, 1, 0, 0, 0, 0, 0, …)
s4 = (0, 0, 1, 0, 0, 0, 0, …)
s5 = (1, 0, 1, 0, 0, 0, 0, …)
s6 = (0, 1, 1, 0, 0, 0, 0, …)

Now, given any “recipe” for a sequence and using the hierarchy of ordinals, you should be able to tell me the position of the sequence in the list. For exemple, all sequences whose last 1 occurs at a finite position correspond to very predictable finite ordinals. The trouble (for me) starts with the less well-behaved sequences. Which ordinal, for example corresponds to 01010101…01… ? And which corresponds to 10101010…01… ? Those are sequences with very simple “recipes”, finding them shouldn’t be so troublesome.

Now for an even more disquieting idea: the last sequence in this list will be, by construction:

ssomething = (1, 1, 1, 1, 1, 1, 1, …)

But which ordinal is something?

Now, a handful of paradoxes isn’t what one gets when playing with infinites without defining the limiting proccesses ? At least that is what E. T. Jaynes keeps telling me…

* * *

The problem, as I see it, admittedly extremely naïvely (to the point of deserving three consecutive adverbs), is that the theory of ordinals lets you always express the first infinite thing you don’t have, but never the last infinite thing you have.

Imagine I had a handle for the “last” infinite natural number — let’s be creative and call it ∞. It would have to correspond to the position of the “last” bit in my sequences (because each sequence has countably many bits, numbered 1, 2, 3…). Observing that the first sequence to have a 1 in the ith position is sequence # 2i-1, I would know, for example that x of the sequence…

sx = (0, 0, 0, 0, 0, 0, 0, … ) ( 1 ] at ∞

…could be no other than x = 2∞-1. And as for my something above, it would be simply 2-1. Now, that starts to look like uncountably many !

Isn’t a notation like…

sy = (1, 0, 1, 0, 1, 0, 1, … ) ( 0, 1 ] at ∞
sz = (1, 0, 1, 0, 1, 0, 1, … ) ( 1, 0 ] at ∞

…just a fancy way of grasping limiting behaviors at infinity and thus avoiding Jaynes’ dreaded paradoxes ? With the specifications above, y and z are clearly defined. Without them, they are irretrievably lost.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s