ハーディ階層（ハーディかいそう）とは、1972年にスタンリー・S・ウェイナーが定義した計算可能関数の階層である[1]。この階層はグジェゴルチク階層や急成長階層と同様に、順序数 α (≦ ε0) で添え字づけられた関数の族 {hα}α ≦ ε0 を定め、hα を含んで限定再帰および初等的な操作で閉じた集合 { H α } α ≤ ε 0 {\displaystyle \{{\mathcal {H}}_{\alpha }\}_{\alpha \leq \varepsilon _{0}}} として定義される。名称はイギリスの数学者ゴッドフレイ・ハロルド・ハーディに由来する。

ハーディは1904年の論文[2]において連続体濃度の集合から濃度 ℵ 1 {\displaystyle \aleph _{1}} （最小の非可算順序数）の部分集合を構成するために、順序数 α < ℵ 1 {\displaystyle \alpha <\aleph _{1}} と対応付けられた自然数列の族が構成可能であることを示した[注 1]。ウェイナーが定めた関数の族 {hα}α ≦ ε0 はこの論文で使われたアイデアをもとに定義されている[1]。
定義

以下の定義はウェイナーのものに基づく。順序数 α ≦ ε0 に対して、自然数上の関数 h α : N → N {\displaystyle h_{\alpha }\colon \mathbb {N} \to \mathbb {N} } を次のように定義する：

h 0 ( n ) = n h β + 1 ( n ) = h β ( n + 1 ) h α ( n ) = h α [ n ] ( n ) if   α   is   a   limit   ordinal. {\displaystyle {\begin{aligned}h_{0}(n)&=n\\h_{\beta +1}(n)&=h_{\beta }(n+1)\\h_{\alpha }(n)&=h_{\alpha [n]}(n)&{\textrm {if}}\ \alpha \ {\textrm {is}}\ {\textrm {a}}\ {\textrm {limit}}\ {\textrm {ordinal.}}\end{aligned}}}

ただし、極限順序数 α (≦ ε0) と自然数 n に対して α[n] とは以下で定義される順序数である：

α が α = ω β + 1 ⋅ ( γ + 1 ) {\displaystyle \alpha =\omega ^{\beta +1}\cdot (\gamma +1)} と書ける場合、 α [ n ] = ω β + 1 ⋅ γ + ω β ⋅ n {\displaystyle \alpha [n]=\omega ^{\beta +1}\cdot \gamma +\omega ^{\beta }\cdot n} 。

α が α = ω β ⋅ ( γ + 1 ) {\displaystyle \alpha =\omega ^{\beta }\cdot (\gamma +1)} （β は極限順序数）と書ける場合、 α [ n ] = ω β ⋅ γ + ω β [ n ] {\displaystyle \alpha [n]=\omega ^{\beta }\cdot \gamma +\omega ^{\beta [n]}} 。

α = ε0 の場合、 α [ 0 ] = 1 ,   α [ n + 1 ] = ω α [ n ] {\displaystyle \alpha [0]=1,\ \alpha [n+1]=\omega ^{\alpha [n]}} 。

計算可能関数の集合 H α {\displaystyle {\mathcal {H}}_{\alpha }} は、hα を含み、ゼロ関数・後者関数・射影関数・限定的な関数の合成[注 2]・限定再帰で閉じた最小の集合として定義される（グジェゴルチク階層も参照）。
性質

（Wainer 1972, Gallier 1991）順序数 α と β に対して、 h α + β ( n ) = h α ( h β ( n ) ) {\displaystyle h_{\alpha +\beta }(n)=h_{\alpha }(h_{\beta }(n))}

（Gallier 1991, §12）ハーディ階層を定める関数 hα と急成長階層を定める関数 fα について、 H ω α ( n ) = f α ( n ) {\displaystyle H_{\omega ^{\alpha }}(n)=f_{\alpha }(n)} f ε 0 ( n − 1 ) ≤ h ε 0 ( n ) ≤ f ε 0 ( n + 1 ) {\displaystyle f_{\varepsilon _{0}}(n-1)\leq h_{\varepsilon _{0}}(n)\leq f_{\varepsilon _{0}}(n+1)}