Home > Number theory > Abstract number theory

The Fast-growing Hierarchy

The fast-growing hierarchy is a function mapping ordinals to functions. What this means is that it is simply a collection of functions. Each one is always increasing and each one grows faster and faster than the last. In fact, these functions increase in value so rapidly that we lack the ability to write it out before long.

It starts simply enough...

1: f₀(n) = n+1

2: f_a+1(n) = f_aⁿ(n)

3: f_a^b+1(n) = f_a^b(f_a(n))

4: f_a¹(n) = f_a(n)

5: f_l(n) = f_l[n](n) (From here onwards l is a limit ordinal)

Ignore rule 5 for now. So what is f₁(n)? It is equal to f₀(f₀(...(n)...)) with n f₀s. This is equivalent to 2n. So far, nothing too spectacular. f₁(100) = 200. But what about f₂(n)? This is a bit more complex. When solved, it is equal to n2ⁿ. f₂(100) has 33 digits. The exact value is 126765060022822940149670320537600. Still, this is nothing compared to even a googol. To go further, recursion is our only tool. Each step is roughly equivalent to adding an up-arrow in the Knuth system. But we can go further.

The first limit ordinal is ω. To form it, it can simply be noted that it is the limit of natural numbers. Thus ω[n] = n. f_ω(n) = f_n(n). This is the limit of up-arrows. But we can still go further with ω+1, ω+2, and so on. We can reach ω + ω = ω*2 (not 2*ω as this is approximately equal to ω) and then add ω again to get ω*3 and so on. We need more rules.

6: ω[n] = n

7: a+(b+1) = (a+b)+1

8: (a+l)[n] = a+l[n]

9: a*(b+1) = a*b + a

10: a*1 = a

11: (a+l)[n] = a+l[n]

Rule 7 deals with addition involving limit ordinals while rules 8 and 9 deal with multiplication. However, we can go further still. ω^2 = ω*ω = ω*n. This allows exponentiation to be defined.

12: a^(b+1) = (a^b)*a

13: a^1 = a

14: (a^l)[n] = a^l[n]

Now we can have huge power towers of ω e.g. ω^(ω^(ω^ω)). But all this has to have a limit. This limit is known as epsilon-zero. Of course, we can extend this beyond even that but it would require ever more complex functions. A simplified theta function could extend this, but even it is fairly complex.

15: θ(0,a) = ω^a

16: ω^0 = 1

17: θ(a+1,b+1)[1] = θ(a+1,b)+1

18: θ(a+1,0)[1] = θ(a,0)

19: θ(a+1,b)[n+1] = θ(a,θ(a+1,b)[n])

20: θ(l,a)[n] = θ(l[n],a)

21: θ(a,l)[n] = θ(a,l[n])

We can express epsilon numbers now. θ(1,0) = ε0. Also, θ(1,1) = ε1, θ(1,2) = ε2, and in general, θ(1,a) = εa. Each epsilon number adds one to the last before putting it in a power tower of ωs. We can go much further, though. θ(2,0) is Cantor's ordinal, and is equal to ε(ε(ε…(ε0)...)) with ω εs. We can go on with θ(2,1), θ(3,0), θ(4,0), θ(ω,0), θ(θ(1,0),0), and so on. The limit of this is the Feferman-Schutte ordinal. We need the full theta function to surpass this. It allows for uncountable arguments. Ω is used, being the first uncountable ordinal. It results in a recursion on the theta function.

22: θ(a+Ω,0)[1] = θ(a,0)

23: θ(a+Ω,b+1)[1] = θ(a+Ω,b)

24: θ(a+Ω,b)[n+1] = θ(a+θ(a+Ω,b)[n],b)

25: θ(a*Ω,0)[1] = θ(a,0)

26: θ(a*Ω,b+1)[1] = θ(a*Ω,b)

27: θ(a*Ω,b)[n+1] = θ(a*θ(a*Ω,b)[n],b)

28: θ(a^Ω,0)[1] = θ(a,0)

29: θ(a^Ω,b+1)[1] = θ(a^Ω,b)

30: θ(a^Ω,b)[n+1] = θ(a^θ(a^Ω,b)[n],b)

These simple rules enable us to go beyond the Feferman Schutte ordinal, which is θ(Ω,0). This is the ordinal strength of many formal systems, but Peano arithmetic falls below, at epsilon zero. Ordinals do get bigger than even this, and so we can continue with, for example, θ(Ω*2,0). Also possible is θ(Ω^2,0), the Ackermann ordinal. The Veblen ordinals can also be expressed, the small Veblen ordinal being θ(Ω^ω,0) and the large one being θ(Ω^Ω,0). Large power towers of Ω lead to ever larger ordinals, limiting at the Bachmann-Howard ordinal. This is also the ordinal strength of various formal systems such as Kripke-Platek set theory, although Zermelo-Fraenkel set theory has a higher ordinal. It is not yet known what the true ordinal strength of ZFC is.

Related entries

• Large numbers

• Hydras