ハーディ階層のソースを表示

'''ハーディ階層'''（ハーディかいそう）とは、1972年にスタンリー・S・ウェイナーが定義した[[計算可能関数]]の階層である<ref name=":0">{{Cite journal|last=Wainer|first=S. S.|date=1972|title=Ordinal Recursion, and a Refinement of the Extended Grzegorczyk Hierarchy|url=https://www.jstor.org/stable/2272973|journal=The Journal of Symbolic Logic|volume=37|issue=2|pages=281–292|ref=harv|doi=10.2307/2272973|issn=0022-4812}}</ref>。この階層は[[グジェゴルチク階層]]や[[急成長階層]]と同様に、順序数 {{Math|''α'' (≦ ''ε''<sub>0</sub>)}} で添え字づけられた関数の族 {{Math|{''h''<sub>''α''</sub>}<sub>''α'' ≦ ''ε''<sub>0</sub></sub>}} を定め、{{Math|''h''<sub>''α''</sub>}} を含んで限定再帰および初等的な操作で閉じた集合 <math>\{\mathcal{H}_{\alpha}\}_{\alpha\leq\varepsilon_{0}}</math>として定義される。名称はイギリスの数学者[[ゴッドフレイ・ハロルド・ハーディ]]に由来する。

ハーディは1904年の論文<ref>{{Cite journal|last=Hardy|first=G. H.|author-link=ゴッドフレイ・ハロルド・ハーディ|year=1904|title=A THEOREM CONCERNING THE INFINITE CARDINAL NUMBERS|journal=Quarterly Journal of Mathematics|volume=35|pages=87-94}}</ref>において[[連続体濃度]]の集合から濃度 <math>\aleph_{1}</math>（[[最小の非可算順序数]]）の部分集合を構成するために、順序数 <math>\alpha<\aleph_{1}</math> と対応付けられた自然数列の族が構成可能であることを示した<ref group="注">ただし具体的に自然数列を構成するためには、'''全ての'''可算極限順序数 {{Math|''α''}} に対して {{Math|1=lim<sub>''n''→''ω''</sub>''α''<sub>''n''</sub> = ''α''}} を満たす順序数列 {{Math|''α''<sub>''n''</sub>}} を与える必要がある。</ref>。ウェイナーが定めた関数の族 {{Math|{''h''<sub>''α''</sub>}<sub>''α'' ≦ ''ε''<sub>0</sub></sub>}} はこの論文で使われたアイデアをもとに定義されている<ref name=":0" />。

== 定義 ==
以下の定義はウェイナーのものに基づく。順序数 {{Math|''α'' ≦ ''ε''<sub>0</sub>}} に対して、自然数上の関数 <math>h_{\alpha}\colon\mathbb{N}\to\mathbb{N}</math> を次のように定義する：

<math>\begin{align}
    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{align}</math>

ただし、極限順序数 {{Math|''α'' (≦ ''ε''<sub>0</sub>)}} と自然数 {{Mvar|n}} に対して {{Math|''α''[''n'']}} とは以下で定義される順序数である：

* {{Math|''α''}} が <math>\alpha=\omega^{\beta+1}\cdot(\gamma+1)</math> と書ける場合、<math>\alpha[n]=\omega^{\beta+1}\cdot\gamma+\omega^{\beta}\cdot n</math>。
* {{Math|''α''}} が <math>\alpha=\omega^{\beta}\cdot(\gamma+1)</math> （{{Math|''β''}} は極限順序数）と書ける場合、<math>\alpha[n]=\omega^{\beta}\cdot\gamma+\omega^{\beta[n]}</math>。
*{{Math|1=''α'' = ''ε''<sub>0</sub>}} の場合、<math>\alpha[0]=1,\ \alpha[n+1]=\omega^{\alpha[n]}</math>。

計算可能関数の集合 <math>\mathcal{H}_{\alpha}</math> は、{{Math|''h''<sub>''α''</sub>}} を含み、ゼロ関数・後者関数・射影関数・限定的な関数の合成<ref group="注">[[グジェゴルチク階層#定義|限定再帰]]と同様に、合成された関数が同じ階層に属する別の関数で上から抑えられるもののみを考える。</ref>・限定再帰で閉じた最小の集合として定義される（[[グジェゴルチク階層]]も参照）。

== 性質 ==

* （{{Harvnb|Wainer|1972}}, {{Harvnb|Gallier|1991}}）順序数 {{Math|''α''}} と {{Math|''β''}} に対して、<math display="block">h_{\alpha+\beta}(n)=h_{\alpha}(h_{\beta}(n))</math>
* （{{Harvnb|Gallier|1991|loc=&sect;12}}）ハーディ階層を定める関数 {{Math|''h''<sub>''α''</sub>}} と[[急成長階層]]を定める関数 {{Math|''f''<sub>''α''</sub>}} について、<math display="block">H_{\omega^\alpha}(n)=f_{\alpha}(n)</math><math display="block">f_{\varepsilon_0}(n-1)\leq h_{\varepsilon_0}(n)\leq f_{\varepsilon_0}(n+1)</math>
* ({{Harvnb|Wainer|1972|p=286}}) 順序数 {{Math|''α''}} が {{Math|1 < ''α'' < ''ε''<sub>0</sub>}} を満たすならば、[[急成長階層]] <math>\mathcal{F}_{\alpha}</math> について<math display="block">\mathcal{F}_{\alpha}=\bigcup\nolimits_{\beta<\omega^{\alpha+1}}\mathcal{H}_{\beta} </math>

== 脚注 ==

=== 注釈 ===
<references group="注" />

=== 参考文献 ===
{{reflist}}

{{DEFAULTSORT:はあていかいそう}}

* {{Citation|洋書|title=What's so special about Kruskal's theorem and the ordinal {{Math|Γ<sub>0</sub>}}? A survey of some results in proof theory|year=1991|last=Gallier|first=Jean H.|publisher=Elsevier B-V.|volume=53|journal=Annals of Pure and Applied Logic|issue=3|pages=199-260|doi=10.1016/0168-0072(91)90022-E}}

== 外部リンク ==
{{巨大数}}

{{Normdaten}}{{Math-stub}}
[[Category:巨大数]]
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]