ハーディ階層

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

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

定義

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

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

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

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

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

性質

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

  
• （Gallier 1991, §12）ハーディ階層を定める関数 h_α と急成長階層を定める関数 f_α について、
  $${\displaystyle H_{\omega ^{\alpha }}(n)=f_{\alpha }(n)}$$

  
  $${\displaystyle f_{\varepsilon _{0}}(n-1)\leq h_{\varepsilon _{0}}(n)\leq f_{\varepsilon _{0}}(n+1)}$$

  
• (Wainer 1972, p. 286) 順序数 α が 1 < α < ε₀ を満たすならば、急成長階層 ${\displaystyle {\mathcal {F}}_{\alpha }}$ について
  $${\displaystyle {\mathcal {F}}_{\alpha }=\bigcup \nolimits _{\beta <\omega ^{\alpha +1}}{\mathcal {H}}_{\beta }}$$

  

脚注

注釈

1. ^ ただし具体的に自然数列を構成するためには、全ての可算極限順序数 α に対して lim_n→ωα_n = α を満たす順序数列 α_n を与える必要がある。
2. ^ 限定再帰と同様に、合成された関数が同じ階層に属する別の関数で上から抑えられるもののみを考える。

参考文献

• 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 

外部リンク