Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Analysis of a Double Kruskal Theorem


Author: Timothy Carlson
Journal: Trans. Amer. Math. Soc. 369 (2017), 2897-2916
MSC (2010): Primary 03F40; Secondary 05C05
DOI: https://doi.org/10.1090/tran/6972
Published electronically: December 7, 2016
MathSciNet review: 3592532
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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-{\bf CA}_0$ or, equivalently, $ {\bf KP}\ell _0$.


References [Enhancements On Off] (What's this?)

  • [1] W. Buchholz, A new system of proof-theoretic ordinal functions, Ann. Pure Appl. Logic 32 (1986), no. 3, 195-207. MR 865989, https://doi.org/10.1016/0168-0072(86)90052-7
  • [2] Timothy Carlson, Generalizing Kruskal's theorem to pairs of cohabitating trees, Arch. Math. Logic 55 (2016), no. 1-2, 37-48. MR 3453578, https://doi.org/10.1007/s00153-015-0457-4
  • [3] 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
  • [4] J. B. Kruskal, Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture, Trans. Amer. Math. Soc. 95 (1960), 210-225. MR 0111704
  • [5] Richard Laver, Well-quasi-orderings and sets of finite sequences, Math. Proc. Cambridge Philos. Soc. 79 (1976), no. 1, 1-10. MR 0392705
  • [6] M. Rathjen, M. Toppel, and A. Weiermann, Ordinal analysis, proof-theoretic reductions and conservativity, in preparation.
  • [7] Michael Rathjen and Andreas Weiermann, Proof-theoretic investigations on Kruskal's theorem, Ann. Pure Appl. Logic 60 (1993), no. 1, 49-88. MR 1212407, https://doi.org/10.1016/0168-0072(93)90192-G
  • [8] 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, https://doi.org/10.1016/S0049-237X(09)70156-9
  • [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

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03F40, 05C05

Retrieve articles in all journals with MSC (2010): 03F40, 05C05


Additional Information

Timothy Carlson
Affiliation: Department of Mathematics, The Ohio State University, Columbus, Ohio 43210
Email: carlson@math.ohio-state.edu

DOI: https://doi.org/10.1090/tran/6972
Received by editor(s): July 19, 2014
Received by editor(s) in revised form: October 23, 2015
Published electronically: December 7, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society