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

点击翻译按钮获取中文摘要

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).