可计算性理论计算复杂性理论证明理论中,缓成长阶层是缓成长函数gα: NN的序数索引族(其中N自然数集合, {0, 1, ... })。缓成长阶层的增长率与急成长阶层形成鲜明对比。

定义

编辑

令 μ 为一个大的可数序数,以便将基本序列分配给每个小于 μ 的极限序数。函数gα: NN缓成长阶层(对于α<μ)定义如下:[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]

参考

编辑

笔记

编辑
  1. ^ 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. ^ 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. ^ 3.0 3.1 Cichon. P. Aczel , 编. Termination Proofs and Complexity Characterisations. Cambridge University Press. 1992: 173–193. 
  4. ^ 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. ^ 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. ^ 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 . 
  7. ^ 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. 
  8. ^ 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=为空 (帮助)
  9. ^ 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.