Hardy Hardy Hardy Wainer Wainer Wainer

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:

• H₀(n) = n
• H_a+1(n) = H_a(n+1)
• H_a(n) = H_a[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.

Evidently:

• H₀(n) = n
• H₁(n) = n + 1
• H₂(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 H_a+1(n) = H_a(n+1). So for a = ω, H_{ω + 1}(n) = 2(n + 1) = 2n + 2.

Continuing!

• H_{ω + m}(n) = 2(n + m)
• H_ω2(n) = 4n
• H_ω3(n) = 8n
• H_ωm(n) = 2^mn
• H_ω²(n) = 2ⁿn (remember? this is equivalent to f₂(n))
• H_ω³(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
• (ω^a₁+ω^a₂+ω^a₃+ω^a₄+ω^a₅+…+ω^a_k)[n] = ω^a₁+ω^a₂+ω^a₃+ω^a₄+ω^a₅+…+ω^a_k[n] where a₁≥a₂≥…≥a_k
• ε₀[0] = 0 (alternatively 1)
• ε₀[n+1] = ω^ε₀[n] = ω ↑↑ (n-1) (alternatively ω ↑↑ n)

It’s oddly weird.

Next time, I’ll talk about the Veblen and Buchholz hierarchies.

Toodle-oo!