---
tag: 4P2BAT6YC3
kind: statement
role: theorem
name: Strengthened finite Ramsey theorem
sources:
  - wikipedia: en:3875355@r1367028911
    locator: Paris–Harrington theorem, section Strengthened finite Ramsey theorem
    note: adopted
    mention: wikipedia://en/3875355#63IX
    sections: [Statement]
inventory: [AC9YJ8WWJ9]
---

## Statement

The strengthened finite Ramsey theorem is a statement about colorings and [[natural numbers|0MWKJ44V5A]] and states that:

For any positive integers *n*, *k*, *m*, such that *m ≥ n*, one can find *N* with the following property: if we color each of the *n*-element subsets of *S* = {1, 2, 3,..., *N*} with one of *k* colors, then we can find a subset *Y* of *S* with at least *m* elements, such that all *n*-element subsets of *Y* have the same color, and the number of elements of *Y* is at least the smallest element of *Y*.

Without the condition that the number of elements of *Y* is at least the smallest element of *Y*, this is a corollary of the [[finite Ramsey theorem|00TQV3F5S4]] in $K_{\mathcal{P}_n(S)}$, with *N* given by:

$$\binom{N}{n} = |\mathcal{P}_n(S)| \ge R(\,\underbrace{ m, m, \ldots , m }_k\,).$$

Moreover, the strengthened finite Ramsey theorem can be deduced from the [[infinite Ramsey theorem|00TQV3F5S4]] in almost exactly the same way that the finite Ramsey theorem can be deduced from it, using a compactness argument (see the article on [[Ramsey's theorem|00TQV3F5S4]] for details). This proof can be carried out in second-order arithmetic.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic.