ハーディ階層

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

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

定義

以下の定義はウェイナーのものに基づく。順序数 テンプレート:Math に対して、自然数上の関数 $h_{\alpha }:\mathbb{N}\to \mathbb{N}$ を次のように定義する：

$\begin{array}{cc}{h}_0(n)& =n\\ h_{\beta +1}(n)& =h_{\beta }(n+1)\\ h_{\alpha }(n)& =h_{\alpha [n]}(n)& \text{if}\alpha \text{is}\text{a}\text{limit}\text{ordinal.}\end{array}$

ただし、極限順序数 テンプレート:Math と自然数 テンプレート:Mvar に対して テンプレート:Math とは以下で定義される順序数である：

• テンプレート:Math が $\alpha ={\omega }^{\beta +1}\cdot (\gamma +1)$ と書ける場合、$\alpha [n]={\omega }^{\beta +1}\cdot \gamma +{\omega }^{\beta }\cdot n$。
• テンプレート:Math が $\alpha ={\omega }^{\beta }\cdot (\gamma +1)$ （テンプレート:Math は極限順序数）と書ける場合、$\alpha [n]={\omega }^{\beta }\cdot \gamma +{\omega }^{\beta [n]}$。
• テンプレート:Math の場合、$\alpha [0]=1,\alpha [n+1]={\omega }^{\alpha [n]}$。

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

性質

• （テンプレート:Harvnb, テンプレート:Harvnb）順序数 テンプレート:Math と テンプレート:Math に対して、$$h_{\alpha +\beta }(n)=h_{\alpha }(h_{\beta }(n))$$
• （テンプレート:Harvnb）ハーディ階層を定める関数 テンプレート:Math と急成長階層を定める関数 テンプレート:Math について、$$H_{{\omega }^{\alpha }}(n)=f_{\alpha }(n)$$$$f_{{\epsilon }_0}(n-1)\le h_{{\epsilon }_0}(n)\le f_{{\epsilon }_0}(n+1)$$
• (テンプレート:Harvnb) 順序数 テンプレート:Math が テンプレート:Math を満たすならば、急成長階層 ${ℱ}_{\alpha }$ について$${ℱ}_{\alpha }=\bigcup _{\beta <{\omega }^{\alpha +1}}{\mathscr{H}}_{\beta }$$

脚注

参考文献

• テンプレート:Citation