緩成長階層
在可計算性理論、計算複雜性理論和證明理論中,緩成長階層是緩成長函數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.
|