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
Additional Information
- Timothy Carlson
- Affiliation: Department of Mathematics, The Ohio State University, Columbus, Ohio 43210
- MR Author ID: 45425
- Email: carlson@math.ohio-state.edu
- Received by editor(s): July 19, 2014
- Received by editor(s) in revised form: October 23, 2015
- Published electronically: December 7, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 2897-2916
- MSC (2010): Primary 03F40; Secondary 05C05
- DOI: https://doi.org/10.1090/tran/6972
- MathSciNet review: 3592532