ハーディ階層

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

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

以下の定義はウェイナーのものに基づく。順序数 $α ≦ ε 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}}$

ただし、極限順序数 $α (≦ ε 0)$ と自然数 $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]}$ 。
$α = ε 0$ の場合、 $\alpha [0]=1,\ \alpha [n+1]=\omega ^{\alpha [n]}$ 。

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

性質

（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 < α < ε 0$ を満たすならば、急成長階層 ${\mathcal {F}}_{\alpha }$ について ${\mathcal {F}}_{\alpha }=\bigcup \nolimits _{\beta <\omega ^{\alpha +1}}{\mathcal {H}}_{\beta }$

ハーディ階層

性質

脚注

注釈

参考文献

外部リンク

Related Articles