Fast Growing Hierarchy
The fast growing hierarchy (shortened to FGH) is a method of defining large numbers. It takes in two inputs.
We define f(0,n) = n+1. For example: f(0,3) = 4. Next step is iteration. f(1,n) is f(0,f(0...f(0,n)...)) where f(0,...) is iterated n times. For example, f(1,2) = f(0,f(0,2)) = 4. Same rules for f(m,n).
Now let's define what ordinals are. Very simplified, they're a kind of infinity.
Consider this: |||....|
This has infinite sticks, but there's a 1st stick, 2nd stick... the last stick is the ωth stick. You can have ω+1, ω+2, ω+3 etc too. For our purposes, a limit ordinal is an ordinal that has no finite part at the end (so ω+3 is not a limit ordinal but ω×3 is.).
So how can we use this within FGH? We need to define a fundamental sequence (FS). An FS is the steps we take to reach a new limit ordinal. So the FS for ω is 0,1,2... and for ω×2 it's ω,ω+1,ω+2...
We can write this as: ωn = n, ω×2n = ω+n, ω^2n = ω×n and so on. There are more ordinals, but it'll do for our purposes.
This is not the only system for an FS. There's more, but I cannot fit it in an entry.
Now consider an ordinal α. Now FGH can be defined concretely:
for f(α,n):
if α is 0, it is n+1.
if α is not a limit ordinal, it is f(α-1,f(α-1...f(α-1,n)...)) where f(α-1,...) is iterated n times.
if α is a limit ordinal, it is f(αn,n).
Let's do an example: f(ω,3) = f(3,3) = f(2,f(2,f(2,3))). I know that f(2,n) = n×2^n, so it's 1.804356 × 10^15151336, which is HUGE! Imagine how large f(ω,10) is.
We define f(0,n) = n+1. For example: f(0,3) = 4. Next step is iteration. f(1,n) is f(0,f(0...f(0,n)...)) where f(0,...) is iterated n times. For example, f(1,2) = f(0,f(0,2)) = 4. Same rules for f(m,n).
Now let's define what ordinals are. Very simplified, they're a kind of infinity.
Consider this: |||....|
This has infinite sticks, but there's a 1st stick, 2nd stick... the last stick is the ωth stick. You can have ω+1, ω+2, ω+3 etc too. For our purposes, a limit ordinal is an ordinal that has no finite part at the end (so ω+3 is not a limit ordinal but ω×3 is.).
So how can we use this within FGH? We need to define a fundamental sequence (FS). An FS is the steps we take to reach a new limit ordinal. So the FS for ω is 0,1,2... and for ω×2 it's ω,ω+1,ω+2...
We can write this as: ωn = n, ω×2n = ω+n, ω^2n = ω×n and so on. There are more ordinals, but it'll do for our purposes.
This is not the only system for an FS. There's more, but I cannot fit it in an entry.
Now consider an ordinal α. Now FGH can be defined concretely:
for f(α,n):
if α is 0, it is n+1.
if α is not a limit ordinal, it is f(α-1,f(α-1...f(α-1,n)...)) where f(α-1,...) is iterated n times.
if α is a limit ordinal, it is f(αn,n).
Let's do an example: f(ω,3) = f(3,3) = f(2,f(2,f(2,3))). I know that f(2,n) = n×2^n, so it's 1.804356 × 10^15151336, which is HUGE! Imagine how large f(ω,10) is.
Fast Growing Hierarchy by cyclopentane December 1, 2022
Get the Fast Growing Hierarchy mug.