Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

The metamathematics of Stable Ramsey's Theorem for Pairs


Authors: C. T. Chong, Theodore A. Slaman and Yue Yang
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
Published electronically: March 25, 2014
MathSciNet review: 3194495
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [Cholak Peter A. et al. , 2001] 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. et al. , 2010] 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.
  • [Downey et al. , 2001] Downey, Rod, 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 (2002i:03046), https://doi.org/10.2307/2695113
  • [Hájek, 1993] Hájek, Petr, 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 (94f:03066)
  • [Hirst, 1987] Hirst, Jeffry Lynn, Combinatorics in Subsystems of Second Order Arithmetic, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)-The Pennsylvania State University. MR 2635978
  • [Jockusch, 1972] Jockusch, Carl G., Jr., Ramsey's theorem and recursion theory, J. Symbolic Logic 37 (1972), 268-280. MR 0376319 (51 #12495)
  • [Jockusch and Soare, 1972] Jockusch, Carl G., Jr. and Robert I. Soare, $ \Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33-56. MR 0316227 (47 #4775)
  • [Kaye, 1991] Kaye, Richard, Models of Peano arithmetic, Oxford Logic Guides, vol. 15, The Clarendon Press, Oxford University Press, New York, 1991. Oxford Science Publications. MR 1098499 (92k:03034)
  • [Kleene, 1943] Kleene, S. C., Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53 (1943), 41-73. MR 0007371 (4,126b)
  • [Liu, 2012] Liu, Jiayi, $ {\mathsf {RT}}^2_2$ does not imply $ {\mathsf {WKL}}_0$, J. Symbolic Logic 77 (2012), no. 2, 609-620. MR 2963024, https://doi.org/10.2178/jsl/1333566640
  • [McAloon, 1978] McAloon, Kenneth, Completeness theorems, incompleteness theorems and models of arithmetic, Trans. Amer. Math. Soc. 239 (1978), 253-277. MR 487048 (81e:03066), https://doi.org/10.2307/1997856
  • [Paris and Kirby, 1978] Paris, J. B. and L. A. S. Kirby, $ \Sigma _{n}$-collection schemas in arithmetic, Logic Colloquium '77 (Proc. Conf., Wrocław, 1977) Stud. Logic Foundations Math., vol. 96, North-Holland, Amsterdam, 1978, pp. 199-209. MR 519815 (81e:03056)
  • [Rogers, 1987] Rogers, Hartley, Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890 (88b:03059)
  • [Sacks, 1990] Sacks, Gerald E., Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970 (92a:03062)
  • [Seetapun and Slaman Theodore A., 1995] Seetapun, David and Slaman Theodore A., On the strength of Ramsey's theorem, Notre Dame J. Formal Logic 36 (1995), no. 4, 570-582.
  • [Simpson, 2009] Simpson, Stephen G., Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge, 2009. MR 2517689 (2010e:03073)
  • [Slaman, 2004] Slaman, Theodore A., $ \Sigma _n$-bounding and $ \Delta _n$-induction, Proc. Amer. Math. Soc. 132 (2004), no. 8, 2449-2456 (electronic). MR 2052424 (2005b:03140), https://doi.org/10.1090/S0002-9939-04-07294-6
  • [Specker, 1971] Specker, E., 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 (43 #4667)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 03B30, 03F35, 03D80, 05D10

Retrieve articles in all journals with MSC (2010): 03B30, 03F35, 03D80, 05D10


Additional Information

C. T. Chong
Affiliation: Department of Mathematics, National University of Singapore, Singapore 119076
Email: chongct@math.nus.edu.sg

Theodore A. Slaman
Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720-3840
Email: slaman@math.berkeley.edu

Yue Yang
Affiliation: Department of Mathematics, National University of Singapore, Singapore 119076
Email: matyangy@nus.edu.sg

DOI: https://doi.org/10.1090/S0894-0347-2014-00789-X
Keywords: Reverse mathematics, $RCA_0$, $\Sigma^0_2$-bounding, Ramsey's Theorem for Pairs, Stable Ramsey's Theorem for Pairs
Received by editor(s): September 1, 2012
Received by editor(s) in revised form: August 17, 2013
Published electronically: March 25, 2014
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society