August 19
Leszek Kołodziejczyk,
University of Warsaw
Ramsey's Theorem over $\mathrm{RCA}^*_0$
The usual base theory used in reverse mathematics, $\mathrm{RCA}_0$, is the fragment of second-order arithmetic axiomatized by $\Delta^0_1$ comprehension and $\Sigma^0_1$ induction. The weaker base theory $\mathrm{RCA}^*_0$ is obtained by replacing $\Sigma^0_1$ induction with $\Delta^0_1$ induction (and adding the well-known axiom $\exp$ in order to ensure totality of the exponential function). In first-order terms, $\mathrm{RCA}_0$ is conservative over $\mathrm{I}\Sigma_1$ and $\mathrm{RCA}^*_0$ is conservative over $\mathrm{B}\Sigma_1 + \exp$.
Some of the most interesting open problems in reverse mathematics concern the first-order strength of statements from Ramsey Theory, in particular Ramsey's Theorem for pairs and two colours. In this talk, I will discuss joint work with Kasia Kowalik, Tin Lok Wong, and Keita Yokoyama concerning the strength of Ramsey's Theorem over $\mathrm{RCA}^*_0$.
Given standard natural numbers $n,k \ge 2$, let $\mathrm{RT}^n_k$ stand for Ramsey's Theorem for $k$-colourings of $n$-tuples. We first show that assuming the failure of $\Sigma^0_1$ induction, $\mathrm{RT}^n_k$ is equivalent to its own relativization to an arbitrary $\Sigma^0_1$-definable cut. Using this, we give a complete axiomatization of the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^n_k$ for $n \ge 3$ (this turns out to be a rather peculiar fragment of PA) and obtain some nontrivial information about the first-order consequences of $\mathrm{RT}^2_k$. Time permitting, we will also discuss the question whether our results have any relevance for the well-known open problem of characterizing the first-order consequences of $\mathrm{RT}^2_2$ over the traditional base theory $\mathrm{RCA}_0$.