View source for Paris–Harrington theorem

{{Short description|Theorem that a certain principle in Ramsey theory is true, but not provable in Peano arithmetic}}
In [[Mathematical logic|mathematical logic]], the '''Paris–Harrington theorem''' states that a certain combinatorial principle in [[Ramsey theory]], namely the strengthened finite Ramsey theorem, which is expressible in Peano arithmetic, is not provable in this system. The combinatorial principle is however provable in slightly stronger systems.

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.

==Strengthened finite Ramsey theorem==
The strengthened finite Ramsey theorem is a statement about colorings and natural numbers 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 [[Ramsey's theorem|finite Ramsey theorem]] in <math>K_{\mathcal{P}_n(S)}</math>, with ''N'' given by:
:<math>\binom{N}{n} = |\mathcal{P}_n(S)| \ge R(\,\underbrace{ m, m, \ldots , m }_k\,).</math>

Moreover, the strengthened finite Ramsey theorem can be deduced from the [[Ramsey's theorem#Infinite graphs|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|second-order arithmetic]].

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

==Paris–Harrington theorem==
Roughly speaking, Jeff Paris and [[Biography:Leo Harrington|Leo Harrington]] (1977) showed that the strengthened finite Ramsey theorem is unprovable in Peano arithmetic by showing that in Peano arithmetic it implies the consistency of Peano arithmetic itself. Since Peano arithmetic cannot prove its own consistency by [[Gödel's incompleteness theorems#Second incompleteness theorem|Gödel's second incompleteness theorem]], this shows that Peano arithmetic cannot prove the strengthened finite Ramsey theorem.

The combinatorial principle can be proven assuming [[Transfinite induction|induction]] up to <math>\varepsilon_0</math> for a relevant classes of formulas. Alternatively, it can be proven assuming the [[Reflection principle|reflection principle]], for the arithmetic theory, for [[Arithmetical hierarchy|<math>\Sigma 1^0</math>-sentences]]. The reflection principle also implies the consistency of Peano arithmetic. It is provable in [[Second-order arithmetic|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|computable function]] of ''n'', ''m'', ''k'', but grows extremely fast. In particular it is not [[Primitive recursive function|primitive recursive]], but it is also far faster-growing than standard examples of non-primitive recursive functions such as the [[Ackermann function]]. It dominates every computable function provably total in Peano arithmetic,<ref>J. Ketonen, R. Solovay, "[https://www.jstor.org/stable/2006985 Rapidly Growing Ramsey Functions]". Annals of Mathematics vol. 113 (1981), pp.267--314.</ref> which includes functions such as the Ackermann function.

==See also==
* [[Goodstein's theorem]]
* [[Kanamori–McAloon theorem]]
* [[Kruskal's tree theorem]]

==References==
{{Reflist}}
* {{cite book |first=David |last=Marker |title=Model Theory: An Introduction |location=New York |publisher=Springer |year=2002 |isbn=0-387-98760-6 }}
* [http://mathworld.wolfram.com/Paris-HarringtonTheorem.html mathworld entry]
* {{cite book |last=Paris |first=J. |last2=Harrington |first2=L. |chapter=A Mathematical Incompleteness in Peano Arithmetic |title=Handbook of Mathematical Logic |editor-first=J. |editor-last=Barwise |location=Amsterdam, Netherlands |publisher=North-Holland |year=1977}}

==External links==
* [https://www.aemea.org/math/Intro_to_unprovability.pdf ''A brief introduction to unprovability''] (contains a proof of the Paris–Harrington theorem) by [https://web.archive.org/web/20110807192747/http://www.maths.bris.ac.uk/~maaib/ Andrey Bovykin]

{{DEFAULTSORT:Paris-Harrington Theorem}}
[[Category:Theorems in the foundations of mathematics]]

{{Sourceattribution|Paris–Harrington theorem}}