Katarzyna W. Kowalik

How strong is Ramsey's theorem if infinity can be weak?

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 + \neg \mathrm{I}Σ^0_1$, $\mathrm{RT}^n_k$ is equivalent to its own relativization to any proper $Σ^0_1$-definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe. We give an 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 PA whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_{\ell+3}$ fragment for $\ell \ge 1$ lies between $\mathrm{I}Σ_\ell \Rightarrow \mathrm{B}Σ_{\ell+1}$ and $\mathrm{B}Σ_{\ell+1}$. We also consider the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^2_k$. We show that they form a subtheory of $\mathrm{I}Σ_2$ whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_4$ fragment is strictly weaker than $\mathrm{B}Σ_2$ but not contained in $\mathrm{I}Σ_1$. Additionally, we consider a principle $Δ^0_2$-$\mathrm{RT}^2_2$, defined like $\mathrm{RT}^2_2$ but with both the $2$-colourings and the solutions allowed to be $Δ^0_2$-sets. We show that the behaviour of $Δ^0_2$-$\mathrm{RT}^2_2$ over $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2$ is similar to that of $\mathrm{RT}^2_2$ over $\mathrm{RCA}^*_0$, and that $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2 + Δ^0_2$-$\mathrm{RT}^2_2$ is $Π_4$- but not $Π_5$-conservative over $\mathrm{B}Σ_2$. However, the statement we use to witness lack of $Π_5$-conservativity is not provable in $\mathrm{RCA}_0 +\mathrm{RT}^2_2$.