「急成長階層」の版間の差分

削除された内容追加された内容

インライン

2021年6月15日 (火) 17:49時点における版

急成長階層（きゅうせいちょうかいそう、英: fast-growing hierarchy、急増加関数（きゅうぞうかかんすう）とも訳される）および拡張グジェゴルチク階層（かくちょうグジェゴルチクかいそう、英: extended Grzegorczyk hierarchy）とは、1970年にマーティン・レーペ（Martin Löb）とスタンリー・S・ウェイナーによって定義された^[1]、最大 $\aleph _{1}$ 層からなる計算可能関数の階層である。

急成長階層の定義にはいくつかのバージョンがあるが、特にウェイナーが $α ≦ ε 0$ の範囲について1972年の論文^[2]で定義し、ケトネンとソロヴェイが簡略化した^[3]バージョンをウェイナー階層（英: Wainer hierarchy）と呼ぶ^[4]。

定義

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

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

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

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

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

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

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

例

$(\omega ^{\omega }+{\omega ^{\omega ^{\omega ^{\omega +1}+{\omega }+2}}})[n]=\omega ^{\omega }+{\omega ^{\omega ^{\omega ^{\omega +1}+{\omega }+2}}}[n]$ (1.を使用)

${\textstyle \omega ^{\omega }+{\omega ^{\omega ^{\omega ^{\omega +1}+{\omega }+2}}}[n]=\omega ^{\omega }+{\omega ^{(\omega ^{\omega ^{\omega +1}+{\omega }+2})[n]}}}$ (3.を使用)

${\textstyle \qquad \qquad \qquad \qquad \,=\omega ^{\omega }+{\omega ^{(\omega ^{(\omega ^{\omega +1}+{\omega }+1)+1})[n]}}}$

${\textstyle \qquad \qquad \qquad \qquad \,=\omega ^{\omega }+{\omega ^{(\omega ^{(\omega ^{\omega +1}+{\omega }+1)})n}}}$ (2.を使用)

他の巨大数の表記法との比較

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 を参照)

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

^ 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.
^ 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.
^ ^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.
^ “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.

[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.

[:0-3] 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.

[1]

[2]

[3]

[4]

@@ 1行目: / 1行目: @@
-'''急成長階層'''(きゅうせいちょうかいそう、{{Lang-en-short|fast-growing hierarchy}}、'''急増加関数'''(きゅうぞうかかんすう)とも訳される)および'''拡張[[グジェゴルチク階層]]'''(かくちょうぐじぇごるちくかいそう、{{Lang-en-short|extended Grzegorczyk hierarchy}})とは、[[順序数]] α に対して ''f<sub>α</sub>'': '''N''' → '''N''' （ '''N''' は [[自然数]] )を定める関数の階層である。最も標準的なものは、全てのα< ε<sub>0</sub>に対しての拡張である '''Wainer階層'''である。
+'''急成長階層'''（きゅうせいちょうかいそう、{{Lang-en-short|fast-growing hierarchy}}、'''急増加関数'''（きゅうぞうかかんすう）とも訳される）および'''拡張[[グジェゴルチク階層]]'''（かくちょうグジェゴルチクかいそう、{{Lang-en-short|extended Grzegorczyk hierarchy}}）とは、1970年にマーティン・レーペ（[[:en:Martin Löb|Martin Löb]]）とスタンリー・S・ウェイナーによって定義された<ref>{{Cite journal|last=Löb|first=M. H.|last2=Wainer|first2=S. S.|date=1970-03-01|title=Hierarchies of number-theoretic functions. I|url=https://doi.org/10.1007/BF01967649|journal=Archiv für mathematische Logik und Grundlagenforschung|volume=13|issue=1|pages=39–51|language=en|doi=10.1007/BF01967649|issn=1432-0665}}</ref>、最大 <math>\aleph_{1}</math> 層からなる[[計算可能関数]]の階層である。
+急成長階層の定義にはいくつかのバージョンがあるが、特にウェイナーが {{Math|''α'' ≦ ''ε''<sub>0</sub>}} の範囲について1972年の論文<ref>{{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|doi=10.2307/2272973|issn=0022-4812}}</ref>で定義し、ケトネンとソロヴェイが簡略化した<ref name=":0">{{Cite journal|last=Ketonen|first=Jussi|last2=Solovay|first2=Robert|date=1981|title=Rapidly Growing Ramsey Functions|url=https://www.jstor.org/stable/2006985|journal=Annals of Mathematics|volume=113|issue=2|pages=267–314|doi=10.2307/2006985|issn=0003-486X}}</ref>バージョンを'''ウェイナー階層'''（{{Lang-en-short|Wainer hierarchy}}）と呼ぶ<ref>{{Cite journal|date=1991-12-03|title=Fast growing functions based on Ramsey theorems|url=https://www.sciencedirect.com/science/article/pii/0012365X91903464|journal=Discrete Mathematics|volume=95|issue=1-3|pages=341–358|language=en|doi=10.1016/0012-365X(91)90346-4|issn=0012-365X}}</ref>。
 == 定義 ==
+以下の関数 {{Math|''f''<sub>''α''</sub>}} の定義はケトネンとソロヴェイの論文<ref name=":0" />による。極限順序数 {{Math|''α''}} の基本列とは、自然数で添え字づけられた順序数の単調増加列 {{Math|{''α''<sub>''n''</sub>}<sub>''n'' < ''ω''</sub>}} であって {{Math|''α''}} に収束するものである。
-急成長階層''f<sub>α</sub>''は、次のように定義される。
+極限順序数 {{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|''α'' (≦ ''ε''<sub>0</sub>)}} に対して、自然数上の関数 <math>f_{\alpha}:\mathbb{N}\to \mathbb{N}</math> を次のように定義する：
-<math>\begin{align}
-&f_{0}(n)=n+1\\
-&f_{\alpha+1}(n)=f^n_{\alpha}(n)\\
-&f_\alpha(n)=f_{\alpha[n]}(n)
-\end{align}</math>
+* <math>f_{0}(n)=n+1</math>
-ここで、<math>f^n_\alpha(n)=\underbrace{ f_\alpha(f_\alpha(\dots(f_\alpha(n))\dots)) }_{n}</math>とし、<math>\alpha[n] </math>は、極限順序数αの基本列のn番目とする。
+* <math>f_{\alpha+1}(n)=f_{\alpha}^{1+n}(n)</math>
+* <math>f_{\alpha}(n)=f_{\alpha[n]}(n)</math>　（{{Math|''α''}} が極限順序数の場合）
+ただし {{Math|''n'' > 0}} に対して<math>f^n_\alpha(n)=\underbrace{ f_\alpha(f_\alpha(\dots(f_\alpha(n))\dots)) }_{n}</math>とする。
-== Wainer階層 ==
-Wainer階層は、α ≤ ε<sub>0</sub>となるαに対し、次のように基本列を定義する事によって得られる急成長階層である。
+計算可能関数の集合 <math>\mathcal{F}_{\alpha}</math>は、{{Math|''f''<sub>''α''</sub>}} を含み、ゼロ関数・後者関数・射影関数・関数の合成・限定再帰で閉じた最小の集合として定義される（[[グジェゴルチク階層]]も参照）。
-カントール標準形で書かれている極限順序数λ<ε<sub>0</sub> の基本列λ[n]は
+==例==
-# λ=ω<sup>α<sub>1</sub></sup>+...+ω<sup>α<sub>k-1</sub></sup>+ω<sup>α<sub>k</sub></sup> のとき、 λ[n]=ω<sup>α<sub>1</sub></sup>+...+ω<sup>α<sub>k-1</sub></sup>+ω<sup>α<sub>k</sub></sup>[n] (但し、α<sub>1</sub>≥...≥α<sub>k-1</sub>≥α<sub>k</sub>)
-# λ=ω<sup>α+1</sup>のとき、λ[n]=ω<sup>α</sup>n
-#λ=ω<sup>α</sup>(αは極限順序数)のとき、λ[n]=ω<sup>α[n]</sup>
-#λ=ε<sub>0</sub>のとき、基本列λ[n]は、
-* λ[0]=1
-* λ[n+1]=ω<sup>λ[n]</sup>
-===例===
 <math>
 (\omega^\omega+{\omega^{\omega^{\omega^{\omega+1}+{\omega}+2}}})[n]=\omega^\omega+{\omega^{\omega^{\omega^{\omega+1}+{\omega}+2}}}[n]