ハーディ階層

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

ハーディは1904年の論文において連続体濃度の集合から濃度 （最小の非可算順序数）の部分集合を構成するために、順序数 と対応付けられた自然数列の族が構成可能であることを示したただし具体的に自然数列を構成するためには、全ての可算極限順序数 に対して を満たす順序数列 を与える必要がある。。ウェイナーが定めた関数の族 はこの論文で使われたアイデアをもとに定義されている。

定義 以下の定義はウェイナーのものに基づく。順序数 に対して、自然数上の関数 を次のように定義する：

ただし、極限順序数 と自然数 に対して とは以下で定義される順序数である：

が と書ける場合、。 が （ は極限順序数）と書ける場合、。 の場合、。

計算可能関数の集合 は、 を含み、ゼロ関数・後者関数・射影関数・限定的な関数の合成限定再帰と同様に、合成された関数が同じ階層に属する別の関数で上から抑えられるもののみを考える。・限定再帰で閉じた最小の集合として定義される（グジェゴルチク階層も参照）。

性質

（, ）順序数 と に対して、 （）ハーディ階層を定める関数 と急成長階層を定める関数 について、 () 順序数 が を満たすならば、急成長階層 について

脚注

注釈

参考文献

外部リンク