查看“︁急成长阶层”︁的源代码

在[[可计算性理论]]、[[計算複雜性理論|计算复杂性理论]]和[[证明论|证明理论]]中，'''急成长阶层'''（也称为'''扩展Grzegorczyk阶层'''或'''Schwichtenberg-Wainer阶层'''） <ref>{{Cite journal |last=Beklemishev |first=L.D. |date=2003 |title=Proof-theoretic analysis by iterated reflection |url=https://link.springer.com/article/10.1007/s00153-002-0158-7 |journal=Archive for Mathematical Logic |volume=42 |issue=6 |page=515–552 |doi=10.1007/s00153-002-0158-7 |s2cid=10454755 |access-date=2024-03-14 |archive-date=2023-05-13 |archive-url=https://web.archive.org/web/20230513034714/https://link.springer.com/article/10.1007/s00153-002-0158-7 |dead-url=no }}</ref>是一类定义域和值域为自然数集，以序数作为索引的函数，即急成长函数''f''<sub>α</sub>: '''N''' → '''N'''构成的集合（其中'''N'''是[[自然数]]集 {0, 1, ...}，并且索引 α 的范围可达某个大的可数[[序数]]）。例如：'''Wainer阶层'''，或'''Löb–Wainer阶层'''是所有具有索引 α<[[艾普塞朗數|ε<sub>0</sub>]] 的急成长函数。

急成长阶层提供了一种根据增长率和[[計算複雜性理論|计算复杂性]]对[[可计算函数]]进行分类的自然方法。

== 定义 ==
令 μ 为一个大的可数序数，使得对于每个[[极限序数]]α<μ，都存在一个基本序列（一个严格递增的序数序列，其上界为α），属于'''急成长阶层'''的函数''f'' <sub>α</sub> : '''N''' → '''N''' ，对于 α<μ，定义如下：

* <math> f_0(n) = n + 1,</math>
* <math> f_{\alpha+1}(n) = f_\alpha^n(n)</math>
* <math> f_\alpha(n) = f_{\alpha[n]}(n) </math> ，如果 α 是极限序数。

这里，''f''<sub>α</sub><sup>''n''</sup>(''n'')=''f''<sub>α</sub>(''f''<sub>α</sub>(...(''f''<sub>α</sub>(''n''))...)) 为函数''f''<sub>α</sub>以''n''为起点的第''n''次[[迭代函数|迭代]]；α[''n''] 表示将基本序列的第''n''个元素分配给极限序数α。 

另一种定义将函数的迭代次数设为''n''+1，而不是上面第二行中的''n''。

该层级的初始部分由索引为''有限序数''（即 α<ω）的函数''f''<sub>α</sub>组成，通常称为'''Grzegorczyk阶层'''，因为它与Grzegorczyk 阶层密切相关。但请注意，前者是函数''f''<sub>''n''</sub>的索引族，而后者是函数''集''的索引族<math>\mathcal{E}^n</math> 。

进一步推广上述定义，通过将''f''<sub>0</sub>取为任意定义域和值域为自然数集的非减函数 g: '''N''' → '''N'''来获得'''急成长阶层'''。对于不大于[[艾普塞朗數|ε<sub>0</sub>]]的极限序数，基本序列有一个简单的自然定义（参见'''Wainer阶层'''）。但超过[[艾普塞朗數|ε<sub>0</sub>]]时，定义要复杂得多，然而，急成长阶层的定义可能远远超出 Feferman-Schütte 序数[[菲弗曼-舒特序數|Γ<sub>0</sub>]] ，至少达到Bachmann-Howard 序数。使用Buchholz psi 函数，可以将急成长阶层的定义扩展到超限迭代的序数<math>\Pi^1_1</math> -理解（参见层次分析）。

完全确定的超出递归序数的扩展被认为不可能；例如，Prӧmel ''等人。'' [1991]（第 17 页）&nbsp;348）指出，在这种尝试中“问题甚至会出现于序数表示法中”。

== Wainer 阶层 ==
'''Wainer阶层'''是通过定义基本序列获得的函数''f''<sub>α</sub> (α≤[[艾普塞朗數|ε<sub>0</sub>]] ) 的特定快速增长层级，如下所示：[Gallier 1991][Prӧmel, et al., 1991]：

对于极限序数 λ<[[艾普塞朗數|ε<sub>0</sub>]] ，以[[序數算術|康托范式]]表示，

* 如果 λ=ω<sup>α<sub>1</sub></sup>+...+ω<sup>α<sub>k−1</sub></sup>+ω<sup>α<sub>k</sub></sup> 对于α<sub>1</sub>≥...≥α<sub>k−1</sub>≥α<sub>k</sub>，则 λ[''n'']=ω<sup>α<sub>1</sub></sup>+...+ω<sup>α<sub>k−1</sub></sup>+ω<sup>α<sub>k</sub></sup>[''n''],
* 如果 λ=ω<sup>α+1</sup>，则 λ[''n'']=ω<sup>α</sup>''n''，
* 如果 λ=ω<sup>α</sup> ，α为极限序数，则 λ[''n'']=ω<sup>α[''n'']，</sup>

* 如果 λ=ε<sub>0</sub>，则取 λ[0]=0 且 λ[''n''+1]=ω<sup>λ[''n'']</sup>如 [Gallier 1991] 中所述；或者，采用相同的序列，除了以 λ[0]=1 开始，如 [Prӧmel, et al., 1991] 中所示。<br />对于''n''>0，有些版本在生成的指数塔中具有一个附加 ω，即 λ[''n'']=ω<sup>ω<sup>⋰<sup>&#x3C9;</sup></sup></sup>，具有''n'' 个ω，或 λ[''n'']=ω↑↑ω。

一些作者使用略有不同的定义，例如，ω<sup>α+1</sup>[''n'']=ω<sup>α</sup>(''n+1'')，而不是 ω<sup>α</sup>''n''；

有些作者仅针对 α<ε<sub>0</sub>定义此层次结构，因此将''f''<sub>ε<sub>0</sub></sub>及以上的函数排除在外。

对于索引超出 ε<sub>0</sub> 的函数，请参阅维勃伦层次结构的基本序列。

== 急成长阶层的函数 ==
任何属于急成长阶层的有限索引 (α<ω) 函数与 Grzegorczyk阶层的函数一致：（参见[[超运算]]）

* ''f''<sub>0</sub>(''n'')=''n''+1=2[1]''n''−1
* ''f''<sub>1</sub>(''n'')=''f''<sub>0</sub><sup>''n''</sup>(''n'')=''n''+''n''=2''n''=2[2]''n''
* 对于''n''≥2，''f''<sub>2</sub>(''n'')=''f''<sub>1</sub><sup>''n''</sup>(''n'')=2<sup>''n''</sup>·''n''>2<sup>''n''</sup>=2[3]''n'' 
* 对于''n''≥2，''k''<ω，''f''<sub>''k''+1</sub>(''n'')=''f''<sub>''k''</sub><sup>''n''</sup>(''n'')>(2[''k''+1])<sup>''n''</sup>''n''≥2[''k''+2]''n'' 。

超出有限索引的函数 (ω≤α≤ε<sub>0</sub>) 参见Wainer阶层：

* 对于''n''≥4，''f''<sub>ω</sub>(''n'')=''f''<sub>''n''</sub>(''n'')>2[''n''+1]''n''>2[''n''](''n''+3)−3=''A''(''n'',''n'') ，其中''A''是[[阿克曼函數|阿克曼函数]]，''f''<sub>ω</sub>是其一元版本。
* 对于所有''n''>0，''f''<sub>ω+1</sub>(''n'')=''f''<sub>ω</sub><sup>''n''</sup>(''n'')≥f<sub>''n''[''n''+2]''n''</sub>(''n'') ，其中''n''[''n''+2]''n''是''第 n''个[[阿克曼函數|阿克曼数]]。
* ''f''<sub>ω+1</sub>(64)=''f''<sub>ω</sub><sup>64</sup>(64)>[[葛立恆數|葛立恒数]]=由''g''<sub>0</sub>=4,''g''<sub>''k''+1</sub>=3[''g''<sub>''k''</sub>+2]3 定义的序列中的''g''<sub>64</sub>。由此可知''f''<sub>ω</sub>(''n'')>2[''n''+1]''n''>3[''n'']3+2，因此''f''<sub>ω</sub>(''g''<sub>''k''</sub>+2)>''g''<sub>''k''+1</sub>+2。
* ''f''<sub>ε<sub>0</sub></sub>(''n'') 是 Wainer 阶层的第一个增长率超过所有[[古德斯坦定理|Goodstein 函数]]的函数。

== 参见 ==
[[大数 (数学)|大数]]

[[缓成长阶层]]

== 参考 ==
<references group="" responsive="1"></references>
== 来源 ==

* Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". ''Logic and Combinatorics'', edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
* {{Citation|last1=Cichon|first1=E. A.|last2=Wainer|first2=S. S.|title=The slow-growing and the Grzegorczyk hierarchies|doi=10.2307/2273557|mr=704094|year=1983|journal=The Journal of Symbolic Logic|issn=0022-4812|volume=48|issue=2|pages=399–408|jstor=2273557|s2cid=1390729}}
* {{citation|mr=1129778|last=Gallier|first=Jean H.|authorlink=Jean Gallier|title=What's so special about Kruskal's theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory|journal=Ann. Pure Appl. Logic|volume=53|year=1991|issue=3|pages=199–260|doi=10.1016/0168-0072(91)90022-E|doi-access=free}} PDF: [https://www.cis.upenn.edu/~jean/kruskal.pdf] {{Wayback|url=https://www.cis.upenn.edu/~jean/kruskal.pdf |date=20240818232917 }}. (In particular Section 12, pp.&nbsp;59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
* {{Citation|last1=Girard|first1=Jean-Yves|author1-link=Jean-Yves Girard|title=Π<sup>1</sup><sub>2</sub>-logic. I. Dilators|doi=10.1016/0003-4843(81)90016-4|mr=656793|year=1981|journal=Annals of Mathematical Logic|issn=0003-4843|volume=21|issue=2|pages=75–219|doi-access=free}}
* Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", ''Arch. Math. Logik'', 13. Correction, ''Arch. Math. Logik'', 14, 1971. Part I {{doi|10.1007/BF01967649}}, Part 2 {{doi|10.1007/BF01973616}}, Corrections {{doi|10.1007/BF01991855}}.
* Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", ''Discrete Mathematics'', v.95 n.1-3, p.&nbsp;341-358, December 1991  {{doi|10.1016/0012-365X(91)90346-4}}.
* {{cite journal |last1=Wainer |first1=S.S |year=1989 |title=Slow Growing Versus Fast Growing |url=https://archive.org/details/sim_journal-of-symbolic-logic_1989-06_54_2/page/608 |journal=[[Journal of Symbolic Logic]] |volume=54 |issue=2 |pages=608–614 |doi=10.2307/2274873 |jstor=2274873 |s2cid=19848720}}
{{大数}}
[[Category:大数]]
[[Category:证明论]]
[[Category:递归论]]