Analysis of a Double Kruskal Theorem

Carlson, Timothy

doi:10.1090/tran/6972

Analysis of a Double Kruskal Theorem
HTML articles powered by AMS MathViewer

by Timothy Carlson PDF

Trans. Amer. Math. Soc. 369 (2017), 2897-2916 Request permission

Abstract:

The strength of an extension of Kruskal’s Theorem to certain pairs of cohabitating trees is calibrated showing that it is independent of the theory $\Pi ^1_1-\textbf {CA}_0$ or, equivalently, $\textbf {KP}\ell _0$.

References

W. Buchholz, A new system of proof-theoretic ordinal functions, Ann. Pure Appl. Logic 32 (1986), no. 3, 195–207. MR 865989, DOI 10.1016/0168-0072(86)90052-7
Timothy Carlson, Generalizing Kruskal’s theorem to pairs of cohabitating trees, Arch. Math. Logic 55 (2016), no. 1-2, 37–48. MR 3453578, DOI 10.1007/s00153-015-0457-4
Gerhard Jäger, Theories for admissible sets: a unifying approach to proof theory, Studies in Proof Theory. Lecture Notes, vol. 2, Bibliopolis, Naples, 1986. MR 881218
J. B. Kruskal, Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjecture, Trans. Amer. Math. Soc. 95 (1960), 210–225. MR 111704, DOI 10.1090/S0002-9947-1960-0111704-1
Richard Laver, Well-quasi-orderings and sets of finite sequences, Math. Proc. Cambridge Philos. Soc. 79 (1976), no. 1, 1–10. MR 392705, DOI 10.1017/S030500410005204X
M. Rathjen, M. Toppel, and A. Weiermann, Ordinal analysis, proof-theoretic reductions and conservativity, in preparation.
Michael Rathjen and Andreas Weiermann, Proof-theoretic investigations on Kruskal’s theorem, Ann. Pure Appl. Logic 60 (1993), no. 1, 49–88. MR 1212407, DOI 10.1016/0168-0072(93)90192-G
Stephen G. Simpson, Nonprovability of certain combinatorial properties of finite trees, Harvey Friedman’s research on the foundations of mathematics, Stud. Logic Found. Math., vol. 117, North-Holland, Amsterdam, 1985, pp. 87–117. MR 835255, DOI 10.1016/S0049-237X(09)70156-9
Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689, DOI 10.1017/CBO9780511581007