Embedded Files
4.2.3
The Fast Growing Hierarchy Below Ordinal w^w
Diagonalization and FGH up to w^w
We are now going to extend FGH to the next major subsystem: FGH_w^w. It is here that ordinals are customarily introduced as "infinities" which can be used to always transcend any previous set of constructed functions. The ordinal numbers, as presented here, were first devised and explored by Georg Cantor. The conventional interpretation is that the ordinals are a way to count ordered infinite sets. However, we needn't consider them as infinities, and can instead treat them simply as "order types". A discussion of ordinals as infinities would be too diversionary at this point, and we really don't need a lot of theory to get started. We'll explore the ordinals as infinities much later in the book, but for now I will provide a non-standard introduction to them here as simply indexes within an index-set.
The basic idea is that we want to continue creating indexes for our Fast Growing Hierarchy, but we have already used up all the natural numbers. Whenever we run out of indexes, we simply invent a new index which is not in the set of old indexes, and then give this index a function which returns indexes in the old set for any non-negative integer input into the function.
So we can use "ω", to be the first index not identical to any index of the index-set {0,1,2,3,...}. It is in this sense that "ω" (omega) is infinite, because it is above all the natural numbers. This feature however is not essential. We needn't think of "ω" as a number. Rather we can think of it as a set. Every "index" we'll use can be considered a set of all lower ranking indexes. This gives us the following:
0 = {}
1 = {0}
2 = {0,1}
3 = {0,1,2}
4 = {0,1,2,3}
etc.
Using this concept we can define index rank in the following way. Say i and j are two indexes:
i < j
if and only if
i is an element of j
We now construct a set made up of all the natural numbers: {0,1,2,3,...}. This set is represented by the index "ω".
We can now use ω to create a new function in our Fast Growing Hierarchy. This new function is (n)[ω]. There is a problem however. We can't simply use the prior technique of recursion. That idea worked because we would simply apply recursion to a previously constructed function. Here however we have an infinite number of functions to chose from, f_0,f_1,f_2, etc. but no last one. Therefore if we chose any one of them to apply recursion to we simply get a function which already exists in the hierarchy. This is where the concept of diagonalization comes in. The basic idea is this:
Let i be an index, and the set of all lower indexes.
create a sequence, where i[0] is the 0th member, i[1] is the 1st, i[2] is the 2nd, etc. Each member of the sequence is also a member of the set i. As a consequence of our definitions no member of the sequence can be equal to or larger than i. We'll further require that this forms a strictly increasing sequence, that is:
i[a] < i[b] : a < b
We also place this additional stipulation: the sequence must be constructed so that for any member of i, α, there is a least natural number, k, such that:
i[k] >= α
This ensures that the sequence has just as much strength as the set i, and that every member is represented in the sequence, or transcended by some member of the sequence.
Now imagine we have such as sequence for "ω" called ω[n]. We can define (n)[ω] as:
(n)[ω] = (n)[ω[n]]
At this point this may seem fairly abstract, but the point here is that there isn't one possible sequence we can use. In practice however, we'll want to pick a sequence that is as natural as possible and works well with other sequences to allow for easier generalization. The simplest sequence with the required properties here is simply to return n:
ω[n] = n
so...
ω[0] = 0
ω[1] = 1
ω[2] = 2
etc.
Simple. What we have just done now is defined a diagonalization over the set of all previously constructed functions: {f_0,f_1,f_2,f_3,...}. We now have that:
(n)[ω] = (n)[ω[n]] = (n)[n]
In other words...
(0)[ω] = (0)[0] = 0+1 = 1
(1)[ω] = (1)[1] = 2*1 = 2
(2)[ω] = (2)[2] = 2*2^2 = 8
(3)[ω] = (3)[3] ~ 10^10^8
(4)[ω] = (4)[4] ~ 2^^65,536
(5)[ω] = (5)[5] ~ 2^^^^5
etc.
Not bad. We now have a function roughly equivalent to En##n or n<n-1>n ... and we aren't done. FGH is an open ended system that allows us to continue to define new functions as long as we define the diagonalizations. These diagonalizations are usually referred to as the "fundamental sequences". We have just defined our very first, but we'll be defining many more, infinitely more in fact, as we proceed.
We now have a new FGH set, which includes all the natural number indexed functions and the new f_ω function:
{f_ω,f_0,f_1,f_2,f_3,...}
Every time we want a new function in our hierarchy we simply look for the highest indexed function. If it exists, and it has index " i " then the function is indexed " i + 1 " and is defined as (n)[i+1] = (n)n[ i ]. If it does not exist we simply define a new index " i ", which does not occur in all of the previous indexes, and then we define a sequence i[n] which surpasses any given index of set i for some minimum n. We then simply define (n)[ i ] = (n)[ i[n] ]. These two deceptively simple rules codify everything we need to define FGH for as long as we can define the indexes and their fundamental sequences. We also need to define the zeroth indexed function. This forms the 3 rules for FGH:
Def. of Fast Growing Hierarchy
Let (n)[α] be defined where n={0,1,2,3,...} and "α" is a set of legal indexes which includes a first member denoted "0", and a successor operation denoted "+1":
1. If α=0 ; (n)[0] = n+1
2. (n)[α+1] = (n)n[α]
3. (n)[α] = (n)[α[n]]
This definition glosses over some technical issues, and also obscures the key difficulty: defining the fundamental sequences. It might also be said that defining the set of legal indexes is also part of the challenge of building FGH. There are however already well established sequences and sets for the lower levels of FGH. We will be relying heavily on these conventions in the beginning.
In any case we won't have any real difficulties in the beginning. Whenever we leave off at a particular index, we can simply add 1 to create a new index and use rule 2 to define the corresponding function.
So for example to get past (n)[ω] we simply define a new index "ω+1", and define a new function:
(n)[ω+1] = (n)n[ω]
Believe it or not (n)[ω+1] already grows as fast as Graham's function. Recall that Graham's function is defined:
G(1) = 3^^^^3
G(n) = <3,3,G(n-1)>
Also recall that:
(n)[m] >> <2,n,m-1>
where m and n are positive integers and m>1
From this we get that:
(0)[ω+1] = (0)0[ω] = 0
(1)[ω+1] = (1)[ω] = (1)[ω[1]] = (1)[1] = 2*1 = 2
(2)[ω+1] = (2)2[ω] = ((2)[ω])[ω] = ((2)[2])[ω] = (8)[ω] = (8)[8] > <2,8,7>
(3)[w+1] = (3)3[w] = ((3)[3])2[w] >> (8)2[w] = ((8)[8])[w] > (<2,8,7>)[w] =
(<2,8,7>)[<2,8,7>] > <2,<2,8,7>,<2,8,7>-1>
In general we have that:
(n+1)[w+1] = (n+1)n+1[w] > ((n)n[w])[w] > <2,8,(n)n[w]-1>
In other words, we are feeding back into the number of up-arrows. The " -1 " is of little concern here and won't actually slow down (n)[w+1] relative to G(n). In fact, all f_w+1 needs is a little bit of a head start in order to dominate G(n). Since this is also true for G(n) this proves that G and f_w+1 are of an equivalent growth rate.
Unlike G(n) however, we can continue to create new functions in FGH in a systematic way.
To create a new function we simply +1 to the previous index and create:
(n)[w+1+1] = (n)n[w+1]
For convenience we can truncate this to w+2. The function f_w+2 is now as powerful as a function which feeds the G function back into itself! Better yet we can keep going with:
(n)[w+3] = (n)n[w+2]
(n)[w+4] = (n)n[w+3]
(n)[w+5] = (n)n[w+4]
...
Continuing this trend indefinitely produces the following unbounded set of functions:
{f0,fw,f1,fw+1,f2,fw+2,f3,fw+3,...}
This set has no supremum (no highest index). We therefore must define a new index outside this set of indexes, and a new fundamental sequence in order to continue. We have no hit our 2nd limit ordinal.
A natural choice for this new index seems to be w+w. This can be truncated to 2w. I should note here that it is more conventional to use the notation w*2 for technical reasons. This mostly has to do with the definitions of ordinal arithmetic. While ordinal arithmetic has some handy applications in googology, it isn't always necessary. Here "2w" is simply an "index", a "name" which is distinct from all previous index/names. The "arithmetic" in this case is entirely superfluous. We could just as easily use "0,1" for "w" and "0,2" for "w*2" or "2w". Later when we investigate further we'll find that paying attention to the order of operations will prove handy, but for now we can mostly gloss over this technical detail.
Now that we have a new index, "2w", we need a fundamental sequence for it. This sequence must surpass every index prior to 2w at some finite point, and this sequence should be strictly increasing. Typically we assign:
2w[n] = w+n
This gives us the sequence:
{w,w+1,w+2,w+3,...}
Since w is already greater than any member of w[n] we needn't worry about them. Every other member of the set 2w is surpassed at some point along the 2w[n] sequence.
We now simply define:
(n)[2w] = (n)[2w[n]] = (n)[w+n]
At this point you can probably already see a larger pattern emerging. Now that we have f_2w, we can repeatedly apply Rule 2, to automatically generate f_2w+1, f_2w+2, f_2w+3, f_2w+4, f_2w+5, etc. This will produce a new function set:
{f0,fw,f2w,f1,fw+1,f2w+1,f2,fw+2,f2w+2,...}
We define the supremum of these to be 2w+w or 3w, and we assign 3w the fundamental sequence 3w[n] = 2w+n. This just allows us to create a new sequence of functions, 3w+1, 3w+2, etc. a new set containing all these, a new supremum, 4w, and a new fundamental sequence 4w[n] = 3w+n, and so on and so on...
So is this the Fast Growing Hierarchy? Nope. All this produces is a new super set of functions which would include w,2w,3w,4w,5w,etc. The set will include every mw+n where m and n are {0,1,2,3,...}. Every time we encapsulate such an idea we simply get the opportunity to expand FGH further, with only a marginal increase in difficultly each time we do so.
All we need to do to move on beyond this set, is first give it a name, which is an index not already occurring in the set. Next define a fundamental sequence for that index which passes every member of that set eventually.
We can use "ww" or "w2" as the new index, and we can define it's fundamental sequence as:
w2[n] = nw
Note here, for the special case of n=0 we have w2[0] = 0w. "0w" is not an index in our system, but we can interpret this as "0" so that we get the fundamental sequence:
{0,w,2w,3w,4w,5w,...}
Believe it or not, but (n)[w^2] already grows as fast as Conway Chain Arrow Notation for an n length chain! So much for amateur hour! And we've only just begun.
We can now move much faster by simply automating the construction of indexes and fundamental sequences. After w^2, we could continue with w^2+1, w^2+2, w^2+3, etc. Beyond all these we simply define the limit ordinal w^2+w. The next limit ordinal would be w^2+2w, then w^2+3w, etc. Beyond all these we would have 2w^2. Eventually we reach 3w^2, then 4w^2, 5w^2, etc. beyond all these lies w3. In short, we can build up to any power of "w", and we can take any multiple and sum of these powers. The key here is to define precisely the set of indexes which are legal, and what each of their fundamental sequences is.
So we define a new set of indexes, we'll call "X" temporarily. An index is a member of X if it can be written in the form:
anwn+b+an-1wn-1+b+ ... a2w2+b+a1w1+b+a0wb
where n={0,1,2,3,...}, b={0,1,2,3,...} and an~a0 = {0,1,2,3,...}
Whenever a constant , an~a0, is zero, it can be removed along with it's power of "w" as long as this doesn't leave the entire expression blank. Furthermore we have the definitions w^0 =1 and 0w^k = 0.
The fundamental sequence (assuming it's a limit ordinal) for such an index is simply to take the term with the lowest power of "w" (the right most term), reduce it's constant by 1, and append a new term with "w" to a power of one less, and a constant of n. This can be written symbolically as:
anwn+b+an-1wn-1+b+ ... a2w2+b+a1w1+b+a0wb[n] =
anwn+b+an-1wn-1+b+ ... a2w2+b+a1w1+b+(a0-1)wb+nwb-1
In practice this is a lot easier than it looks. To demonstrate, here are some examples:
w2+w[n] = w2+n
w3+2w2[n] = w3+w2+nw
etc.
There is a simpler alternative, but it requires a less compact ordinal notation. Here we use ordinals of the form:
wkn+wk(n-1)+ ... +wk2+wk1+wk0
With k0 ~ kn being non-negative integer constants, and k0 <= k1 <= ... <= kn. Despite the fact that we have no multipliers in front of the powers of "w", we can still express any ordinal in "X". For example:
2w = w+w
3w^2+2w = w^2+w^2+w^2+w+w
The upshot of this is that we can more easily define the fundamental sequences. Let "#" be any portion of the ordinal we wish to omit, up and including the whole ordinal. We then define the following rules:
#+w^k[0] = #
#+w^k[n] = #+w^(k-1)+w^k[n-1]
w^k[0] = 0
w^k[n] = w^(k-1)+w^k[n-1]
provided k>0
We needn't worry about the case when k=0, since w^0=1, in which case we have a successor ordinal and we don't need to define a fundamental sequence for the ordinal (for successor ordinals we can just use the simple rule that #+1[n] = #, but this isn't necessary to define for the purposes of FGH).
Now we have clearly defined a way to compute values for functions such as f_w^3, f_w^4, f_w^5, etc. Thus we now have a new subsystem of FGH with no highest function. The set "X" is usually denoted by the Cantorian ordinal w^w, hence we have constructed subsystem FGH_w^w.
The function set "w^w" now has an infinite number of functions that will surpass any of Bowers' hyper-operators defined within linear space, ie. any binary function you could define, f(a,b), with constants k1 through kn defined by <a,b,k1,k2,...,kn> will be surpassed by some function in "w^w". Not bad.
Every time we increase the exponent of "w" by 1 it's the equivalent of adding 1 entry in BEAF. There is also a close relation between the coefficients in FGH (an through a0) and the values of entries in BEAF. When thought of in this way it makes sense that FGH_w^w is on par with linear arrays. The coefficients of the indexes themselves form arrays.
In fact it is possible to use an alternative notation. Rather than use "w" we can use "0,1" as our index. "w+1" becomes "1,1", "w+2" becomes "2,1" etc. 2w becomes "0,2", 3w becomes "0,3" and w^2 becomes "0,0,1". To convert from the ordinal index to an "array index" simply take the coefficients from least to greatest power of "w", and separate them by commas.
This simplifies the set of indexes to those of the form:
a0,a1,a2,...,an
where a0~an,n={0,1,2,3,...}
The fundamental sequence then can be described as follows:
0,0,...,0,k#[n] = 0,0,...,n,k-1#
where # is the rest of the array. This is much simpler looking. This variation matches up nicely with BEAF.
Here we have that:
(n)[3] ~ <2,n,2>
(n)[4] ~ <2,n,3>
(n)[5] ~ <2,n,4>
...
(n)[0,1] = (n)[n] ~ <2,n,n>
(n)[1,1] ~ <2,n,1,2>
(n)[2,1] ~ <2,n,2,2>
(n)[3,1] ~ <2,n,3,2>
...
(n)[0,2] = (n)[n,1] ~ <2,n,n,2>
(n)[1,2] ~ <2,n,1,3>
...
(n)[0,0,1] = (n)[0,n] ~ <2,n,n,n>
(n)[1,0,1] ~ <2,n,1,1,2>
...
(n)[1,0,0,1] ~ <2,n,1,1,1,2>
(n)[1,0,0,0,1] ~ <2,n,1,1,1,1,2>
etc.
FGH_w^w is also on par with my own xE# (Extended Hyper-E Notation). It can be shown that:
(n)[w] ~ En##n
(n)[w^2] ~ En###n
(n)[w^3] ~ En####n
(n)[w^4] ~ En#####n
(n)[w^5] ~ En######n
etc.
We can also define a nice variation of FGH using array ordinals and define rules for them up to w^w. Here we'll use the format:
(n,m)[A]
Where n and m are non-negative integers, and A is an array of non-negative integers. "n" represents the input of some function of FGH, and "m" represents the functional power. Given this we can provide the following formal definition of FGH up to w^w:
FGH_w^w
(Array Indexed)
Let (n,m)[A] be defined where n,m={0,1,2,3,...} & A = " a0,a1,a2,...,ak" where k={0,1,2,3,...} and a0~ak={0,1,2,3,...} as follows:
1. A=0 ; (n,m)[0] = n+m
2. m=0 ; (n,0)[A] = n
3. ak=0 ; (n,m)[#,0] = (n,m)[#]
4. m=1, a0~ai=0 a(i+1)=!0 ; (n,1)[0,0,...,0,0,k#] = (n,1)[0,0,...,0,n,k-1#]
5. m=1 ; (n,1)[a0,#] = (n,n)[a0-1,#]
6. (n,m)(A) = ((n,1)[A],m-1)[A]
Functional growth rates up to f_w^w are already more than sufficient to cover anything we're likely to come up with in practical applications ... but for the purely theoretical we can extend FGH much further than this still. We can keep going as long as we can define the set of indexes and all of it's fundamental sequences...
Page updated
Google Sites
Report abuse