Saturday, December 12, 2009

The Infinite Node Tree

I have to stop have dreaming about infinities, they keep waking me up at night ...

We can define an 'infinite node tree' as a tree similar to an N-ary tree, except that at each and every node, there are an infinite number of children.

Can this tree be traversed?

Yes, if we start at the first level, and create a set of all of the children at each level we get something like:

level1 = { c1, c2, .... }
level2 = { {c11, c12, ... }, {c21, c22, ...}, ... }
level3 = { {c111, c112, ...}, {c211, c211, ...}, ...}
...

In my previous post, I suggested that if we have several infinite sets we can combined them as follows:

If we have the set:

S = { { a1, b1, c1, ...}, {a2, b2, c2, ...}, ....}

Is there a injective and surjective mapping onto

{ a, b, c, d, ....}

Hypothesis: Yes

If we define a 'pass' to be taking the a finite number of elements from a finite set, then adding in a new set, we get an algorithm like:

N=1
sets = S{N}

forever
    for each set in sets
        get next element in current set
    sets += S{N}

So we traverse the above as follows:

a1,   b1, a2,    c1, b2, a3,   d1, c2, b3, a4,   ...

We can see that eventually we will get through all elements of S.

Then:

a = a1, b = b1, c = a2, d = c1, e = b2, f = a3, ....

Thus there appears to be a simple mapping between a single infinite set and an infinite set of infinite sets.

Now we can do that for our infinite node tree, by adding in each new set, one at a time, for each new level. (two iterators, instead of one).

So for each iteration, we add in the next set of each new level (one at a time) and then add in the next elements of each new set in the list of sets. Something like:

N=1
M=1
sets = S{N}
levels = L{M}

forever
    for each level in levels
        for each set in sets
            get next element in current set
        sets += S{N++}
    levels += L{M++}

(or something similar, it's late :-)

So eventually, slowly, we will eventually traverse all of the elements in the tree exactly once (as we approach infinity).

So what can we do with this infinite node tree?

To make it simpler, we can remove all of the finite elements out of R, and replace them with infinite representation, so for instance:

1 = 1.0000000...
4 = 4.0000000...

NOTE: I'm not sure if this is really necessary, but it does mean that I am left with a consistent set of  infinite representations for all of the possible numbers in R. I'd rather only deal with only one type of number, like Pi or sqrt(2).

Now if we consider that between any two numbers in R, there lies an infinite number of other numbers such that as a set they look like:

{ ..., A, ..., B, ... }

Then starting somewhere arbitrarily like 0, we can build an infinite node tree containing all of the numbers in R.

UPDATE2: To clarify, each real is contained in its own node in the tree. That is, there is a node for Pi and a node for sqrt(2), as well as nodes for all of the other numbers (rational and irrational).

Another, perhaps easier way to look at it is to add in all of the known numbers in R to a level in the tree (like in Cantor's first set of the diagonalization argument). Between each of these number is an infinite number of children, and beneath all of them is still more infinite numbers of child, etc. As we find more, we can add them to the lower levels (so we can use Cantor's construction as the way to build the tree itself).

Either way, I think the entire structure of R fits into the structure of the infinite node tree.

UPDATE: I just woke up and realized that I am slightly wrong here. The child and the parent are right next to each other. To fix this, we actually need a binary infinite node tree, that is a tree where there are two infinite sets of children, the left set and the right set. Fortunately,  having this extra set at each node doesn't significant change how we traverse the tree (instead of adding the next child, we add in the next one from the left and the next one from the right.). Now between any and every parent and child is an infinite number of other children.

AND this tree is traversable.

Thus, in iterating through the tree as we visit each node we can assign a number in N. This appears to form an injective and surjective mapping between N and R.

"You can't refute Cantor's proof using an enumeration without addressing Cantor's proof." -  Mark C. Chu-Carroll

In the first part of Cantor's diagonalization argument, we construct a list of all of the elements from the mapping.

That's the first problem. The structure is actually a tree of infinite breadth and infinite depth, and in this case one that is not easily expressible as a simple list.

The second part of Cantor's construction is to create an element from the diagonal. As we start this, we descend down one branch of the tree, but as the tree is infinite in length, we can't ever get to the bottom, so we can't go to the next branch.

What I believe this means (although it is late), is that we can't construct the element. Ever.

So we can't construct an element that isn't already included in our tree. I take this to mean either we can't apply this construction method OR it definitely shows that all elements are now contained in the tree. Either way it doesn't invalidate the mapping.

OK, that's enough, it's late and I need my beauty sleep.

UPDATE2: I thought of another interesting bit. If we see Cantor's diagonalization construction as a number generator, since it will generate an infinite amount of numbers, then we can use it as the means to count. That is, if we seed it with some finte list of initial values, assigning them all a number. Then at each interation, a new unique number will be generation. Since this goes on for infinity, it will create an infinitly large set of countable numbers. However, the question is, what if there are gaps? Someone could prove that as the list approaches infnity, the gaps decrease in size, but another way of dealing with it is to use two of these generators at each node in the binary infinite node tree. Then we can parallelize all of them at once, and construct a tree, that eventually won't have an gaps at any level (I think). That's an interesting way to create the tree.

UPDATE3: There are a couple of problems with the my above arguments, that I was thinking about today.

The first is that I keep falling back to the calculus notion of infinity, instead of the set theory one. That is, I am relying on "generating" the tree, not just having it created (all at once). I keep trying to sneak up on infinity, and it keeps running away and hiding.

The second is that my tree construction is vague. I can fix both problems at once.

First we'll start with: if there are any trees that will satisfy the bijection, there are an infinite number of them.

I can envision a number of ways to create these trees, but I realized the simplest way was there all along. The tree can be constructed by using Dedekind cuts. That is, each and every cut is actually a node in the tree, with the two sets on either side of it as the left and right child sets. It's a very natural extension of the cuts into an (infinite) tree structure.

Since the cuts resolve the differences between rationals and irrationals, I'm assuming that we can cut down to an infinite number in both the left and right sets, thus getting to every point on the R number line, which is more or less what Wikipedia says the cuts accomplish. Well it seems to say that it applies to the irrational real numbers, but I think that it works for both (or at least for my altered reals where I made everything infinite in length).

Then the tree created in that manner is assured of getting to every member of R. There are no duplicates, and there are no gaps. And the whole structure can be created as a set in one shot.

An issue that might bug some people is that I am using the term 'tree' when I believe there is no such thing in ZFC set theory. That's OK because in a level by level manner, sets can nicely express trees. Thus using the term tree in this context is a convenience to make the whole idea easier to understand, not a necessity.

However, the real meat of this idea is how the structure of the tree itself is used to get around Cantor's diagonalization. If we can't create the element, then it can't be missing. But we can't create it because we get lost down one branch of the tree. I don't get into the trap of having to create the element all at once precisely because Cantor's argument is based on 'constructing' the element, not just having it exist in a completed form. Where I was playing fast and loose before, with time, in this case I believe that I am allowed to rely on it (existing).

(Also, I thought about a bunch of other construction techniques, and also whether or not the tree can have duplicates (or be a DAG instead of a tree), and whether the tree actually needs to be ordered (which I was actually assuming all along, but forgot to mention). But I realized that the Dedekind cut construction was by far the cleanest and that it has already been established as being correct (although not necessarily my usage of it)).