ハーディ階層
ハーディ階層(ハーディかいそう)とは、1972年にスタンリー・S・ウェイナーが定義した計算可能関数の階層である。この階層はグジェゴルチク階層や急成長階層と同様に、順序数 α (≦ ε0) で添え字づけられた関数の族 {hα}α ≦ ε0 を定め、hα を含んで限定再帰および初等的な操作で閉じた集合 { H α } α ≤ ε 0 {\displaystyle \{{\mathcal {H}}_{\alpha }\}_{\alpha \leq \varepsilon _{0}}} として定義される。名称はイギリスの数学者ゴッドフレイ・ハロルド・ハーディに由来する。
ハーディは1904年の論文において連続体濃度の集合から濃度 א 1 {\displaystyle \aleph _{1}} (最小の非可算順序数)の部分集合を構成するために、順序数 α < א 1 {\displaystyle \alpha <\aleph _{1}} と対応付けられた自然数列の族が構成可能であることを示した。ウェイナーが定めた関数の族 {hα}α ≦ ε0 はこの論文で使われたアイデアをもとに定義されている。
α が α = ω β + 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α を含み、ゼロ関数・後者関数・射影関数・限定的な関数の合成・限定再帰で閉じた最小の集合として定義される(グジェゴルチク階層も参照)。