ハーディ階層

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

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

定義

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

${\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}}$

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

• α が $\alpha =\omega ^{\beta +1}\cdot (\gamma +1)$ と書ける場合、$\alpha [n]=\omega ^{\beta +1}\cdot \gamma +\omega ^{\beta }\cdot n$。
• α が $\alpha =\omega ^{\beta }\cdot (\gamma +1)$ （β は極限順序数）と書ける場合、$\alpha [n]=\omega ^{\beta }\cdot \gamma +\omega ^{\beta [n]}$。
• α = ε₀ の場合、$\alpha [0]=1,\ \alpha [n+1]=\omega ^{\alpha [n]}$。

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

性質

• （Wainer 1972, Gallier 1991）順序数 α と β に対して、
  $$h_{\alpha +\beta }(n)=h_{\alpha }(h_{\beta }(n))$$
• （Gallier 1991, §12）ハーディ階層を定める関数 h_α と急成長階層を定める関数 f_α について、
  $$H_{\omega ^{\alpha }}(n)=f_{\alpha }(n)$$
  $$f_{\varepsilon _{0}}(n-1)\leq h_{\varepsilon _{0}}(n)\leq f_{\varepsilon _{0}}(n+1)$$
• (Wainer 1972, p. 286) 順序数 α が 1 < α < ε₀ を満たすならば、急成長階層 ${\mathcal {F}}_{\alpha }$ について
  $${\mathcal {F}}_{\alpha }=\bigcup \nolimits _{\beta <\omega ^{\alpha +1}}{\mathcal {H}}_{\beta }$$

脚注

参考文献

• Gallier, Jean H. (1991), “What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory”, Annals of Pure and Applied Logic (Elsevier B-V.) 53 (3): 199-260, doi:10.1016/0168-0072(91)90022-E