Hostname: page-component-77c89778f8-m42fx Total loading time: 0 Render date: 2024-07-21T13:47:38.917Z Has data issue: false hasContentIssue false
  • English
  • Français

THE STRENGTH OF RAMSEY’S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORS

Published online by Cambridge University Press:  21 December 2018

THEODORE A. SLAMAN  and
KEITA YOKOYAMA
THEODORE A. SLAMAN
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA, BERKELEY BERKELEY, CA94720-3840, USA E-mail: [email protected]
KEITA YOKOYAMA
Affiliation:
SCHOOL OF INFORMATION SCIENCE JAPAN ADVANCED INSTITUTE OF SCIENCE AND TECHNOLOGY 1-1 ASAHIDAI, NOMI, ISHIKAWA923-1292, JAPAN E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article, we will show that ${\rm{R}}{{\rm{T}}^2} + WK{L_0}$ is a ${\rm{\Pi }}_1^1$-conservative extension of ${\rm{B\Sigma }}_3^0$.

Keywords

Primary 03B3003F3505D10Secondary 03H1503C6203D80reverse mathematicsRamsey’s theoremfirst-order part
Type
Articles
Information
The Journal of Symbolic Logic , Volume 83 , Issue 4 , December 2018 , pp. 1610 - 1617
Copyright
Copyright © The Association for Symbolic Logic 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Belanger, D. A., Conservation theorems for the cohesiveness principle, preprint. 2015. Available at http://www.math.nus.edu.sg/∼imsdrb/papers/coh-2015-09-30.pdf.Google Scholar
Cholak, P. A., Jockusch, C. G., and Slaman, T. A., On the strength of Ramsey’s theorem for pairs, this Journal, vol. 66 (2001), no. 1, pp. 1–55.Google Scholar
Chong, C. T., Slaman, T. A., and Yang, Y., The inductive strength of Ramsey’s theorem for pairs. Advances in Mathematics, vol. 308 (2017), pp. 121–141.CrossRefGoogle Scholar
Hájek, P., Interpretability and fragments of arithmetic, Arithmetic, Proof Theory, and Computational Complexity (Clote, P. and Krajícek, J., editors), Oxford Logic Guides, vol. 23, Oxford University Press, New York, 1993, pp. 185–196.Google Scholar
Hájek, P. and Kučera, A., On recursion theory in ${\rm{I}}{{\rm{\Sigma }}_1}$., this Journal, vol. 54 (1989), no. 2, pp. 576–589.Google Scholar
Hirschfeldt, D. R., Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 28, World Scientific Publishing, Hackensack, NJ, 2015.Google Scholar
Hirst, J. L., Combinatorics in Subsystems of Second Order Arithmetic, Ph.D. thesis, The Pennsylvania State University, ProQuest LLC, Ann Arbor, MI, 1987.Google Scholar
Patey, L. and Yokoyama, K., The proof-theoretic strength of Ramsey’s theorem for pairs and two colors, Advances in Mathematics, vol. 330 (2018), pp. 1034–1070.CrossRefGoogle Scholar
Simpson, S. G., Subsystems of Second Order Arithmetic, second ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009.CrossRefGoogle Scholar
Yokoyama, K., On ${\rm{\Pi }}_1^1$ conservativity for ${\rm{\Pi }}_2^1$ theories in second order arithmetic, 10th Asian Logic Conference (Arai, T., Brendle, J., Kikyo, H., Chong, C. T., Downey, R., Feng, Q., and Ono, H., editors), World Scientific Publishing, Hackensack, NJ, 2010, pp. 375–386.Google Scholar