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

在[[可计算性理论]]、[[計算複雜性理論|计算复杂性理论]]和[[证明论|证明理论]]中，'''缓成长阶层'''是缓成长函数''g''<sub>α</sub>: '''N''' → '''N'''的序数索引族（其中'''N'''是[[自然数]]集合, {0, 1, ... }）。缓成长阶层的增长率与[[急成长阶层]]形成鲜明对比。

== 定义 ==
令 μ 为一个大的可数序数，以便将基本序列分配给每个小于 μ 的[[极限序数]]。函数''g''<sub>α</sub>: '''N''' → '''N'''的'''缓成长阶层'''（对于α<μ）定义如下：<ref>J. Gallier, [https://www.cis.upenn.edu/~jean/kruskal.pdf What's so special about Kruskal's theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory] {{Wayback|url=https://www.cis.upenn.edu/~jean/kruskal.pdf |date=20240818232917 }} (2012, p.63). Accessed 8 May 2023.</ref>

* <math> g_0(n) = 0 </math>
* <math> g_{\alpha+1}(n) = g_\alpha(n) + 1 </math>
* 对于极限序数α，<math> g_\alpha(n) = g_{\alpha[n]}(n)</math>。

这里， α[''n''] 表示分配给极限序数 α 的基本序列的第''n''个元素。

关于[[急成长阶层]]的文章描述了所有 α<ε<sub>0</sub> 的基本序列的标准化选择。

== 例 ==

* <math> g_1(n) = 1 </math>
* <math> g_m(n) = m </math>
* <math> g_\omega(n) = n </math>
* <math> g_{\omega+m}(n) = n+m </math>
* <math> g_{\omega m}(n) = mn </math>
* <math> g_{\omega^m}(n) = n^m </math>
* <math> g_{\omega^\omega}(n) = n^n </math>
* <math> g_{\varepsilon _0}(n) = n\uparrow\uparrow n </math>

== 与[[急成长阶层]]的关系 ==
对于较小的索引，缓成长阶层比急成长阶层增长得慢得多。即使''g''<sub>[[艾普塞朗數|ε<sub>0</sub>]]</sub>也只相当于''f''<sub>3</sub>，并且当α达到巴赫曼-霍华德序数时，''g''<sub>α</sub>也只能达到''f''<sub>ε<sub>0</sub></sub>的增长率。[[皮亚诺公理|皮亚诺算术]]无法证明[[偏函数]]结构中的第一个函数。 <ref name="girard81">{{Cite journal |last=Girard |first=Jean-Yves |author-link=Jean-Yves Girard |year=1981 |title=Π<sup>1</sup><sub>2</sub>-logic. I. Dilators |journal=Annals of Mathematical Logic |volume=21 |issue=2 |page=75–219 |doi=10.1016/0003-4843(81)90016-4 |issn=0003-4843 |mr=656793 |doi-access=free}}</ref> <ref name="cichon">{{Cite book|last=Cichon|title=Termination Proofs and Complexity Characterisations|year=1992|publisher=Cambridge University Press|pages=173–193|editor-last=P. Aczel|editor3=|editor1=}}</ref> <ref name="wainer83">{{Cite journal |last=Cichon |first=E. A. |last2=Wainer |first2=S. S. |year=1983 |title=The slow-growing and the Grzegorczyk hierarchies |journal=The Journal of Symbolic Logic |volume=48 |issue=2 |page=399–408 |doi=10.2307/2273557 |issn=0022-4812 |jstor=2273557 |mr=704094 |s2cid=1390729}}</ref>

然而与之形成鲜明对比的是，吉拉德证明，缓成长阶层最终''会赶上''急成长阶层。<ref name="girard81"></ref>具体来说，存在一个序数α使得对于所有整数''n''

: ''g''<sub>α</sub>(''n'')<''f''<sub>α</sub>(''n'')<''g''<sub>α</sub>(''n''+1)

其中''f''<sub>α</sub>是[[急成长阶层]]中的函数。他进一步表明，第一个使之成立的α，是归纳定义的任意有限迭代的理论''ID''<sub><ω</sub>的序数。<ref name="wainer89">{{Cite journal |last=Wainer |first=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=The Journal of Symbolic Logic |volume=54 |issue=2 |page=608–614 |doi=10.2307/2274873 |jstor=2274873 |s2cid=19848720}}</ref>然而，对于<ref name="cichon"></ref>中发现的基本序列的分配，第一次匹配发生在ε<sub>0</sub>级别。<ref name="weier1997">{{Cite journal |last=Weiermann |first=A |year=1997 |title=Sometimes slow growing is fast growing |journal=Annals of Pure and Applied Logic |volume=90 |issue=1–3 |page=91–99 |doi=10.1016/S0168-0072(97)00033-X |doi-access=free}}</ref>对于Buchholz风格的树序数，可以证明第一次匹配甚至发生在<math>\omega^2</math> 。

将证明<ref name="wainer89"></ref>的结果扩展到相当大的序数表明，低于超限迭代序数的序数非常少<math>\Pi^1_1</math> -理解缓成长阶层和急成长阶层相匹配的情况。 <ref name="weier1995">{{Cite journal |last=Weiermann |first=A. |year=1995 |title=Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones |journal=Archive for Mathematical Logic |volume=34 |issue=5 |page=313–330 |doi=10.1007/BF01387511 |s2cid=34180265}}</ref>

缓成长阶层极其敏感地依赖于底层基本序列的选择。 <ref name="weier1997"></ref> <ref name="weier1999">{{Cite book|chapter=Sets and Proofs|url=https://books.google.com/books?id=2IHm3RT2bBoC&pg=PA403|publisher=Cambridge University Press|date=1999-06-17|isbn=978-0-521-63549-3|language=en|first=S. Barry|last=Cooper|first2=John K.|last2=Truss|access-date=2024-03-14|archive-date=2023-10-10|archive-url=https://web.archive.org/web/20231010103618/https://books.google.com/books?id=2IHm3RT2bBoC&pg=PA403|dead-url=no}}</ref> <ref name="weier2001">{{Cite journal |last=Weiermann |first=Andreas |year=2001 |title=Γ<sub>0</sub> May be Minimal Subrecursively Inaccessible |journal=Mathematical Logic Quarterly |volume=47 |issue=3 |page=397–408 |doi=10.1002/1521-3870(200108)47:3<397::AID-MALQ397>3.0.CO;2-Y}}</ref>

== 参考 ==

* {{Cite journal |last=Gallier |first=Jean H. |year=1991 |title=What's so special about Kruskal's theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory |url=http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387 |journal=Ann. Pure Appl. Logic |volume=53 |issue=3 |pages=199–260 |doi=10.1016/0168-0072(91)90022-E |mr=1129778 |doi-access= |authorlink=Jean Gallier}}{{dead link|date=June 2022|bot=medic}} PDF's: [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal1.pdf part 1] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal2.pdf 2] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal3.pdf 3]. (In particular part 3, Section 12, pp.&nbsp;59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)

== 笔记 ==
<references />
{{大数}}
[[Category:证明论]]
[[Category:递归论]]