Hierarchy Hierarchy Hierarchy
Hardy hierarchy. You remember fast- and slow-growing hierarchy? It’s another one of those.
Honestly, it feels as slow as SGH.
Hardy hierarchy is defined as follows:
- H0(n) = n
- Ha+1(n) = Ha(n+1)
- Ha(n) = Ha[n](n) if a is a limit ordinal
I haven’t fully explained what limit ordinals are, so in the future posts, I’ll explain.
- H0(n) = n
- H1(n) = n + 1
- H2(n) = n + 2
- Hω(n) = 2n
- Hω + 1(n) = 2n + 2
Before we continue, why isn’t it 2n + 1, like other hierarchies? Because the second rule of Hardy hierarchy states that Ha+1(n) = Ha(n+1). So for a = ω, Hω + 1(n) = 2(n + 1) = 2n + 2.
- Hω + m(n) = 2(n + m)
- Hω2(n) = 4n
- Hω3(n) = 8n
- Hωm(n) = 2mn
- Hω2(n) = 2nn (remember? this is equivalent to f2(n))
- Hω3(n) ≈ n↑↑n
You know what? I’ll link the website.
Wainer hierarchy is actually in the FGH website, so I’ll link the section. Fun fact: when people say “Fast Growing Hierarchy”, they can refer to different hierarchies. I’ll cover other hierarchies in future posts.
Wainer Hierarchy is defined as the following:
- ω[n] = n
- ωa+1[n] = ωan where ωan = ωa + ωa + ωa + ωa + ωa + ωa + ωa + ωa + ωa + … n times
- ωa[n] = ωa[n] if and only if a is a limit ordinal
- (ωa1+ωa2+ωa3+ωa4+ωa5+…+ωak)[n] = ωa1+ωa2+ωa3+ωa4+ωa5+…+ωak[n] where a1≥a2≥…≥ak
- ε0 = 0 (alternatively 1)
- ε0[n+1] = ωε0[n] = ω ↑↑ (n-1) (alternatively ω ↑↑ n)
It’s oddly weird.
Next time, I’ll talk about the Veblen and Buchholz hierarchies.