## 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 PDF
- J. Amer. Math. Soc.
**27**(2014), 863-892 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**

## Additional Information

**C. T. Chong**- Affiliation: Department of Mathematics, National University of Singapore, Singapore 119076
- MR Author ID: 48725
- Email: chongct@math.nus.edu.sg
**Theodore A. Slaman**- Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720-3840
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
**Yue Yang**- Affiliation: Department of Mathematics, National University of Singapore, Singapore 119076
- Email: matyangy@nus.edu.sg
- Received by editor(s): September 1, 2012
- Received by editor(s) in revised form: August 17, 2013
- Published electronically: March 25, 2014
- © Copyright 2014 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**27**(2014), 863-892 - MSC (2010): Primary 03B30, 03F35, 03D80; Secondary 05D10
- DOI: https://doi.org/10.1090/S0894-0347-2014-00789-X
- MathSciNet review: 3194495