Wednesday, December 16, 2009

The Magic Sequence

This post is a continuation of both my discussions at:

http://scienceblogs.com/goodmath/2009/12/another_cantor_crank_represent.php

and at:

http://theprogrammersparadox.blogspot.com/2009/12/infinite-node-tree.html

To understand what I am saying you have to get through all of my comments (and other responses) at Mark's site, my post and all of the comments for my post. I know. It's a lot of stuff, and currently it is badly organized.

This post will clear up the discussion at Good Math, Bad Math about Cantor's Diagonalization Argument, and later today I'll add another one which will (hopefully) show that R -> N.


Consider the following sequence of real numbers:

0.100000000...
0.110000000...
0.111000000...
...
0.010000000...
0.011000000...
0.011100000...
...
...

Please note the second terminating ellipsis (...), it is not a typo. The first two ellipsis' are symbolic notation to explain how to extend the two existing sub-sequences of numbers. The third one in this case means that we extend the infinite sequences themselves.

Now, this structure and this notation will provoke two questions:

Can't you enumerate this sequence and re-write is as such?
Is this syntax even legal?

I'd like to answer both of these questions together. Starting with another example:

1  | [2]. 1 0 0 0 0 0 0 0 0 ...
2  |  0 . 1 1 0 0 0 0 0 0 0 ...
4  |  0 . 1 1 1 0 0 0 0 0 0 ...
...
3  |  0 .[2]1 0 0 0 0 0 0 0 ...
5  |  0 . 0 1 1 0 0 0 0 0 0 ...
8  |  0 . 0 1 1 1 0 0 0 0 0 ...
...
6  |  0 . 0[2]1 0 0 0 0 0 0 ...
9  |  0 . 0 0 1 1 0 0 0 0 0 ...
13 |  0 . 0 0 1 1 1 0 0 0 0 ...
...
...

In this example, on the left I have added a unique number from N to each row, using a method of counting where I gradually add in each new infinite sub-sequence, one-by-one and extend the count to include them. This structure is countable.

On the right I have attempted to apply Cantor's Diagonalization, but because there are an infinite number of sub-sequences, I can go forward to each, but I can never get back. The structure can NOT be diagonalized.

So we can clear up the first problem I keep hearing. The above example shows explicitly that:

countable != diagonalizable.

Now the really interesting bit, the coolest part of all of this, is the enumeration on the left-hand side. It is clearly enumerable, so we can write it out as a list of elements, but I won't dare! Why?

Because once I start writing out the elements I can never quit! That is, if at any point in the writing I stop and finish with ..., then that list (the one that I've written) is no longer the same as the one above.

Yes, it's an enumerable list, but No it cannot be written out as a finite list of elements. The ellipsis is not strong enough to describe it. We need a symbol more like [...|...] which would clearly show that the list was going off to "two" infinities at exactly the same time, not just one. (although it won't explain how to construct the missing elements).

Grasping for a name, I decided that "magic sequence" adequacy reflects the fact that it is a valid countable sequence that we can write, but if and only if we never stop writing it!

Is this really part of set theory? Yes, absolutely. The magic sequence is a simple sequence that can be counted. The alternative double ellipsis syntax may or may not be acceptable, but even if it isn't it is just a convenience for being able to write down (in a finite state) a magic sequence.

Again, it is a simple countable sequence that is unwritable as such. The multiple ellipsis is the only syntactic way we have of describing this mathematical object. How can this happen?

If we have:

- an infinite number of infinite elements.

everybody can agree that this is both countable and diagonlizable. But if we have:

- an infinite number of an infinite number of infinite elements

then it can't be diagonalized, the second infinity clearly gums up the works. But if we group it as:

- [ an infinite number of an infinite number ] of infinite elements

The first part of this is countable, and the entire thing is a magic sequence of infinite elements. So we can count it, and use it as a sequence.

Cantor's diagonalization argument starts with a sequence. If I supply it with a magic sequence, it becomes invalid. It cannot say one way or the other that there are missing elements.

This is a very deep and wide hole.

What's really interesting though, is that if R can be counted, then the only way it can be counted is with a magic sequence. A regular infinite sequence will ALWAYS fail the diagonalization argument. There is no question about this. The diagonalization argument was originally constructed to ensure this.


So, if you've not been following my last post (and all of the comments at both sites), I will summarize the current state of my argument.

I have:

a) a mathematical object (binary infinite node tree), that I think is expressible enough to contain the reals (R). This object fits in set theory.

b) a mapping of R onto this structure (for which there are known problems, this mapping is invalid!).

c) another mathematical object (magic sequence).

d) a simple example that shows that a magic sequence is countable, but not diagonalizable, thus Cantor can't be applied to a magic sequence.

e) a way of traversing the structure in a, to generate a magic sequence.


At this moment, the only real hole I have in my argument comes from the irrationals. In the instance of the tree I created in the comments (the 22nd one I think, but there are no numbers), I put ALL of them in the 2nd level, cut into two sets. That clearly doesn't work.

If we start enumerating the tree, starting at root, the first item is Pi, and the second item is the first element of the set of irrationals over the range [0,Pi).

Unfortunately, there is no first element until we get to infinity, but we're not allowed to get there.

Still although that particular mapping doesn't work, after a bit of thinking, I believe I have one that does. But, that will have to wait for another post this evening, since I have to get back to work now ...

Sorry to leave you all hanging :-)