Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results

详细信息    查看全文

• 作者：Andreas Weiermann
• 关键词：Analytic combinatorics ; Proof-theoretic ordinals ; Ordinal analysis ; Independence results for systems of arithmetic ; Tauberian theory ; Logical limit laws
• 刊名：Annals of Pure and Applied Logic
• 出版年：2005
• 出版时间：2005
• 年：2005
• 卷：136
• 期：1-2
• 页码：189-218
• 全文大小：390 K

文摘

This paper is intended to give for a general mathematical audience (including non-logicians) a survey of intriguing connections between analytic combinatorics and logic. We define the ordinals below ε₀ in non-logical terms and we survey a selection of recent results about the analytic combinatorics of these ordinals. Using a versatile and flexible (logarithmic) compression technique we give applications to phase transitions for independence results, Hilbert’s basis theorem, local number theory, Ramsey theory, Hydra games, and Goodstein sequences. We discuss briefly universality and renormalization issues in this context. Finally, we indicate how regularity properties of ordinal count functions can be used to prove logical limit laws.