ハーディ階層

ハーディ階層（ハーディかいそう）とは、1972年にスタンリー・S・ウェイナーが定義した計算可能関数の階層である。この階層はグジェゴルチク階層や急成長階層と同様に、順序数 で添え字づけられた関数の族 を定め、 を含んで限定再帰および初等的な操作で閉じた集合 formula_1として定義される。名称はイギリスの数学者ゴッドフレイ・ハロルド・ハーディに由来する。
ハーディは1904年の論文において連続体濃度の集合から濃度 formula_2（最小の非可算順序数）の部分集合を構成するために、順序数 formula_3 と対応付けられた自然数列の族が構成可能であることを示した。ウェイナーが定めた関数の族 はこの論文で使われたアイデアをもとに定義されている。
定義.
以下の定義はウェイナーのものに基づく。順序数 に対して、自然数上の関数 formula_4 を次のように定義する：
formula_5
ただし、極限順序数 と自然数 に対して とは以下で定義される順序数である：
計算可能関数の集合 formula_11 は、 を含み、ゼロ関数・後者関数・射影関数・限定的な関数の合成・限定再帰で閉じた最小の集合として定義される（グジェゴルチク階層も参照）。