Finite Ramsey theorem in arithmetic

Question

How much induction is needed to prove finite Ramsey theorem in PA?

I searched for a while but in vain.

Answer 1

$I\Sigma_1$ - the ordered semiring axioms plus induction for $\Sigma_1$ formulas - is certainly enough. The standard proof goes through unchanged in $I\Sigma_1$, the key points being:

• The reduction to the two-color case is trivial.

• The formula we apply induction to in the two-color case is "There is some $n$ such that any $2$-coloring of the $s$-element subsets of $\{0,...,n\}$ has a homogeneous set of size $r$." This goes through in $I\Sigma_1$ (note that there's only one truly unbounded quantifier here, since the number of $s$-element subsets and $2$-colorings of $s$-element subsets of $\{0,...,n\}$ is bounded by a function whose totality is provable in $I\Sigma_1$).

But we can do better: by proving a stronger result (the exponential upper bound) we get rid of that unbounded quantifier. So $I\Delta_0+exp$ is already enough.

---

I believe this is treated in more detail in Hajek/Pudlak, Metamathematics of first-order arithmetic (and even if it's not I strongly recommend that book, it's wonderful).