Well ordering principles for iterated ^1_1-comprehension

DOI10.1007/S00029-023-00879-2MaRDI QIDQ6080077zbMATH OpenFDO

Publication date 30 October 2023

Published in Selecta Mathematica. New Series (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2112.08005

admissible sets dilators iterated \(\Pi^1_1\)-comprehension ordinal analysis ordinal collapsing functions reverse mathematics transfinite recursion well ordering principles

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Ordinal and cardinal numbers (03E10) Recursive ordinals and ordinal notations (03F15) Second- and higher-order arithmetic and fragments (03F35)

Abstract: We introduce ordinal collapsing principles that are inspired by proof theory but have a set theoretic flavor. These principles are shown to be equivalent to iterated

P i_{1}^{1}

-comprehension and the existence of admissible sets, over weak base theories. Our work extends a previous result on the non-iterated case, which had been conjectured in Montalb'an's "Open questions in reverse mathematics" (Bull. Symb. Log. 17(3)2011). This previous result has already been applied to the reverse mathematics of combinatorial and set theoretic principles. The present paper is a significant contribution to a general approach that connects these fields.

Review text

The authors present new reverse mathematical equivalences between ordinal collapsing principles, iterated \(\Pi^1_1\)-comprehension, and the existence of admissible sets. A central result is that, over \(\mathsf{RCA}_0\), the following are equivalent for any infinite well-ordering \(\nu\): (1) \(\Pi^1_1\)-recursion along \(\nu\); (2) any dilator has a well founded \(\nu\)-fixed point; and (3) if \(D\) is a dilator, then \(\psi_\nu (D)\) is well founded. Using \(\mathsf{ATR}_0^{\mathsf{set}}\) as a base system, (1) and (3) are shown to be equivalent to: (4) for any set \(u\), there is a sequence of admissible sets \(\mathsf{Ad}_\alpha \owns u\) for \(\alpha < \nu\) such that \(\alpha < \beta < \nu\) entails \(\mathsf{Ad}_\alpha \in\mathsf{Ad}_\beta\) (where \(\nu\) is viewed as an ordinal). The result has consequences in the characterization of \(\beta\)-models of \(\Pi^1_1\)-comprehension, including a result promised in a paper of \textit{M. Rathjen} [in: Axiomatic thinking II. Cham: Springer. 89--127 (2022; Zbl 07632450)]. \textit{A. Freund} has applied the work presented here to prove the equivalence of \(\Pi^1_1\)-transfinite recursion and a uniform Kruskal-Friedman theorem with gap condition [``Reverse mathematics of a uniform Kruskal-Friedman theorem, Preprint, \url{arXiv:2112.08727}]. These new iterated results build on earlier results on the equivalence of \(\Pi^1_1\)-comprehension and fixed points of dilators in the work of \textit{A. Freund} [J. Math. Log. 20, No. 2, Article ID 2050006, 26 p. (2020; Zbl 1457.03027)].

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Well ordering principles for iterated \(\Pi^1_1\)-comprehension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080077)