xE# versus FGH
ABSTRACT
This paper extends upon methods and concepts presented in the paper "Equipotency of E# with FGH_ω". In this paper it will be demonstrated conclusively that xE# is equipotent with FGH_ω^ω. The term "equipotency" should not be confused with the term "cardinality" here. Instead the term is borrowed from it's proper english definition of "equally powerful". The technical definition of equipotency here is that two systems are equipotent if and only if there exists no function in either system capable of eventually dominating every function in the other system. In other words, for any given function in FGH_ω^ω there exists a function in xE# that eventually dominates it, while for any given function in xE# there exists a function in FGH_ω^ω which eventually dominates it. What this means in laymen's terms is that xE# is just as good as expressing a certain range of large numbers as FGH_ω^ω.
We can skip some of the preliminaries that were established in the previous article. We will begin by first defining our two systems:
DEFINITION OF xE#
Let E a_1 &_1 a_2 &_2 ... a_(n-1) &_(n-1) a_n
be defined for a_1 ~ a_n are positive integers
and &_1 ~ &_(n-1) are members of the delimiter set &*
as follows:
1. If n=1 ; E a_1 = 10^(a_1)
2. If a_n = 1 ; @ &_(n-1) 1 = @
3. If &_(n-1) != '#' ; @ a_(n-1) &_(n-1) a_n
= @ a_(n-1) &_(n-1)[] a_(n-1) &_(n-1)((a_n)- 1)
4. otherwise; @ a_(n-1) # a_n = @ ( @ a_(n-1) # ((a_n)-1) )
DEFINITION &*
'#' is an element of &*
If '@' is an element of &* then '@#' is an element of &*
DEFINITION &[]
#[] is undefined.
If & != # it can be expressed as @#. If so @#[] = @
DEFINITION OF FGH_ω^ω
Let f_α(n) be defined for n is a non-negative integer and α is a member of ω^ω*
1. If α = 0 ; f_0(n) = n+1
2. If α = β+1 ; f_β+1(n) = f_β^n(n)
3. If α is a limit ordinal ; f_α(n) = f_α[n](n)
DEFINITION OF ω^ω*
0 is an element of ω^ω*
If 'α' is an element of ω^ω* then 'α+1' is an element of ω^ω*
'ω^k' where k is a positive integer is an element of ω^ω*
If 'α' and 'β' are elements of ω^ω* then 'α+β' is an element of ω^ω*
DEFINITION OF α[n]
If α = @+1 then α is a successor FSE, otherwise α is a limit FSE.
If α is a limit FSE, it can be expressed as @+ω^k or @ω^k. In this case α[n] is defined as follows:
If α = ω^1 ; @ω^1[n] = @n
If α = ω^k , where k>1 ;
@ω^k[0] = @
@ω^k[n] = @ω^(k-1)+ω^k[n-1]
DEFINITION OF xE#H
Express:
##...## w/k #s as #^k
Let an expression of xE# be represented by:
E100#^(x1)100#^(x2) ... 100 #^(x(n-1)) a_n
Let this correspond to the shorthand:
E100#*(ω^(x1-1)+ω^(x2-1)+ ... ω^(x(n-1)-1)) a_n
where ω^0 = 1. In this way we map every member of ω^ω* with a distinct function of xE#H. In order to weed out all the rogue cases, we can add the stipulation that:
x1 >= x2 >= x3 >= ... >= x(n-1)
These correspond to the ordinals of the set ω^ω. This forms an ordered set of order-type ω^ω of functions in xE#. This is the so called Extended Hyper-E Hierarchy (xE#H).
DEFINITION OF FGH_ω^ω HIERARCHY
Let α be a valid member of the hierarchy if and only if:
α = ω^(x1)+ω^(x2)+ ... ω^(xn)
where x1 >= x2 >= x3 >= ... >= xn
and where ω^0 = 1. In this case:
f_α(n) is a member of the hierarchy.
CONJECTURE
Let α = ω^(x1)+ω^(x2)+ ... ω^(xn) where x1>=x2>= ... >= xn and ω^0 = 1.
f_α(n) < E100#*(α)2n ∀α<ω^ω
THE FIRST LIMIT CASE
Before we can delve into the proof overall we need to establish an important property for the first limit case.
Recall that:
f_k(n) < E100#100# ... #100#2n w/k-2 100s : k>2
Furthermore...
f_k(n) < E100#100# ... #100#100#n w/k-1 100s : k>2
and...
f_k(n) < E100#100# ... #100#100#100#n w/k 100s : k>2
which we can write simply as:
E100#*(k)n
Furthermore we have:
f_ω(n) = f_n(n) < E100#*(n)n
We want to establish that for all "n":
E100#*(n)n < E100#*(2n)1
Recall our proof that every function of E# it is a S.IN/E.AB function.
@100#100
= @@@...@@@100 w/100 @s
Since @n is E.AB
@n > n
Combined with AxMS we have:
@n >= n+1
Therefore:
@100 >= 101
@@100 >= @101 >= 102
etc.
@@@...@@@100 w/100 @s >= @199
This means that:
E100#*(n)100#*(n)1
= E100#*(n)100#*(n-1)100
>= E100#*(n)100#*(n-2)199
>= E100#*(n)100#*(n-3)298
...
>= E100#*(n)(100+99(n-1))
= E100#*(n)(100+99n-99)
= E100#*(n)(99n+1)
> E100#*(n)n
n < 99n+1
via AxP&F
and E100#*(n)n < E100#*(n)(99n+1)
bec. E100#*(k)n is a S.IN function.
Thus we have just proven that:
E100#*(n)n < E100#*(2n)1
E100#*(2n)1 = E100##(2n)
Therefore:
f_ω(n) < E100##(2n)
An important part of this proof is to show that each valid step implies the successor step. To do this we adopt the proof used in "Equipotency of E# with FGH_w", and generalize it. This means we need to demonstrate that every function in xE# has the property:
3@n < @(n+1)
This was already demonstrated for E#. The tricky part here is actually to establish it for the limit cases. Can we establish this property for E100##n?
We can acknowledge that:
E100##n
We need to prove that:
3@100 < @100#100
This is fairly easily done since:
@100#100 = @@@...@@@100 w/100 @s
and @ is E.AB, so...
@^(100)100 >= @^(99)101 >= @^(98)102 >= ... >= @199
3@100 < @101 < @199 since @ is S.IN
Thus this is also true for E100##n.
So we have proven:
3E100##n < E100##(n+1)
It is also important we show that E100##n is a S.IN and E.AB function.
Lemma 2 from "Equipotency of E# with FGH_w" establishes conclusively that:
E100 < E100#100 < E100#100#100 < E100#100#100#100 < ...
So we know that E100##n is S.IN
To prove it's E.AB, we need only show that:
E100 > 1
Since this is obviously so we have:
E100#100 > E100 > 1 --> E100#100 > E100 >= 2 --> E100#100 > 2
E100#100#100 > E100#100 > 2 --> E100#100#100 > E100#100 >= 3
--> E100#100#100 > 3
etc.
So E100##n > n
Therefore E100##n is E.AB
What we want to do now is set up a feed-back induction where we establish the successor cases on the limit cases, and the limit cases on the successor cases, but use each to support the other.
We begin by establishing the successor cases for certain assumptions:
Assume @n is a function such that:
@n is S.IN/E.AB and 3@n < @(n+1)
Can we prove all these properties for the successor case?
@100#n
= @@@...@@@100 w/n @s
@100 > @1 > 1
@@100 > @100 > 1 --> @@100 > @100 >= 2 --> @@100 > 2
@@@100 > @@100 > 2 --> @@@100 > @@100 >= 3 --> @@@100 > 3
etc.
so
@@...@@100 w/n @s > n
@100#n > n
Therefore @100#n is E.AB
Since @n is E.AB it follows that:
@100 < @(@100) < @(@@100) < @(@@@100) < ...
Therefore @100#n is also S.IN
Now we observe that:
3@100 < @101 <= @@100 --> 3@100 < @@100
Assume:
3@100#k < @100#(k+1)
3@100#(k+1) = 3@(@100#k) < @((@100#k)+1) < @(@100#k+@100#k+@100#k)
= @(3@100#k) < @(@100#(k+1)) < @100#(k+2)
So it holds then that:
3@100#n < @100#(n+1)
So as long as we can establish something for a particular case, we also establish all these properties automatically for all successors of that case.
So what happens when we consider a limit case?
Assume the property holds for all cases below the relevant case:
So we have:
@100#^(k)n
Firstly we know:
@100#^(k)n =
@100#^(k-1)100#^(k-1) ... 100#^(k-1)100 w/n 100s
This must have a lower order so we can assume all the prerequisite properties needed. In order to make this work it will be important to prove another very important property. Namely that:
E100#*(α)n < E100#*(β)n : α<β
But this property may not be true in general. At very least we need to demonstrate it for successor cases. Actually there is a simple counter example that shows that this property can not hold in general. Namely
Let α=2 , β = ω , and n = 1
In this case we have:
E100##1 = E100 < E100#100 = E100#100#1
What we do have is that E100##n eventually surpasses any function of the form E100#*(k)n. But a strict inequality is not possible in this case.
Can we show that:
@100 < @100#^(k)100
In all cases?
Let's prove:
f_ω+1(n) < E100##100#(2n)
Firstly we previously established that:
f_w(n) < E100##(2n)
We also proved that:
E100##n is S.IN/E.AB and that 3E100##n < E100##(n+1)
Furthermore if:
@n is S.IN/E.AB and 3@n < @(n+1)
then this also holds for @100#n
From this we gather the following:
f_w+1(n) = f_w^n(n)
< E100##(2*E100##(2*E100##( ... (2*E100##(2n)) ... ) w/n 100s
< E100##(E100##(1+2*E100##( ... (2*E100##(2n)) ... )
< E100##(E100##(3*E100##( ... )
< E100##(E100##(E100##(1+2*E100##( ... )
etc.
so that we eventually get...
< E100##(2n+1)#n
Here we need to show that 2n+1 < E100##100#n
we know that:
2n+1 <= 3n < En < E100#n < E100#100#n etc.
When n=1 we have 3 < E100
E100#100 > 6
E100##n >= E(99n+1) > En > 3n
and we also have:
E100##1 < E100##100
E100##2 < E100##(E100##100)
E100##(E100##100) >= E100##101 > E100##2
E100##(E100##100#2) >= E100##102 > E100##3
etc.
So we have:
E100##n < E100##100#n
From this we conclude:
E100##(2n+1)#n < E100##(E100##n)#n < E100##(E100##100#n)#n
= E100##100#(2n)
Therefore:
f_ω+1(n) < E100##100#(2n)
A General Successor Case
Assume:
f_α(n) < @(2n)
Furthermore assume 3@n < @(n+1), @n is S.IN/E.AB and 3n < @n
Now we want to prove the same for the successor case:
f_α+1(n) = f_α^n(n)
< @2@2@2@2@ ... 2@2@2@(2n) w/n 2s
< @@(1+2@2@ ... @(2n))
< @@(3@2@ ... @(2n))
< @@@(1+2@ ... @(2n))
etc.
< @@@@...@@@@(2n+1) w/n @s
<= @@@@...@@@@(3n) w/n @s
< @@@@...@@@@(@n)
Note that @n < @100#n since:
@100#n = @@@...@@@100 >= @(n+99) > @n
Therefore:
@@@@...@@@@(@n) < @@@...@@@@(@100#n) = @(@100#n)#n = @100#(2n)
So we see the property transfers over in all of the successor cases. But this only proves that one of the 5 conditions carries over. We also need to show all the other properties
S.IN carries in all successor cases
@n is S.IN/E.AB
@100#1 = @100
@100#(k+1) = @(@100#k) > @100#k bec. @n is E.AB
Therefore @100#n is S.IN
E.AB Carries in all successor cases
@100#1 = @100 > 100 > 1 : bec. @n is E.AB
@100#2 = @@100 > @100 > 1 --> @@100 > @100 >= 2 --> @100#2 > 2
@100#3 = @@@100 > @@100 > 2 --> @@@100 > @@100 >= 3 --> @100#3 > 3
etc.
Therefore:
@100#n is E.AB
Successor case is at least as fast as exponential
3@n < @(n+1)
3@100#1 < @101 <= @@100
Assume 3@100#n < @100#(n+1)
3@100#(n+1) = 3@(@100#n) < @((@100#n)+1) < @(3@100#n)
< @(@100#(n+1)) = @100#(n+2)
Therefore:
3@100#n < @100#(n+1)
Successor Case is larger than 3n
3n < @n
@100 > 300 > 3
@@100 > @300 > 900 > 6
@@@100 > 100*3^3 > 3^3
...
In general
@100#n > 3^n
Now we show 3^n >= 3n
3(1) = 3^1
3(2) = 6 < 9 = 3^2
Assume 3k < 3^k : k>1
3(k+1) = 3k+3 < 3k+3k < 3k+3k+3k = 9k = 3*3k < 3*3^k = 3^(k+1)
So we have:
@100#n > 3^n >= 3n
3n < @100#n
So all the properties easily carry over. So we have shown that any time
f_α(n) < @(2n) --> f_α+1(n) < @100#(2n)
Since
f_ω(n) < E100##(2n)
It now immediately follows that:
f_ω+1(n) < E100##100#(2n)
f_ω+2(n) < E100##100#100#(2n)
f_ω+3(n) < E100##100#100#100#(2n)
etc.
Now what remains is a general means for proving the limit cases based on successor cases and smaller limit cases.
INVESTIGATION INTO THE LIMIT CASES
>PROVE EVERY MEMBER OF xE# is S.IN/E.AB
It has already been proven for every member of E#. We consider whether a limit case must necessarily be S.IN/E.AB provided that every function below it is also S.IN/E.AB.
@100#^(k)n is some limit function. First we show it's strictly increasing:
@100#^(k)(n+1) = @100#^(k-1)100#^(k)n
@100##(n+1) = @100#100##(n) = @100#100#100...#100 w/n+1 100s
If every function below this is S.IN/E.AB then:
@100#100#...#100#n w/k 100s is such a function.
Prove @100#100 > @100
Assume @n is S.IN/E.AB
@100#100 = @@@...@@@100 w/100 @s
Since @n is E.AB it follows that:
@@@...@@@100 >= @@@...@@101 >= @@@...@102 >= ... >= @199 > @100
So yes it is always a larger value when we append an extra hundred, assuming that the previous function is indeed S.IN/E.AB
Since this is the case, and E100##n is S.IN/E.AB it follows that:
E100##100 < E100##100#100 < E100##100#100#100 < E100##100#100#100#100 < ...
Since this is the case:
@100##n is a S.IN function provided @n is S.IN/E.AB.
It is also E.AB since:
@100##1 = @100 >= 101 > 1
@100##2 > @100##1 > 1 --> @100##2 > @100##1 >= 2 --> @100##2 > 2
@100##3 > @100##2 > 2 --> @100##3 > @100##2 >= 3 --> @100##3 > 3
etc.
So we have that it is also E.AB
This then allows us to say:
@100##100##n is S.IN/E.AB since @100##n is S.IN/E.AB
But then we get into an iteration where by
@100##100##100##n is S.IN/E.AB
@100##100##100##100##n is S.IN/E.AB
etc.
So what about @100###n ?
The problem is we need to demonstrate that:
@100 < @100##100 < @100##100##100 < @100##100##100##100 < ...
But we already showed that:
@100 < @100#100 < @100#100#100 < @100#100#100#100 < ...
therefore:
@100 < @100##100 since
@100##100 = @100#100#100# ... #100 w/100 100s
furthermore the same argument applies to:
@100##100 < @100##100##100 < @100##100##100##100 < ...
So this means
@100 < @100###100
But we just showed this is generally true for the deutero-hyperion '##'
So it also follows that:
@100###100 < @100###100##100 < @100###100##100##100 < ...
which implies...
@100###100 < @100###100###100 < @100###100###100###100 < ...
Which implies that:
@100 < @100####100
Which must hold true in general so...
@100 < @100####100 < @100####100####100 < ...
So that @100 < @100#####100
etc.
and thus we can always show that:
@100 < @100#^(k)100
This interestingly proves that every function in xE# is S.IN
Since every function is S.IN we can also easily prove every function in E.AB.
@100#^(k)(n+1) > @100#^(k)n
since it contains one more #^(k-1). So we have shown the strictly increasing property.
We need to show that @100#^(k)1 = @100 is always greater than 1.
This is simple. Assume every function below is E.AB, and that @100#^(k)n is our new function. We have:
1 < @1 < @100 = @100#^(k)1 < @100#^(k)2 < @100#^(k)3 < ...
Since every function is S.IN. By combining this result with AxMS we show that it is also E.AB.
If Every function in xE# is S.IN/E.AB is this enough to prove what we need to prove? No. We still need to know that every function grows at least as fast as exponential.
We can employ a similar strategy here.
We already showed that if 3@n < @(n+1) then 3@100#n < @100#(n+1)
Thus this property carries over an arbitrary number of proto-hyperions.
So we consider a deutero-hyperion case which builds from proto-hyperions:
3@100##n = 3@100#100# ... #100#100 w/n 100s
< @100#100# ... #100#101 w/n-1 100s
< @100#100# ... #100#199 w/n-1 100s
<= @100#100# ... #100#100#100 w/n+1 100s
= @100##(n+1)
So it carries over to a deutero-hyperion case if it carries over for all proto-hyperion cases! Now we can say:
3@100##n < @100##(n+1)
implies:
3@100##100##n < @100##100##(n+1)
implies:
3@100##100##100##n < @100##100##100##(n+1)
etc.
So now it applies to all proto-hyperion and deutero-hyperion cases.
So guess what, we can show it applies to a trito-hyperion now:
3@100###n < @100##100## ... ##100##101 w/n-1 100s
This presents something of a snag here. Can we say that:
@100##100 > @101 ?
Firstly we have that:
@100 < @100##100
But this doesn't actually prove the assertion.
We appear to have to resort to:
@100##n = @100#100#100#...#100#100 >= @100#100#100#...#199
... >= @(99n+1)
So that we have:
@100##100 >= @(99*100+1) = @9901 > @101
This appears to be a sound argument.
Which means that:
3@100###n < @100###(n+1)
So now:
3@100###100###n < @100###100###(n+1)
3@100###100###100###n < @100###100###100###(n+1)
etc.
So we move on to the teterto-hyperions:
3@100####n < @100###100### ... ###100###101
We proved that @101 < @100##100
and furthermore we proved that:
@100##100 < @100##100##100 < @100##100##100##100 < ...
so it follows that:
@100###100### ... ###100###101 < @100###100### ... ###100###100###100
Thus we now have proven that:
3@100####n < @100####(n+1)
So all the teterto-hyperion cases are proven.
In general assume we have shown that 3@100#^(k)n < @100#^(k)(n+1)
and that it's been already shown that @101 < @100#^(k-1)100
Next we have:
3@100#^(k+1)n < @100#^(k)100#^(k) ... 100#^(k)101
@101 < @100#^(k-1)100 < @100#^(k-1)100#^(k-1)100 < ...
so...
@101 < @100#^(k)100
therefore:
@100#^(k)100#^(k) ... 100#^(k)101
< @100#^(k)100#^(k) ... 100#^(k)100#^(k)100
= @100#^(k+1)(n+1)
So we have inductively shown that for every function in xE#
3@n < @(n+1)
That's some powerful stuff.
Now only one thing remains. Can we use this to demonstrate a carry over in limit cases. One more complication might be that if we have a sequence of functions ending in "2n", this may make the proof complicated. We want to perhaps convert this to "n". We also need to find a general way to show that the function diagonalizing over all previous functions is larger.
ω α ∀ β