Continuous Order Transformations: A Bridge Between Ordinal Analysis, Reverse Mathematics, and Combinatorics

连续阶次变换：序数分析、逆向数学和组合数学之间的桥梁

• 批准号: 460597863
• 负责人: Professor Dr. Anton Freund
• 金额: --
• 依托单位: Juniorprofessur am Lehrstuhl für Mathematik III (Mathematische Logik)
• 依托单位国家: 德国
• 项目类别: Independent Junior Research Groups
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/460597863?language=en
• 关键词: Continuous; Order; Transformations; Bridge; Between

The following question is central for several branches of mathematical logic: Which axiom systems are strong enough to prove a given mathematical theorem? In addition to its intrinsic intellectual interest, an answer to this question does often yield further information about the theorem in question, for example on the quality of approximations or the complexity of algorithmic solutions. Our project will deepen connections between two branches of mathematical logic, which are both concerned with the central question formulated above: ordinal analysis and reverse mathematics. As a bridge between the two approaches, we will use continuous transformations (finite-type functionals) over the categories of partial and linear orders. This will allow us to answer the central question in cases where it is currently open. Specifically, we will analyze theorems of combinatorics, mostly related to Kruskal's tree theorem, the graph minor theorem, and the theory of better quasi orders. We will also obtain a general framework, in which known and new results can be explained in a uniform way. Our approach is exemplified by previous work of the applicant (Advances in Mathematics 355, 2019, article no. 106767, 65 pp.), which uses methods from ordinal analysis (specifically work of Gerhard Jäger) to characterize the important axiom of Pi^1_1-comprehension, solving one of Antonio Montalbán's ``Open questions in reverse mathematics" (Bulletin of Symbolic Logic 17:3, 2011, pp. 431-454). Based on this characterization, Michael Rathjen, Andreas Weiermann and the applicant have shown (arXiv:2001.06380) that a uniform version of Kruskal's theorem is equivalent to Pi^1_1-comprehension--and hence (by a result of Alberto Marcone) also to the famous minimal bad sequence lemma of Crispin Nash-Williams. In our project, we will substantially extend the indicated approach: We plan (1) to determine the precise strength of Harvey Friedman's gap condition, which has been open for 30 years and is relevant for the graph minor theorem; (2) to use order transformations to characterize axioms beyond Pi^1_1-comprehension, which will shed new light on ordinal analyses of Michael Rathjen and Toshiyasu Arai and hence on Hilbert's second problem; (3) to extend the use of order transformations to all finite types and levels of the analytical hierarchy; and (4) to develop applications of order transformations to the theory of better quasi orders, with the aim to determine the strength of Nash-Williams's theorem on transfinite sequences (which would solve another open questions from Montalbán's list).

以下问题是数理逻辑几个分支的核心问题：哪些公理系统足以证明给定的数学定理？除了其内在的智力兴趣之外，这个问题的答案通常确实会产生有关所讨论定理的更多信息，例如近似值的质量或算法解决方案的复杂性。我们的项目将加深数理逻辑的两个分支之间的联系，这两个分支都涉及上面提出的中心问题：序数分析和逆向数学。作为两种方法之间的桥梁，我们将在偏序和线性序的类别上使用连续变换（有限型泛函）。这将使我们能够在当前开放的情况下回答核心问题。具体来说，我们将分析组合数学定理，主要与克鲁斯卡树定理、图小定理和更好拟阶理论相关。我们还将获得一个总体框架，在其中可以以统一的方式解释已知的和新的结果。我们的方法以申请人之前的工作为例（数学进展 355，2019 年，文章编号 106767，第 65 页），该工作使用序数分析方法（特别是 Gerhard Jäger 的工作）来表征 Pi^1_1 推导式的重要公理，解决 Antonio Montalbán 的“逆向数学中的开放问题”之一（Bulletin of 符号逻辑 17:3，2011，第 431-454 页）。基于这一特征，Michael Rathjen、Andreas Weiermann 和申请人已经证明 (arXiv:2001.06380) Kruskal 定理的统一版本相当于 Pi^1_1 推导式，因此（由 Alberto Marcone 得出）也相当于著名的最小不良序列 克里斯平·纳什-威廉姆斯的引理。在我们的项目中，我们将大幅扩展所指出的方法：我们计划 (1) 确定 Harvey Friedman 间隙条件的精确强度，该条件已开放 30 年并且与图小定理相关； (2) 使用阶次变换来表征超出 Pi^1_1 理解的公理，这将为 Michael Rathjen 和的序数分析提供新的启示 Toshiyasu Arai 以及希尔伯特的第二个问题； (3) 将阶次变换的使用扩展到分析层次结构的所有有限类型和级别； (4) 开发阶次变换在更好准阶理论中的应用，目的是确定纳什-威廉姆斯超限序列定理的强度（这将解决 Montalbán 列表中的另一个悬而未决的问题）。