ハーディ階層

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

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

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

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

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

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

性質 

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

脚注

注釈

参考文献

外部リンク 

巨大数
計算可能性理論
数学に関する記事