Paris–Harrington theorem

In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic. This was 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 ${\displaystyle K_{{\mathcal {P}}_{n}(S)}}$, with N given by:

Moreover, the strengthened finite Ramsey theorem can be deduced from the infinite Ramsey theorem 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 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.

...
Wikipedia