fgh_ack

The Ackermann Ordinal is named after German mathematician Wilhelm Ackermann (1896-1962), who made many contributions to the theory of computable functions. He is perhaps best known for the Ackermann function which he defined in 1928. It was the first known example of a computable function which was not primitive recursive.

The Ackermann function was already an incredibly powerful function ... but it pales in comparison to what we can create by combining FGH with Ackermann's Ordinal.

The so-called Ackermann Ordinal is actually the limit of an ordinal notation devised by Ackermann that involved a ternary ordinal function. Recall that we explored the consequences of a binary Veblen function in the previous article. It turns out we can extend this to a ternary Veblen function and it's equivalent to Ackermann's Ordinal notation. The supremum of this system is the Ackermann Ordinal, usually denoted φ(1,0,0,0), but which I'll denote as ε(0,0,0,1).

We'll pick up where we left off with the introduction of Γ₀, and introduce the general Γ-function. This will turn out to be woefully insufficient however, and we will have to instead develop a ternary epsilon function in order to reach the Ackermann ordinal. With this achieved we'll be able to reach into the next echelon of FGH, FGH_Ack. We'll discover however that the Ackermann Ordinal is just a small example of an even more extensive ordinal function which allows for any number of arguments. The limit of such a function is the so called Small Veblen Ordinal (SVO). The Ackermann ordinal will provide the basic theory needed to construct this larger ordinal.

The Gamma-Function

When we last left off I had introduced Γ₀ as the supremum of the binary Veblen function. It may have occurred to you that the zero could be treated as an argument signifying it as the first fixed-point of the binary Veblen function, and that this could itself be turned into an ordinal function enumerating the fixed-points of the binary Veblen function. This is exactly what we will do, in the way of introduction, to prepare ourselves for the next major lines of development. Firstly we define a fundamental sequence for Γ₀. When we are in need of a new initial value we can always use 0. We can then nest inside the most significant function currently introduced. So we define:

Γ₀[0] = 0

Γ₀[n] = ε(0,Γ₀[n-1])

This gives us...

Γ₀[0] = 0

Γ₀[1] = ε₀

Γ₀[2] = ε(0,ε₀)

Γ₀[3] = ε(0,ε(0,ε₀))

Γ₀[4] = ε(0,ε(0,ε(0,ε₀)))

...

Taking the union of all the members of the fundamental sequence gives us the first fixed-point of the ordinal-function β-->ε(0,β). ie.

Γ₀ = Γ₀[0] U Γ₀[1] U Γ₀[2] U Γ₀[3] U Γ₀[4] U ...

It may have occurred to you in the previous article that Γ₀ is just another ordinal and is therefore subject to all the previously established constructions. So of coarse we can continue with ...

Γ₀+1 , Γ₀+2 , ... Γ₀+ω , Γ₀+ω^ω , ... Γ₀+ε₀ , Γ₀+ε₁ , ... Γ₀+ε(0,1) ... Γ₀+ε(0,ε₀) ,

Γ₀+ε(0,ε(0,ε₀) , ... Γ₀+Γ₀, Γ₀+Γ₀+Γ₀ ... ω^(Γ₀+1), ω^ω^(Γ₀+1) ... ε(Γ₀+1) , ε(Γ₀+2) ...

ε(ε(Γ₀+1)) , ε(ε(ε(Γ₀+1) ... ε(Γ₀+1,1) , ε(Γ₀+1,2) , ε(Γ₀+1,3) , ...

Some comment at this point is helpful. Note that Γ₀ is a fixed point of every function φ(0,β) where β is less than Γ₀. Hence we have ...

Γ0 = ε(Γ0,0) = ε(Γ0,1) = ε(Γ0,2) = ε(Γ0,3) = ...

This is also true of limit ordinals less than Γ0. One way to recognize this is to remember that an ordinal is just a set represented as the union of the members of it's fundamental sequence. So we consider ε(Γ0,ω). According to the rules previously established for the binary epsilon function, when the first argument is a limit ordinal, we can simply take the first arguments fundamental sequence. So we have ...

ε(Γ0,ω)[n] = ε(Γ0[n],ω)

Therefore ...

ε(Γ0,ω) = ε(0,ω) U ε(ε0,ω) U ε(ε(0,ε0),ω) U ε(ε(0,ε(0,ε0)),ω) U ...

the limit of this sequence is itself still Γ0, therefore ε(Γ0,ω) = Γ0. To get out of this we need to take the successor of Γ0. Applying the rules we obtain ...

ε(Γ0+1,ω)[n] = ε(ε(Γ0,ω)+1,n)

With that in mind we can continue along the sequence of limit ordinals ...

ε(Γ0+1,ω) , ε(Γ0+1,ω+1) , ... ε(Γ0+1,ω+ω) ... ε(Γ0+1,ω^2) ... ε(Γ0+1,ω^ω) ... ε(Γ0+1,ε0) , ε(Γ0+1,ε1) ... ε(Γ0+1,ε(0,1)) ... ε(Γ0+1,ε(0,ω)) ... ε(Γ0+1,ε(0,ε0)) ... ε(Γ0+1,ε(0,ε(0,ε0))) ,

ε(Γ0+1,ε(0,ε(0,ε(0,ε0)))) , ...

Here we reach another trouble spot where we have to be careful to remember the rules. We might be tempted to assume that ε(Γ0,Γ0) = Γ0 , and the ε(Γ0+1,Γ0) is therefore the limit of the above sequence. But this turns out to be very incorrect. Let's first consider the ordinal

ε(0,Γ0). By the rules we would take the fundamental sequence of the second argument. So we have ...

ε(0,Γ0)[n] = ε(0,Γ0[n]) = Γ0[n+1]

So we conclude that ε(0,Γ0) = Γ0. Now we consider ε(1,Γ0)...

According to Law 6 of epsilon (See FGH_Γ0 article) we have ...

ε(1,Γ0)[n] = ε(ε(0,Γ0)+1,Γ0[n])

Look familiar? Remember that ε(0,Γ0) = Γ0 , so this is basically equivalent to ε(Γ0+1,Γ0[n]). This was what our above sequence was approaching. So somewhat counter-intuitively we have that

lim ε(Γ0+1,Γ0[n]) != ε(Γ0+1,Γ0)

and ...

Γ0 = ε(0,Γ0) << ε(Γ0,Γ0)

... this serves as a reminder that our intuition is not always so consistent, and we must check it against the rules to make sure we are actually constructing a logical system. It may also be tempting to assume that Γ1 = ε(1,Γ0), since Γ0 = ε(0,Γ0). However in order for this to be truε ε(1,Γ0) has to be a fixed-point of β-->ε(0,β). However this can't be the case since ε(1,Γ0) < ε(0,Γ0+1) << ε(0,ε(1,Γ0)).

Rather what we find is that there are now many many more ordinal functions possible than before. We can begin by establishing the function β-->ε(β,Γ0). We have ...

ε(β+1,Γ0)[n] = ε(ε(β,Γ0)+1,Γ0[n])

ε(λ,Γ0)[n] = ε(λ[n],Γ0)

This makes it possible to speak of ε(2,Γ0) , ε(3,Γ0) , ε(ω,Γ0), ε(ε0,Γ0) , ε(Γ0,Γ0) ,

ε(ε(Γ0,Γ0),Γ0) , ε(ε(ε(Γ0,Γ0),Γ0),Γ0) , ...

The supremum of this sequence is ε(0,Γ0+1). At this point all of the previous rules of the binary epsilon function can carry us forward. We can have ...

ε(0,Γ0+Γ0) , ε(0,ε(1,Γ0)) , ... ε(0,ε(0,Γ0+1)) , ε(0,ε(0,ε(0,Γ0+1))) , ...

finally the limit of this sequence is Γ₁. Pretty long way already it seems ... but we're just getting started. Next Γ1 can be extended using all the previously established ordinal functions. So we'll have ...

Γ1+1, ... Γ1+ω , ... Γ1+ε0 ... Γ1+Γ0 ... Γ1+Γ1 ... ω^(Γ1+1) , ε(Γ1+1) , ε(Γ1+1,1) ,

ε(Γ1+1,2) , ... ε(Γ1+1,ω) ... ε(Γ1+1,ε0) ... ε(Γ1+1,Γ0) , ε(Γ1+1,Γ0+1) , ε(Γ1+1,ε(0,Γ0+1)) ,

ε(Γ1+1,ε(0,ε(0,Γ0+1))) ...

of coarse the limit of this sequence is ε(1,Γ1). We can eventually climb out of this to reach ...

ε(2,Γ1) , ε(ω,Γ1) , ... ε(Γ1,Γ1) ... ε(ε(Γ1,Γ1),Γ1) , ε(ε(ε(Γ1,Γ1),Γ1),Γ1) , ... ε(0,Γ1+1) ...

ε(0,Γ1+2) ... ε(0,Γ1+Γ1) ... ε(0,ε(0,Γ1+1)) ... ε(0,ε(0,ε(0,Γ1+1))) ...

The limit of this sequence is Γ2. You should get the jist. We can construct a sequence of fixed-points enumerated Γ-function. So we can have Γ3,Γ4,Γ5, ... we then define the Γ-function for limit ordinals using Γ(λ)[n] = Γ(λ[n]). Thus we can have ...

Γ(ω) ... Γ(ω+ω) ... Γ(ω^2) ... Γ(ω^ω) ... Γ(ε0) ... Γ(Γ0) ... ΓΓΓ0 , ΓΓΓΓ0 , ΓΓΓΓΓ0 , ...

This brings us to the limits of gamma-notation, and the first fixed-point of the gamma function! As you can see we have quickly exhausted the usefulness of the gamma-function, and something much more extensible is needed to reach the Ackermann Ordinal, the small Veblen Ordinal, and beyond. At this point I'll now introduce the ternary-epsilon function, and show how it provides ordinal notations for the fixed-points of the gamma-function and well beyond ...

Ternary-Epsilon Function