Wednesday, December 30, 2009

A Very Large Structure

You'd think I'd learn. You really would.

I've posted a number of entries about issues with ZFC set theory, all of which, through the patient help of a number of readers, have proven to not live up to their expectations. As it stands, nothing I've said so far has shown any real problems within set theory. ZFC set theory has proven itself durable, and although I find some non-intuitive attributes to the formal system, it has proven itself consistent. It is exactly as it was designed to be.

I am going to present another possible argument (I've learned to not say proof :-) that most likely will crash itself at the rocks of set theory, like all of the others. Still, I am too much of a stubborn fool to just turn and run ...

This argument will come in three parts:

1. I will define a data-structure that exists OUTSIDE of set theory.
2. I will use the data-structure to define a set.
3. I will apply Cantor's diagonal construction to the set, and examine the results.


THE DATA-STRUCTURE

This section will define a data-structure that will be useful later in defining a set. The data-structure itself is not intended to be within set theory, and is only really useful as a convenient method of enumerating the number values to be placed in the set.

Lets start by specifying three irrational values:

sqrt(2)/10 = 0.141421356...
e/10 = 0.271828183...
Pi/10 = 0.314159265...

Each of these values is an irrational number, that is they contain an infinitely long non-repeating sequence of digits. The division by 10 just shifts the digits, it doesn't alter the non-repeating representation.

Lets construct a subtree P0 such that:

- it is an N-ary tree, where each and every node has exactly 10 children.
- the value placed at the root is 0.
- the value of each child node from left to right is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, this extends to all of the children, all of the way down to infinity.

We can define a path through P0, as being the sequence of digits starting at the root and continuing all of the way to infinity. Thus:

- All paths are infinitely long.
- There are an infinite number of these paths in the structure.

Each path, expresses either a finite rational, a infinitely repeating rational, or an infinitely long non-repeating irrational. A few examples of each are:

a) 0.000000000... is a finite rational. (commonly written as 0)
b) 0.000110100... is a finite rational. (commonly written as 0.0001101)
c) 0.333333333... is an repeating rational (commonly written as 1/3)
d) 0.151515151... is an repeating irrational (commonly written as 1/6.6)
e) 0.999999999... is an repeating rational
f) 0.141421356...  is an irrational (commonly written as sqrt(2)/10)
g) 0.271828183... is an irrational (commonly written as e/10)
h) 0.314159265... is an irrational (commonly written as Pi/10)


We can see that a) is in the structure, starting at root and continuing down each and every far left hand child (0) until infinity. b) goes from the root to thru a 3 zeros, then to a 1, another 1, and then continues down the tree for all of the zeros. c) follows the 3 children (4th branch) and d) alternates between 1 and 5. e) follows the far right child all of the way down to infinity.

f), g) and h) follow a much more complex path from the root, twisting and turning at each level in a way to guarantee that they aren't going to repeat in any way.

By construction, this tree contains paths that specify all of the permutations of all possible real values in the range [0,1). Although each node has exactly 10 children, there are an infinite number of paths, and each path is infinitely long.

Because it is fully specified, we can say that 0.0000000..., 0.333333333... and 0.999999999... are paths in P0. We can also say that sqrt(2)/10 is a path in P0. And we can say that both e/10 and Pi/10 are paths in P0. There are an infinite number of these defined paths in P0.

We can now construct a tree called T that has an infinite number of children, stretching out to infinity on the right. For convenience we can say that the value contained at the root of T is 0.

To construct the children we can start by adding in P0, at the left-hand node. To the right, increasing by 1 each time, we can add in an infinite number of children:

P0, P1, P2, P3, P4, ...

P1 is similar to P0, in that it permutes all possible combination of paths, but it's root value is 1 instead of 0. P2 is 2, P3 is 3, etc. Each Pn subtree covers the range [n,n+1) of real numbers. Each Pn subtree permutes all possible combinations of the infinite paths. Each Pn subtree fits snugly against its siblings, so that together the children cover the range [0, infinity]

Now we need to show that T encodes all possible representations for all possible real values. We can start by noting that any infinitessimally small values are contained in P0, located somewhere on the left-hand side of the branches of P0, such as example b) from above.

Any large irrational value, such as Pi^e can be found thus:

Pi^e = 22.4591577...  which starts at the child P22, the 23rd node of T, and works its way down to infinity. 

Because there are an infinite number of Pn subtrees, all extremely huge reals are contained in a subtree somewhere. Pi starts under P3, e in P2, etc.

So the structure contains all of the large numbers, the small ones, and every possible infinite variation of the digits on both sides of the decimal place. Thus the tree T contains an infinite representation for every possible value in R.


THE SETS

By definition, any irrational or real value can be used in a set. That is we can define a finite set

A = { sqrt(2), e, Pi }

and although the actual values of each of these elements are infinitely long non-repeating values, they are completely included in the set, and the set itself is countable.

So, we can define a finite set from our 8 example numbers in P0:

B = { 0, 0.0001101, 1/3, 1/6.6, 0.999999..., sqrt(2)/10, e/10, Pi/10 }

This set is countable.

We can extend this method of defining a set to handle an infinite number of elements. Thus we can define a set P0 from the above subtree P0 as follows:

The set P0 contains exactly one element from each and every infinitely path in the subtree P0. Since order doesn't matter in a set, we can express this set as follows:

P0 = { 0, 1/3, Pi/10, sqrt(2)/10, e/10, r1, r2, r3, ... }

Where r1, r2, r3, ... are all of the other reals matching the infinite number of different paths in the subtree P0. Based on the elementary property of sets we can say that:

- The set P0 contains irrationals such as Pi/10.
- The set P0 contains rationals such as 0 and 1/3.
- The set is infinite.

We can show that:

- The set P0 is countable.
- The set P0 is countably infinite.

because we can trivially construct a function f: P0 -> N that is an injection. If we have an injection f on a infinite set, by the basis of set theory we can always find a bijection.

From the construction and because the set is countably infinite we can say that:

- The set P0 contains all of the infinite paths that exist in the subtree P0.

As well as P0, we can define the sets P1, P2, P3, ... to have the exact same properties as the set P0. That is they have unordered elements such as:

P1 = { 1, 4/3, r1_1, r1_2, r1_3, ... }
P2 = { 2, 7/3, r2_1, r2_2, r2_3, ... }

We can now define a set T, such that it is the union of all of the elements of the sets P0, P1, P3, ... Because the order of sets is unimportant, we can list the elements in the set T by the following method:

The first element in the set T is the 1st element of P0.
The second element in the set T is the 2nd element of P0.
The third element in the set T is the 1st element of P1.
The fourth element in the set T is 3rd element of P0.
The fifth element in the set T is the 2nd element of P1.
The sixth element in the set T is the 1st element of P2.
....

This enumeration shows that there is an injective function between the elements of T and N.

The enumeration gives us the set:

T = { 0, 1/3, 1, Pi/10, 4/3, 2, ... }

Because this set is constructed from the union of countably infinite sets, and because we can trivially construct an f: T -> N,  this set too is countably infinite.

Please note that although we defined the sets from the corresponding data structures, other than as a syntactic way to enumerate out all of the elements for the definition of the set, the data structures themselves are not used in the basis of this argument.

I say this because many counter-arguments will attempt to show that the subtree P0 is uncountable. Whether it is or is not, doesn't matter because within the rules of set theory we can define the sets Pn to have an infinite number of elements,  and we can only use the tree as a method of enumerating these elements in a descriptive way for the definition.

At very least, we could use an intervening seqeunce constructed from descending the tree, one infinite path at a time in some fixed order. As an infinite sequence, it could contain all of the infinitely long paths. We can always construct such a sequence from the infinite number of infinite paths contained within the tree because otherwise Cantor's diagonal argument would never be able to test such an arrangement of numbers, and this would be an inconsistency in set theory. It has been shown multiple times that Cantor's can test any possible arrangement of real numbers. Because of that constructing a sequence must be possible. 


THE TEST

So, now we have a set T, which we believe contains all of the possible real values. Of course we must test this with Cantor's diagonal argument. We do this by constructing a sequence from our set T, and apply the diagonal argument to that sequence.

Now, there are four possible outcomes from Cantor's argument:

1. It constructs an element E, found in T.
2. It constructs an element E, not found in T.
3. It never halts.
4. It constructs an element E, but not from all of the elements in T.

#3 and #4 can be shown to be trivially not possible. That is, they rely on there being structures in set theory that are larger than just sequences (aka magic sequences), but over the last few weeks, there has been more than ample proof that such structures do not, and cannot exist in set theory, and that the first principles of set theory itself keep them from existing. Thus Cantor's diagonal argument by definition can always construct an element E from all of the elements in the sequence T.

#2 is the normal expected behavior for Cantor's. That is, we expect to go through the construction and be able to create an element E that is a real number, but that is not contained in the set T. Since T is countably infinite, there is definitely some enumeration to which we can apply the construction. Now, since T contains all of the elements from the sets P0, P1, P2, ... and these in turn contain all of the possible elements from their data-structure counter-parts, the only way for any elements to get missed, is for them to have dropped out when we went from the data structures to the sets and then to the sequence. That is, the data-structure self-evidently contains all possible permutations of all real numbers, so either Cantor's is wrong, set theory is inconsistent or something got lost along the way (ie. that R itself is not able to fit into set theory, so it's not even uncountable, it is just outside looking in).

#1 would confirm that T, which is R, is countable. Which given it's underlying status, I think this may actually show a contradiction as well because T is infinitely countable and R is uncountable, yet they are isomorphic to each other.

My guess would be that #1 is the likely result, in that we could take the element E that has been constructed, and look it up in the tree T, in some subtree Pn. We will be able to find it there, and thus show that there are no missing elements.

Given everyone's faith in set theory, there is likely some problem with the construction of this argument.