急成長階層

急成長階層(きゅうせいちょうかいそう、英: fast-growing hierarchy)および拡張グジェゴルチク階層 (かくちょうグジェゴルチクかいそう、英: extended Grzegorczyk hierarchy)とは、1970年にマーティン・レーペ(Martin Löb)とスタンリー・S・ウェイナーによって定義された^[1] 、最大 ${\displaystyle \aleph _{1}}${\displaystyle \aleph _{1}} 層からなる計算可能関数の階層である。急成長階層の定義にはいくつかのバージョンがあるが、特にウェイナーが α ≦ ε₀ の範囲について1972年の論文^[2] で定義し、ケトネンとソロヴェイが簡略化した^[3] バージョンをウェイナー階層(英: Wainer hierarchy)と呼ぶ^[4] 。

急成長階層の定義に登場する、可算な順序数で添字づけられた計算可能関数の族 ${\displaystyle \{f_{\alpha }\}_{\alpha <\tau }}${\displaystyle \{f_{\alpha }\}_{\alpha <\tau }}(τ は適当な極限順序数)を急増加関数と呼ぶ。

以下の関数 f_α の定義はケトネンとソロヴェイの論文^[3] による。極限順序数 α の基本列とは、自然数で添え字づけられた順序数の単調増加列 {α_n}_{n < ω} であって α に収束するものである。

極限順序数 α (≦ ε₀) と自然数 n に対して α[n] を以下で定義する:

• α が ${\displaystyle \alpha =\omega ^{\beta +1}\cdot (\gamma +1)}${\displaystyle \alpha =\omega ^{\beta +1}\cdot (\gamma +1)} と書ける場合、${\displaystyle \alpha [n]=\omega ^{\beta +1}\cdot \gamma +\omega ^{\beta }\cdot n}${\displaystyle \alpha [n]=\omega ^{\beta +1}\cdot \gamma +\omega ^{\beta }\cdot n}。
• α が ${\displaystyle \alpha =\omega ^{\beta }\cdot (\gamma +1)}${\displaystyle \alpha =\omega ^{\beta }\cdot (\gamma +1)} (β は極限順序数)と書ける場合、${\displaystyle \alpha [n]=\omega ^{\beta }\cdot \gamma +\omega ^{\beta [n]}}${\displaystyle \alpha [n]=\omega ^{\beta }\cdot \gamma +\omega ^{\beta [n]}}。
• α = ε₀ の場合、${\displaystyle \alpha [0]=1,\ \alpha [n+1]=\omega ^{\alpha [n]}}${\displaystyle \alpha [0]=1,\ \alpha [n+1]=\omega ^{\alpha [n]}}。

順序数 α (≦ ε₀) に対して、自然数上の関数 ${\displaystyle f_{\alpha }:\mathbb {N} \to \mathbb {N} }${\displaystyle f_{\alpha }:\mathbb {N} \to \mathbb {N} } を次のように定義する:

• ${\displaystyle f_{0}(n)=n+1}${\displaystyle f_{0}(n)=n+1}
• ${\displaystyle f_{\alpha +1}(n)=f_{\alpha }^{1+n}(n)}${\displaystyle f_{\alpha +1}(n)=f_{\alpha }^{1+n}(n)}
• ${\displaystyle f_{\alpha }(n)=f_{\alpha [n]}(n)}${\displaystyle f_{\alpha }(n)=f_{\alpha [n]}(n)} (α が極限順序数の場合)

ただし n > 0 に対して${\displaystyle f_{\alpha }^{n}(n)=\underbrace {f_{\alpha }(f_{\alpha }(\dots (f_{\alpha }(n))\dots ))} _{n}}${\displaystyle f_{\alpha }^{n}(n)=\underbrace {f_{\alpha }(f_{\alpha }(\dots (f_{\alpha }(n))\dots ))} _{n}}とする。

計算可能関数の集合 ${\displaystyle {\mathcal {F}}_{\alpha }}${\displaystyle {\mathcal {F}}_{\alpha }}は、f_α を含み、ゼロ関数・後者関数・射影関数・関数の合成・限定再帰で閉じた最小の集合として定義される(グジェゴルチク階層も参照)。

• f₀(n)=n+1
• f₁(n)=f₀ⁿ(n)=n+(1·n)=2n
• f₂(n)=f₁ⁿ(n)=2(2(...2(n)...))=2ⁿn>2↑n (クヌースの矢印表記 を参照)
• f₃(n)=f₂ⁿ(n)>2↑↑n
• f_ω(n)=f_n-1ⁿ(n)>2 ↑^n-1 n ≒ {n,n,n-1} (配列表記・BEAF を参照)

• 巨大数
• 順序数
• ハーディ階層
• 緩成長階層

1. ^ Löb, M. H.; Wainer, S. S. (1970年03月01日). "Hierarchies of number-theoretic functions. I" (英語). Archiv für mathematische Logik und Grundlagenforschung 13 (1): 39–51. doi:10.1007/BF01967649. ISSN 1432-0665 . https://doi.org/10.1007/BF01967649 . 
2. ^ Wainer, S. S. (1972). "Ordinal Recursion, and a Refinement of the Extended Grzegorczyk Hierarchy". The Journal of Symbolic Logic 37 (2): 281–292. doi:10.2307/2272973. ISSN 0022-4812 . https://www.jstor.org/stable/2272973 . 
3. ^ ^{a b} Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". Annals of Mathematics 113 (2): 267–314. doi:10.2307/2006985. ISSN 0003-486X . https://www.jstor.org/stable/2006985 . 
4. ^ "Fast growing functions based on Ramsey theorems" (英語). Discrete Mathematics 95 (1-3): 341–358. (1991年12月03日). doi:10.1016/0012-365X(91)90346-4. ISSN 0012-365X . https://www.sciencedirect.com/science/article/pii/0012365X91903464 . 

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

• すべてのスタブ記事
• 数学関連のスタブ項目