How Strong is Ramsey’s Theorem If Infinity Can Be Weak?

Journal of Symbolic Logic:1-20 (forthcoming)
  Copy   BIBTEX

Abstract

We study the first-order consequences of Ramsey’s Theorem for k-colourings of n-tuples, for fixed $n, k \ge 2$, over the relatively weak second-order arithmetic theory $\mathrm {RCA}^*_0$. Using the Chong–Mourad coding lemma, we show that in a model of $\mathrm {RCA}^*_0$ that does not satisfy $\Sigma ^0_1$ induction, $\mathrm {RT}^n_k$ is equivalent to its relativization to any proper $\Sigma ^0_1$ -definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe. We give a complete axiomatization of the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^n_k$ for $n \ge 3$. We show that they form a non-finitely axiomatizable subtheory of $\mathrm {PA}$ whose $\Pi _3$ fragment coincides with $\mathrm {B} \Sigma _1 + \exp $ and whose $\Pi _{\ell +3}$ fragment for $\ell \ge 1$ lies between $\mathrm {I} \Sigma _\ell \Rightarrow \mathrm {B} \Sigma _{\ell +1}$ and $\mathrm {B} \Sigma _{\ell +1}$. We also give a complete axiomatization of the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^2_k + \neg \mathrm {I} \Sigma _1$. In general, we show that the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^2_k$ form a subtheory of $\mathrm {I} \Sigma _2$ whose $\Pi _3$ fragment coincides with $\mathrm {B} \Sigma _1 + \exp $ and whose $\Pi _4$ fragment is strictly weaker than $\mathrm {B} \Sigma _2$ but not contained in $\mathrm {I} \Sigma _1$. Additionally, we consider a principle $\Delta ^0_2$ - $\mathrm {RT}^2_2$ which is defined like $\mathrm {RT}^2_2$ but with both the $2$ -colourings and the solutions allowed to be $\Delta ^0_2$ -sets rather than just sets. We show that the behaviour of $\Delta ^0_2$ - $\mathrm {RT}^2_2$ over $\mathrm {RCA}_0 + \mathrm {B}\Sigma ^0_2$ is in many ways analogous to that of $\mathrm {RT}^2_2$ over $\mathrm {RCA}^*_0$, and that $\mathrm {RCA}_0 + \mathrm {B} \Sigma ^0_2 + \Delta ^0_2$ - $\mathrm {RT}^2_2$ is $\Pi _4$ - but not $\Pi _5$ -conservative over $\mathrm {B} \Sigma _2$. However, the statement we use to witness failure of $\Pi _5$ -conservativity is not provable in $\mathrm {RCA}_0 +\mathrm {RT}^2_2$.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,346

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
Dickson’s lemma and weak Ramsey theory.Yasuhiko Omata & Florian Pelupessy - 2019 - Archive for Mathematical Logic 58 (3-4):413-425.
Reverse mathematics and a Ramsey-type König's Lemma.Stephen Flood - 2012 - Journal of Symbolic Logic 77 (4):1272-1280.
The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Ramsey’s theorem and König’s Lemma.T. E. Forster & J. K. Truss - 2007 - Archive for Mathematical Logic 46 (1):37-42.
A game‐theoretic proof of analytic Ramsey theorem.Kazuyuki Tanaka - 1992 - Mathematical Logic Quarterly 38 (1):301-304.
On the strength of Ramsey's theorem without Σ1 -induction.Keita Yokoyama - 2013 - Mathematical Logic Quarterly 59 (1-2):108-111.
Ramsey’s coheirs.Eugenio Colla & Domenico Zambella - 2022 - Journal of Symbolic Logic 87 (1):377-391.
Ramsey's Theorem for Pairs and Provably Recursive Functions.Alexander Kreuzer & Ulrich Kohlenbach - 2009 - Notre Dame Journal of Formal Logic 50 (4):427-444.

Analytics

Added to PP
2022-06-15

Downloads
1 (#1,500,365)

6 months
1 (#450,993)

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
Factorization of polynomials and °1 induction.S. G. Simpson - 1986 - Annals of Pure and Applied Logic 31:289.

View all 14 references / Add more references