This result has been described by some (such as the editor of the Handbook of Mathematical Logic in the references below) as the first "natural" example of a true statement about the integers that could be stated in the language of arithmetic, but not proved in Peano arithmetic; it was already known that such statements existed by Gödel's first incompleteness theorem.
The strengthened finite Ramsey theorem is a statement about colorings and natural numbers and states that: 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 in
The strengthened finite Ramsey theorem can be proven assuming induction up to
It is provable in second-order arithmetic (or the far stronger Zermelo–Fraenkel set theory) and so is true in the standard model.
The smallest number N that satisfies the strengthened finite Ramsey theorem is then a computable function of n, m, k, but grows extremely fast.