# What are the proof-theoretic strengths of Ramsey's theorems?

The proof-theoretic strength of a theory is measured by the $$\mathsf{\Pi}_{1}^{1}$$-ordinal of the theory (indeed, there are other ordinal analyses, like the $$\Pi_{2}^{0}$$-ordinal of the theory).

Consider the following statements:

Finite Ramsey Theorem ($$\mathrm{FRT}$$): For any $$r,k,p\in\mathbb{N}$$, there exists $$N\in\mathbb{N}$$ such that for any set $$S$$ of cardinality $$N$$ and any function $$c:[S]^{p}\rightarrow [r]$$ there exists a subset $$H\subseteq S$$ of cardinality $$k$$ such that $$c|_{[H]^{p}}$$ is constant.

By $$[r]$$ we mean the set $$\{1,\ldots r\}$$, and the function $$c$$ is often called an $$r$$-coloring of the $$p$$-element subsets of $$S$$. The subset $$H$$ is called a homogeneous $$k$$-subset of $$S$$.

What is the proof-theoretic strength of $$\mathrm{FRT}$$? My understanding is that it should not be more than $$\omega^{\omega}$$ because $$\mathsf{RCA}_{0}+\mathsf{IΣ}_{1}$$ proves $$\mathrm{FRT}$$ since we are essentially applying induction to the formula: "there exists an $$N$$ such that every $$r$$-coloring of the $$p$$-element subsets of $$\{1,\ldots,N\}$$ has a homogeneous $$k$$-subset". But $$\mathsf{RCA}_{0}+\mathsf{IΣ}_{1}$$ seems more than we really need, and it may very well be that the proof-theoretic strength is $$\omega^{n}$$ for some low $$n\ge 1$$.

Infinite Ramsey Theorem ($$\mathrm{IRT}$$): For any $$r,p\in\mathbb{N}$$, and for any function $$c:[\mathbb{N}]^{p}\rightarrow [r]$$, there exists an infinite subset $$H\subseteq \mathbb{N}$$ such that $$c|_{[H]^{p}}$$ is constant.

Let $$\mathrm{IRT}(p)$$ denote the instance of $$\mathrm{IRT}$$ for exponent $$p$$. That is, $$\mathrm{IRT}$$ is simply the statement $$\forall p\,\,\mathrm{IRT}(p)$$.

First, we consider the case of $$A$$ countable:

1. Over $$\mathsf{RCA}_{0}$$, $$\mathsf{ACA}_{0}$$ proves $$\mathrm{IRT}(P)$$, $$p\geq 0$$ (Lemma III.7.4, p.123 of 1). Therefore, the proof-theoretic strength of $$\mathrm{IRT}(p)$$, $$p\ge 0$$ is at most $$\varepsilon_{0}$$. Moreover, Theorem III.7.6, p.124 of 1 shows that over $$\mathsf{RCA}_{0}$$, $$\mathsf{ACA}_{0}$$ is equivalent to $$\mathrm{IRT}(p)$$, $$p\ge 3$$. Therefore, the proof-theoretic ordinal of $$\mathrm{IRT}(p)$$, $$p\geq 3$$ is indeed $$\varepsilon_{0}$$. The case $$\mathrm{IRT}(0)$$ is trivial. Does the proof-theoretic strength of $$\mathrm{IRT}(1)$$ (i.e. the infinite pigeonhole principle) equal $$\omega^{\omega}$$? What is the proof-theoretic strength of $$\mathrm{IRT}(2)$$?
2. Remark III.7.7, p.124 in 1 indicates that the statement $$\forall p\,\,\mathrm{IRT}(p)$$ is provable from $$\mathsf{ACA}_{0}$$ plus $$\mathsf{\Pi}_{2}^{1}$$-induction over $$\mathsf{RCA}_{0}$$. From this I gather that the proof-theoretic strength of $$\mathrm{IRT}$$ could be $$\varepsilon_{\alpha}$$ for some ordinal $$\alpha$$ (possibly $$\alpha=\omega$$?) But I am not sure. What is the proof-theoretic strength of IRT?

Second, we consider $$A$$ arbitrary infinite: Then we must consider $$\mathrm{IRT}$$ as a statement of $$\mathsf{ZFC}$$, for it has been shown in [2] that $$\mathrm{IRT}$$ is not a theorem of $$\mathsf{ZF}$$ and that some form of the Axiom of Choice is necessary to prove it. What is the proof-theoretic strength of $$\mathrm{IRT}$$ in this context?

Finally, if we modify $$\mathrm{IRT}$$ above by exchanging the sentence "Let $$A$$ be an infinite set" with "For any infinite set $$A$$"- does this change any of the results discussed in the first case above (i.e. when infinite means countably infinite)? What about the second case (i.e. when infinite means arbitray infinite)

1 Simpson, S. S., Subsystems of Second Order Arithmetic 2nd. ed. Cambridge University Press. Cambridge-New York (2009)

[2] Kleinberg, E. M., The independence of Ramsey's theorem. The journal of symbolic logic, vol. 34 (1969), pp. 205–206.

1. Note that $$\mathsf{FRT}$$ is both expressible and provable in $$\mathsf{PA}$$ (In fact, it is expressible as a $$\mathsf{I\Delta}_{0}(\exp_{2})$$-formula but it is independent of $$\mathsf{I\Delta}_{0}(\exp_{2})$$ - see [*] p.188). However, in Chapter II.1 of Metamathematics of first-order arithmetic, by Petr Hájek and Pavel Pudlák, it is shown that $$\mathsf{PA}^{-}+\mathsf{I\Sigma}_{1}^{0}$$ proves $$\mathrm{FRT}$$. Furthermore, it appears that $$\mathsf{EFA}$$ (i.e. $$\mathsf{I\Sigma}_{0}^{0}+\mathsf{exp}$$, exponentiation is totat) is what is minimally required to prove $$\mathrm{FRT}$$. Therefore, the proof-theoretic strength of $$\mathrm{FRT}$$ is $$\omega^{3}$$.
2. K. McAloon showed that over $$\mathsf{RCA}_{0}$$, $$\mathrm{IRT}$$ and $$\mathsf{ACA}_{0}^{'}$$ are equivalent (see K. MacAloon, Paris-Harrington incompleteness and progressions of theories, Proceedings of Symposia in Pure Mathematics 42(1985), 447-460). The proof theoretic strength of $$\mathrm{IRT}$$ is thus $$\varepsilon_{\omega}$$.
3. J.L. Hirst showed in his Ph.D. thesis that over $$\mathsf{RCA}_{0}$$, $$\mathrm{IRT}(1)$$ and $$\mathsf{B\Pi}_{1}^{0}$$(equivalently $$\mathsf{B\Sigma}_{2}^{0})$$ are equivalent. It is also shown that $$\mathsf{WKL}_{0}$$ does not prove either $$\mathrm{IRT}(1)$$ or $$\mathrm{IRT}(2)$$. This seems to suggest that the proof-theoretic stregths of $$\mathrm{IRT}(1)$$ and $$\mathrm{IRT}(2)$$ correspond to ordinals at least $$\omega^{\omega}$$. But as I stated above, for $$p\ge 3$$ we know that the proof-theoretic ordinal of $$\mathrm{IRT}(p)$$ is $$\varepsilon_{0}$$. Hence, the proof-theoretic ordinals of $$\mathrm{IRT}(1)$$ and $$\mathrm{IRT}(2)$$ appear to lie between $$\omega^{\omega}$$ and $$\varepsilon_{0}$$. From this we have that the proof-theoretic ordinal of $$\mathrm{IRT}(1)$$ is between $$\omega^{\omega}$$ and $$\omega^{\omega^{\omega}}$$ and it may very well be precisely one of them. Regarding $$\mathrm{IRT}(2)$$, we have the following result.
4. It has been shown that over $$\mathsf{RCA}_{0}$$, $$\mathrm{IRT}(2)$$ does not imply $$\mathsf{ACA}_{0}$$ (see David Seetapun and Theodore A. Slaman, On the strength of Ramsey’s theorem, Notre Dame J. Formal Logic 36 (1995), no. 4, 570–582).
5. In The proof-theoretic strength of Ramsey's theorem for pairs and two colors, L. Patey and K. Yokoyama show that the case of $$\mathrm{IRT}(2)$$ when $$r=2$$ is simple enough that any consequence of its existence can be obtained purely finitistically (thus improving a result of Chong, Slaman and Yang that it does not imply $$\mathsf{I\Sigma}_{2}^{0}$$). This is rather interesting, since the case of $$\mathrm{IRT}(3)$$ when $$r=2$$ is already not finitistically reducible.