The metamathematics of Stable Ramsey’s Theorem for Pairs

Chong, C.; Slaman, Theodore; Yang, Yue

doi:10.1090/S0894-0347-2014-00789-X

The metamathematics of Stable Ramsey’s Theorem for Pairs
HTML articles powered by AMS MathViewer

by C. T. Chong, Theodore A. Slaman and Yue Yang

J. Amer. Math. Soc. 27 (2014), 863-892

DOI: https://doi.org/10.1090/S0894-0347-2014-00789-X

Published electronically: March 25, 2014

PDF | Request permission

Abstract:

We show that, over the base theory $\textit {RCA}_0$, Stable Ramsey’s Theorem for Pairs implies neither Ramsey’s Theorem for Pairs nor $\Sigma ^0_2$-induction.

References

Cholak Peter A., Jockusch Carl G., and Slaman Theodore A., On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1–55.
Chong C. T., Steffen Lempp, and Yue Yang, On the role of the collection principle for $\Sigma ^0_2$-formulas in second-order reverse mathematics, Proc. Amer. Math. Soc. 138 (2010), no. 3, 1093–1100.
Rod Downey, Denis R. Hirschfeldt, Steffen Lempp, and Reed Solomon, A $\Delta ^0_2$ set with no infinite low subset in either it or its complement, J. Symbolic Logic 66 (2001), no. 3, 1371–1381. MR 1856748, DOI 10.2307/2695113
Petr Hájek, Interpretability and fragments of arithmetic, Arithmetic, proof theory, and computational complexity (Prague, 1991) Oxford Logic Guides, vol. 23, Oxford Univ. Press, New York, 1993, pp. 185–196. MR 1236462
Jeffry Lynn Hirst, COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)–The Pennsylvania State University. MR 2635978
Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
Richard Kaye, Models of Peano arithmetic, Oxford Logic Guides, vol. 15, The Clarendon Press, Oxford University Press, New York, 1991. Oxford Science Publications. MR 1098499
S. C. Kleene, Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53 (1943), 41–73. MR 7371, DOI 10.1090/S0002-9947-1943-0007371-8
Jiayi Liu, ${\mathsf {RT}}^2_2$ does not imply ${\mathsf {WKL}}_0$, J. Symbolic Logic 77 (2012), no. 2, 609–620. MR 2963024, DOI 10.2178/jsl/1333566640
Kenneth McAloon, Completeness theorems, incompleteness theorems and models of arithmetic, Trans. Amer. Math. Soc. 239 (1978), 253–277. MR 487048, DOI 10.1090/S0002-9947-1978-0487048-9
J. B. Paris and L. A. S. Kirby, $\Sigma _{n}$-collection schemas in arithmetic, Logic Colloquium ’77 (Proc. Conf., Wrocław, 1977) Studies in Logic and the Foundations of Mathematics, vol. 96, North-Holland, Amsterdam-New York, 1978, pp. 199–209. MR 519815
Hartley Rogers Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890
Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
David Seetapun and Slaman Theodore A., On the strength of Ramsey’s theorem, Notre Dame J. Formal Logic 36 (1995), no. 4, 570–582.
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
Theodore A. Slaman, $\Sigma _n$-bounding and $\Delta _n$-induction, Proc. Amer. Math. Soc. 132 (2004), no. 8, 2449–2456. MR 2052424, DOI 10.1090/S0002-9939-04-07294-6
E. Specker, Ramsey’s theorem does not hold in recursive set theory, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 439–442. MR 0278941