The metamathematics of Stable Ramsey’s Theorem for Pairs

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

¹ Department of Mathematics, National University of Singapore, Singapore 119076
² Department of Mathematics, University of California, Berkeley, Berkeley, California 94720-3840

Journal of the American Mathematical Society, Tome 27 (2014) no. 3, pp. 863-892

Résumé

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.

Détail

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

Bibliographie

[1] Cholak Peter A., Jockusch Carl G., Slaman Theodore A. On the strength of Ramsey’s theorem for pairs J. Symbolic Logic 2001 1 55

[2] Chong C. T., Steffen Lempp, Yue Yang On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics Proc. Amer. Math. Soc. 2010 1093 1100

[3] Downey, Rod, Hirschfeldt, Denis R., Lempp, Steffen, Solomon, Reed A Δ⁰₂ set with no infinite low subset in either it or its complement J. Symbolic Logic 2001 1371 1381

[4] Hã¡Jek, Petr Interpretability and fragments of arithmetic 1993 185 196

[5] Hirst, Jeffry Lynn COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC 1987 153

[6] Jockusch, Carl G., Jr. Ramsey’s theorem and recursion theory J. Symbolic Logic 1972 268 280

[7] Jockusch, Carl G., Jr., Soare, Robert I. Π⁰₁ classes and degrees of theories Trans. Amer. Math. Soc. 1972 33 56

[8] Kaye, Richard Models of Peano arithmetic 1991

[9] Kleene, S. C. Recursive predicates and quantifiers Trans. Amer. Math. Soc. 1943 41 73

[10] Liu, Jiayi 𝖱𝖳²₂ does not imply 𝖶𝖪𝖫₀ J. Symbolic Logic 2012 609 620

[11] Mcaloon, Kenneth Completeness theorems, incompleteness theorems and models of arithmetic Trans. Amer. Math. Soc. 1978 253 277

[12] Paris, J. B., Kirby, L. A. S. Σ_{𝑛}-collection schemas in arithmetic 1978 199 209

[13] Rogers, Hartley, Jr. Theory of recursive functions and effective computability 1987

[14] Sacks, Gerald E. Higher recursion theory 1990

[15] Seetapun, David, Slaman Theodore A. On the strength of Ramsey’s theorem Notre Dame J. Formal Logic 1995 570 582

[16] Simpson, Stephen G. Subsystems of second order arithmetic 2009

[17] Slaman, Theodore A. Σ_{𝑛}-bounding and Δ_{𝑛}-induction Proc. Amer. Math. Soc. 2004 2449 2456

[18] Specker, E. Ramsey’s theorem does not hold in recursive set theory 1971 439 442