NOTE ON THE DEFINITION OF GROWTH RATES
The definition of the limit ordinal for a notation system implicitly rests on the definition of growth rates. Computer science uses Big-O notation to establish a classification system of growth rates, however I use a slightly different definition (growth class) when working in googology.
The Order-Type of Extended Cascading-E is greater than Gamma-naught
ABSTRACT
What does it mean to say the order-type of a particular googological system is such and such in the fast growing hierarchy? This notion has been used to gauge the strength of various notations for the purposes of comparison. For example we can say that Conway's Chain-arrows has order-type ω2. This is it's "ordinal strength" or "growth rate" in FGH.
Informally what we mean when we assign such an ordinal to a system is that it can only reasonably express numbers of roughly this size given a reasonable character limit, say 500 characters. More formally the ordinal is the slowest growth rate in FGH which exceeds the growth rate of any function definable within a given system. It is this latter definition which we will be using. So when we say Chain Arrows is of order-ω2 we are actually saying that every function definable in Chain Arrows grows slower than ω2.
The goal in this article is to demonstrate that xE^ is indeed of order-type greater than φ(1,0,0) (Gamma-naught). This statement can be made precise enough that it can be proven. The basic strategy will be to show that for every member of FGH_φ(1,0,0) there is a function in xE^ with at least the same growth rate. This proves that the limit ordinal of xE^ can be no smaller than φ(1,0,0).
Technically this doesn't prove it's exactly φ(1,0,0), only that it's at least of this order. To do this it would be necessary to demonstrate that f_φ(1,0,0) grows faster than any function definable in xE^. This would require some fairly sophisticated enumeration techniques. We'll explore this towards the end of the article.
PRELIMINARY DEFINITIONS
We begin by establishing some important definitions...
A function (from integers to integers) is STRICTLY INCREASING FUNCTION (S.INC) if and only if:
For EVERY a<b we have f(a) < f(b)
When f(x)=x we say that "x" is a FIXED-POINT of f. When f(x)<x we say that "x" is a DEFICIENCY-POINT of f. When f(x)>x we say that "x" is a ABUNDANCY-POINT of f.
Thus an EVERYWHERE ABUNDANT FUNCTION (E.AB) is a function such that every point is an abundancy-point. ie:
For EVERY x we have x < f(x)
In googology we may adopt the following definition for growth rate. We will say g(n) grows faster than f(n) if and only if for every Δn >= 0 , there exists an N such that:
f(n+Δn) < g(n) : n>N
In other words, if we have two sequences, and no matter how much of a head start we give f, g always "wins out" eventually (gains a permanent and irreversible lead), then g is clearly a faster growing sequence than f.
This is symbolized:
f(n) [<] g(n)
If the condition fails for at least one of integer constants ,Δn, then g(n) does not grow faster than f(n) and we can write:
f(n) [!<] g(n)
If f(n) [!<] g(n) and g(n) [!<] f(n) then f(n) and g(n) are of the same growth rate and we can write:
f(n) [=] g(n)
A function in growth class-α, where α is an ordinal, is a function within the same class as f_α in the Fast Growing Hierarchy. In other words:
f(n) is of growth class-α if and only if
f(n) [=] f_α(n)
f(n) is above class-α if and only if:
f_α(n) [<] f(n)
A SYSTEM OF NOTATION is a legal set of CONSTRUCTIONS only involving a predefined set of functions. For example if our system of notation only contains the function S(n), then the legal constructions are: n, S(n), S(S(n)), S(S(S(n))), etc. Functional powers are not allowed. Each construction will involve a finite set of arguments (in this case only 1 argument is possible). Some of these arguments may take on a constant, while others can take on the independent variable n. Every such construction defines a function with some growth rate.
The LIMIT ORDINAL of a System of Notation is the least member of FGH with a growth rate greater than any function definable within that system of notation using constructions.
Strategy overview
All n are element of Z+.
(n)[0] = n+1
(n)[1] = 2n
(n)[2] = n*2^n < 2^n*2^n = 4^n < 10^n = En = n#{0}
:: (n)[2] < n#{0} : n element Z+
(n)[3] = n[2]^n < EEE..EEEn = En#n < E(E100#n)#n = E100#(2n)
Note: Need proof that n < E100#n
Inductive...
1 < 10^1
k < 10^k
k+1 <= k+k < 10*k < 10*10^k = 10^(k+1)
Inductive...
since n < En for all n...
1 < E1 < E100 = E100#1
k < E100#k
k+1 < 10*E100#k
climbing method is required.
(n)[4] < E100#(2*E100#(2*E100#(2* ... (2*E100#(2n))))
E100#(E100#(E100#( ... (E100#(2n+1)))) = E100#(2n+1)#n
< E100#(E100#100#n)#n = E100#100#(2n)
(n)[5] < E100#100#(2n+1)#n < E100#100#(E100#100#100#n)#n = E100#100#100#(2n)
etc.
(n)[2] < n#{0}
(n)[3] < (2n)#{1}
(n)[4] < (2n)#{2}
(n)[5] < (2n)#{3}
...
(n)[k+2] < (2n)#{k}
(n)[ω] = (n)[n] < (2n)#{n-2} = E100#100#100# ... #100#100#(2n)
< (2n)#{ω}
since E100##(2n)
(2n)#{n-2} < (2n)#{n}
E100#2
E100#100#4
E100#100#100#6
E100#100#100#100#8
etc.
vs.
E100#100
E100#100#100#100
E100#100#100#100#100#100
so...
(n)[ω] << (2n)#{ω} = E100##(2n)
(n)[ω+1] = E100##(2n+1)#n << E100##(E100##100#n)#n = E100##100#(2n)
need proof for
@(@m#a)#b = @m#(a+b)
proof...
@m#a = @(@(@( ... @(@(@(m))) ... ))) w/a @'s
@X#b = @(@(@( ... @(@(@(X))) ... ))) w/b @'s
So they always add. Thus the same argument can be recycled...
(n)[α] << (2n)#{β} = @(2n)
(n)[α+1] << @(2n+1)#n << @100#(2n) = (2n)#{β+1}
Thus...
(n)[ω] << E100##(2n)
(n)[ω+1] << E100##100#(2n)
(n)[ω+2] << E100##100#100#(2n)
(n)[ω*2] << E100##100##(2n)
(n)[ω^2] << E100###(2n)
ω^2+1 --> ###+#
ω^2+2 --> ###+#+#
ω^2+ω --> ###+##
$(ω) --> #*$(#)
ω^ω --> #^#
(n)[ω^ω] << E100#^#(2n)
ω^(ω+1) --> #^#*#
ω^ω^2 --> #^##
ε0 --> #^^#
ε1 --> (#^^#)^^#
(n)[ε1] << E100(#^^#)^^#(2n)
ε2 --> ((#^^#)^^#)^^#
ε(ω) --> #^^#>#
ε(α) --> #^^#>(α)
ε(0,1) --> #^^##
(#^^##)^^# --> ε(ε(0,1)+1)
(#^^##)^^#>α --> ε(ε(0,1)+α)
(#^^##)^^#>(#^^##)^^# --> ε(ε(0,1)+ε(ε(0,1)+1)) == ε(ε(ε(0,1)+1))
(#^^##)^^#>(#^^##)^^#>(#^^##)^^# --> ε(ε(ε(ε(0,1)+1)))
(#^^##)^^## --> ε(1,1)
#^^##>α --> ε(α,1)
#^^### --> ε(0,2)
#^^###>α --> ε(α,2)
#^^####>α --> ε(α,3)
#^^#^# --> ε(0,ω)
ε(1,ω)[n] = ε(ε(0,ω)+1,n)
(#^^#^#)^^# --> ε(ε(0,ω)+1,0)
(#^^#^#)^^## --> ε(ε(0,ω)+1,1)
(#^^#^#)^^### --> ε(ε(0,ω)+1,2)
(#^^#^#)^^#### --> ε(ε(0,ω)+1,3)
(#^^#^#)^^#^# --> ε(1,ω)
#^^(#^#)>α --> ε(α,ω)
#^^(#^#*#) --> ε(0,ω+1)
#^^(#^#*#)>α --> ε(α,ω+1)
#^^(#^#*#^#)>α --> ε(α,ω*2)
#^^(#^β)>α --> ε(α,β)
Thus #^^^# --> ε(0,0,1) or Γ(0).
(n)[2] = {0,2,8,24,64,160,...}
################################################################################
CONJECTURE
The SYSTEM OF NOTATION xE^ is at least of order-φ(1,0,0)
A PRELIMINARY DISCUSSION OF OUR STRATEGY
For the purposes of proving our conjecture it will not be necessary to enumerate every possible construction/function in xE^. It suffices to show that for every function in FGH_φ(1,0,0) there exists a function in xE^ which grows at least as fast. This means that no order less than φ(1,0,0) could dominate over the entire system.
We will do this by first establishing a special ordinal-indexed sub-set of xE^ and show that every member of FGH_φ(1,0,0) there is a member of this sub-set which grows at least as fast.
In order to establish that one function grows at least as fast as a member of FGH, f_α, all we need to show is that:
f_α(n) < f(n) : n>N
If this is true than f_α CAN NOT be of a higher growth class, since for Δn=0, there is no point at which f_α gains a permanent lead on f as required by the definition. If the above holds it follows that f(n) [>=] f_α(n).
DEFINING THE xE^H SET
For the purposes of comparison we're going to create an ordinal indexed hierarchy within xE^, called the Extended Cascading-E Hierarchy (xE^H). This will allow us to more readily compare the growth rates within it with growth rates in FGH. This has similarities to FB100Zs idea of Ordinal Indexed Extensible-E, but has some considerable differences.
Let n#{α} denote the nth member of the αth sequence.
n#{0} = En
Now imagine an expresion in xE^, with two are more arguments. It's delimiters must be in descending order from left to right. Now imagine each argument of this expression is 100 except the last one which is "n". Each such expression defines a function n#{α} for some ordinal α.
These functions are ordered by the following general rule. Compare first delimiters. Whichever has the greater first delimiter is a higher rank. If the first delimiter is of the same rank, compare the next rank using the same criterion. Continue in this manner until a higher rank is determined or they are shown to be equal.
This order can then be put in one-to-one correspondence with the ordinals to create an ordinal indexed hierarchy. This defines the following sequence:
n#{0} = En
n#{1} = E100#n
n#{2} = E100#100#n
n#{3} = E100#100#100#n
n#{4} = E100#100#100#100#n
...
n#{ω} = E100##n
n#{ω+1} = E100##100#n
n#{ω+1} = E100##100#100#n
...
n#{ω*2} = E100##100##n
n#{ω*3} = E100##100##100##n
...
n#{ω2} = E100###n
n#{ω2+1} = E100###100#n
...
n#{ω3} = E100####n
n#{ω4} = E100#####n
...
n#{ωω} = E100#^#n
...
n#{ω^ω^ω} = E100#^#^#n
...
n#{ε0} = E100#^^#n
n#{ε1} = E100(#^^#)^^#n
...
n#{ε(ω)} = E100#^^#>#n
etc.
We'll use the xE^H to establish that xE^ is at least of order-type
φ(1,0,0).
ESTABLISHING PREREQUISITE PROPERTIES FOR FGH
For the Fast Growing Hierarchy (FGH) we'll use the following notation:
(n)[α] = f_α(n)
(n)m[α] = fm_α(n)
When we want to talk about a set of functions in FGH, I'll use FGH_α to mean the set of all functions in FGH with ordinal-index less than α.
Before we can proceed with the main argument of the proof we first have to establish some important prerequisite properties of every member of FGH below φ(1,0,0). The two properties we need to establish is that every member of
FGH_φ(1,0,0) is a strictly increasing function (S.INC), and also an everywhere abundant function (E.AB).
We'll begin by providing a definition for FGH:
DEF. FGH
n is a non-negative integer
I. (n)[0] = n+1
II. (n)[α+1] = (n)n[α]
III. (n)[α] = (n)[α[n]] *
* where α is a limit ordinal
##########################################################################################################################################################
We can begin by making the following observations:
(n)[0] = n+1
(n)[1] = 2n
(n)[2] = n*2n
For the purposes of comparison we'll assume that "n" is a positive integer, since ExE doesn't work with zero. For this we also make the observation that:
(1)[α] = 2 : All α
In ExEH we'll find that the smallest value is a googol (E100) except for the instance of 1#{0} = E1 = 10. Otherwise it will tend to be some massive number even at the first value.
Our strategy will be to show that for every member of FGH up to a certain limit ordinal there is a member of ExEH which is always larger for n>0. This can be used to measure the limit ordinal of ExE up to a certain system (we'll use it to measure in turn E#, xE#, E^, and lastly xE^). One important thing to note is that if we have two functions such that f(n)<g(n) provided n>N then g must grow at least as fast as f. The idea here is that if f(n) grew faster it should always overtake g(n) eventually. The fact that it fails to do so proves it doesn't grow faster. The primary thing we want to do here is prove the growth rate of the system xE^ defined as the least ordinal growth rate in FGH which exceeds all growth rates in the given system. A nice upshot of the proof will be constructible upper-bounds in xE^ for numbers in FGH.
To achieve this we begin by setting up some useful lemmas
(Note: all occurrences of "n" in the following proof are taken as positive integers)
(n)[2] = n*2^n < 2^n*2^n = 4^n < 10^n = En = n#{0}
Therefore...
LEMMA I [L1]
(n)[2] < n#{0}
Because FGH uses a form of primitive recursion slightly stronger than ExE uses we need to establish an upper-bound in standard primitive recursion. Primitive recursion usually involves providing a fixed base value, which is then repeatedly feed into some function. FGH does this, but it also keeps increasing the base value, resulting in a slightly faster growth rate. As will be seen it makes virtually no difference (it will take an really really long time for it to have even one more nested function in the stack). We will upper-bound it with a gross overestimate that it doubles the speed of nesting. To establish this we begin with the following observations:
n < 2^n = (1)n[1]
and
(1)n[0]= n+1 =< 2^n = (1)n[1]
Next we want to show that (1)n[1] =< (1)n[α] for all α>1.
First we can establish it for α=2 :
(1)1[2] = 2 = (1)1[1] by definition
(1)2[2] = (2)[2] = (2)2[1] > (1)2[1] > (1)2[0] = 2+1
Assume...
(1)k[2] > (1)k[1] > k+1
Now we establish for k+1:
(1)k+1[2] = ((1)k[2])[2] = ((1)k[2])(1)^k[2][1]
> (1)k+1[1] > (1)k+1[0] = k+2
So by induction we establish that:
(1)n[1] =< (1)n[2]
So we've established the case for at least one α. We now show that the successor case must be true if α is true:
Assume...
n+1 < (1)n[1] =< (1)n[α]
Now we establish for α+1:
(1)1[α+1] = 2 = (1)1[1] by definition
(1)2[α+1] = (2)[α+1] = (2)2[α] > (1)2[α] > (1)2[1] > 2+1
Assume...
(1)k[α+1] > (1)k[α] > (1)k[1] > k+1
Now we establish for k+1:
(1)k+1[α+1] = ((1)k[α+1])[α+1] = ((1)k[α+1])(1)^k[α+1][α]
> (1)(1)^k[α][α] > (1)k+1[α] > (1)k+1[1] > k+2
So by w^2-induction we establish that:
(1)n[1] =< (1)n[k] : k>1
Now we simply need to show that this also applies for any limit ordinal. Assume that the statement has been proven true for all ordinals less than limit ordinal α:
(1)1[α] = 2 = (1)1[1]
(1)2[α] = (2)[α] = (2)[α[2]]
Here we note that α[n] >= n for all limit ordinals α.
(2)[α[2]] >= (2)[2] = (2)2[1] > (1)2[1] > 2+1
Assume ...
(1)k[α] >= (1)k[1] > k+1
We now establish for k+1:
(1)k+1[α] = ((1)k[α])[α] = ((1)k[α])[α[(1)k[α]]]
> (k+1)[α[(1)k[α]]] >= (k+1)[(1)k[α]] >= (k+1)[(1)k[1]] > (k+1)[k+1]
= (k+1)k+1[k] > (1)k+1[k] > (1)k+1[1] > k+2
Thus we establish our second lemma:
LEMMA II [L2]
(1)n[1] =< (1)n[α]
With these lemmas established we now begin with the proof proper.
We begin by establishing an upbound on (n)[3] in ExE:
(n)[3] = (n)n[2] < (n+1)n[2] < ((1)n[1])n[2] =< ((1)n[2])n[2] via LEMMA II
((1)n[2])n[2] = (1)2n[2] < E1#(2n) via LEMMA I
E1#(2n) < E1#(n*2^n) = E1#((n)[2]) < E1#(En) < E100#(En) <
E100#100#n = n#{2}
(n)[3] only grows at the rate of tetration while n#{2} grows at a pentational growth rate. Although this might seem wasteful it won't end up mattering much in the long run. We won't exhaust xE^ any faster than we exhaust FGH_ϕ(ω,0,0). Our only goal is to show that for every member of a given sub-system of FGH there is a member of ExE of a given sub-system which grows faster. This establishes the minimum strength of the system we're measuring against FGH.
We can quickly establish that E# has limit ordinal ω in FGH.
Assume that:
(n)[a] < n#{b}
now consider (n)[a+1]:
(n)[a+1] = (n)n[a] < (1)2n[a] < E100#100#...#100#1#2n w/b 100s
< E100#100#...#100#100#100#n w/b+2 100s = n#{b+2}
In other words for every function in FGH_ω there is a function in ExEH_ω which grows at least as fast. For E# has limit ordinal ω.
We can further establish the following constructive upperbounds:
(n)[0] << n#{0} --> (n)[k] << n#{2k}
Next we look at FGH_ω^ω and xE#:
(n)[ω] = (n)[n] < n#{2n} < 1#{100n} = E100##(100n) =< E100##100#n = n#{ω+1}
By the same argument established previously previously we also have
(n)[ω+1] < n#{ω+3}
(n)[ω+2] < n#{ω+5}
(n)[ω+3] < n#{ω+7}
...
(n)[ω+k] < n#{ω+2k+1}
We now diagonalize over this construction:
(n)[ω+ω] = (n)[ω+n] < n#{ω+2n+1} < 1#{ω+100n} = E100##100##(100n)
<< E100##100##100#n = n#{ω+ω+1}
This establishes the next level of diagonalization:
(n)[ω*k] < n#{ω*k+1}
So we find that for limit ordinals the successor of that ordinal in ExE grows at least as fast. We'll see this property continue throughout FGH as we climb up xE^.
With this property established we now go up to (n)[ω^2]:
(n)[ω^2] = (n)[ω*n] < n#{ω*n+1} < 1#{ω*100n} = E100###(100n)
=< E100###100#n = n#{ω^2+1}
and this brings us up to the next level. So we can now use induction to take us to the limits of xE#.
Assume...
(n)[ω^m*k] < n#{ω^m*k+1}
(n)[ω^(m+1)] = (n)[ω^m*n] < n#{ω^m*n+1} < 1#{ω^m*100n}
= E100#m+2(100n) = E100#m+2100#n = n#{ω^(m+1)+1}
Thus we establish for every member of FGH_ω^ω there is a member of of xE#H which grows at least as fast. So xE# has limit ordinal ω^ω.
We now use the established facts to support the claim that every limit ordinal in FGH can be matched by its successor ordinal in ExEH.
Assume that some set of ordinals less than limit ordinal α. We now establish that the limit ordinal α is matched by α+1:
(n)[α] = (n)[α[n]]
α[n] must be a member of set α, so there must be a function n#{β} with β<α which grows at least as fast as (n){α[n]}. If α[n] is a limit ordinal (most likely) then it's matched by α[n]+1 in ExE, and if it's a successor ordinal it's matched by α[n]+n+1. So we have :
(n)[α[n]] < n#{α[n]+n+1} < 1#{α[n]*100n}