缓成长阶层
在可计算性理论、计算复杂性理论和证明理论中,缓成长阶层是缓成长函数gα: N → N的序数索引族(其中N是自然数集合, {0, 1, ... })。缓成长阶层的增长率与急成长阶层形成鲜明对比。
定义
令 μ 为一个大的可数序数,以便将基本序列分配给每个小于 μ 的极限序数。函数gα: N → N的缓成长阶层(对于α<μ)定义如下:[1]
- 对于极限序数α,。
这里, α[n] 表示分配给极限序数 α 的基本序列的第n个元素。
关于急成长阶层的文章描述了所有 α<ε0 的基本序列的标准化选择。
例
与急成长阶层的关系
对于较小的索引,缓成长阶层比急成长阶层增长得慢得多。即使gε0也只相当于f3,并且当α达到巴赫曼-霍华德序数时,gα也只能达到fε0的增长率。皮亚诺算术无法证明偏函数结构中的第一个函数。 [2] [3] [4]
然而与之形成鲜明对比的是,吉拉德证明,缓成长阶层最终会赶上急成长阶层。[2]具体来说,存在一个序数α使得对于所有整数n
- gα(n)<fα(n)<gα(n+1)
其中fα是急成长阶层中的函数。他进一步表明,第一个使之成立的α,是归纳定义的任意有限迭代的理论ID<ω的序数。[5]然而,对于[3]中发现的基本序列的分配,第一次匹配发生在ε0级别。[6]对于Buchholz风格的树序数,可以证明第一次匹配甚至发生在 。
将证明[5]的结果扩展到相当大的序数表明,低于超限迭代序数的序数非常少 -理解缓成长阶层和急成长阶层相匹配的情况。 [7]
缓成长阶层极其敏感地依赖于底层基本序列的选择。 [6] [8] [9]
参考
- Gallier, Jean H. What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory. Ann. Pure Appl. Logic. 1991, 53 (3): 199–260. MR 1129778. doi:10.1016/0168-0072(91)90022-E.[失效連結] PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
笔记
- ^ J. Gallier, What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory (2012, p.63). Accessed 8 May 2023.
- ^ 2.0 2.1 Girard, Jean-Yves. Π12-logic. I. Dilators. Annals of Mathematical Logic. 1981, 21 (2): 75–219. ISSN 0003-4843. MR 0656793. doi:10.1016/0003-4843(81)90016-4
.
- ^ 3.0 3.1 Cichon. P. Aczel , 编. Termination Proofs and Complexity Characterisations. Cambridge University Press. 1992: 173–193.
- ^ Cichon, E. A.; Wainer, S. S. The slow-growing and the Grzegorczyk hierarchies. The Journal of Symbolic Logic. 1983, 48 (2): 399–408. ISSN 0022-4812. JSTOR 2273557. MR 0704094. S2CID 1390729. doi:10.2307/2273557.
- ^ 5.0 5.1 Wainer, S. S. Slow Growing Versus Fast Growing. The Journal of Symbolic Logic. 1989, 54 (2): 608–614. JSTOR 2274873. S2CID 19848720. doi:10.2307/2274873.
- ^ 6.0 6.1 Weiermann, A. Sometimes slow growing is fast growing. Annals of Pure and Applied Logic. 1997, 90 (1–3): 91–99. doi:10.1016/S0168-0072(97)00033-X
.
- ^ Weiermann, A. Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones. Archive for Mathematical Logic. 1995, 34 (5): 313–330. S2CID 34180265. doi:10.1007/BF01387511.
- ^ Cooper, S. Barry; Truss, John K. Sets and Proofs. Cambridge University Press https://books.google.com/books?id=2IHm3RT2bBoC&pg=PA403. 1999-06-17. ISBN 978-0-521-63549-3 (英语). 缺少或
|title=
为空 (帮助) - ^ Weiermann, Andreas. Γ0 May be Minimal Subrecursively Inaccessible. Mathematical Logic Quarterly. 2001, 47 (3): 397–408. doi:10.1002/1521-3870(200108)47:3<397::AID-MALQ397>3.0.CO;2-Y.
|