---
tag: 509ZWA0R26
kind: statement
role: theorem
name: Paris–Harrington theorem
msc: [03F30, 05D10]
uses: [0QFT7Z76N5]
about: [0QFT7Z76N5]
sources:
  - url: https://en.wikipedia.org/wiki/Paris–Harrington_theorem
same_as:
  wikidata: Q7137494
  wikipedia: Paris–Harrington theorem
---

## Statement

Call a finite set $Y \subseteq \N$ *large* if $\abs{Y} \ge \min Y$.
The *strengthened finite Ramsey theorem* $\mathrm{PH}$ is the following statement.
For all positive integers $n$, $k$, $m$ there is an integer $N$ with this property.
For every colouring of the $n$-element subsets of $\set{1, 2, \ldots, N}$ with $k$ colours, there is a large set $Y \subseteq \set{1, \ldots, N}$ with $\abs{Y} \ge m$.
Moreover, all $n$-element subsets of $Y$ have the same colour.

1. $\mathrm{PH}$ is true; it follows from the infinite Ramsey theorem.
2. $\mathrm{PH}$, written as a sentence of first-order arithmetic, is not provable in [[Peano arithmetic|0QFT7Z76N5]] $\mathsf{PA}$.

## Remarks

Part 1 is a compactness argument.
If $\mathrm{PH}$ failed for some $n, k, m$, the bad colourings for larger and larger $N$ would fit together by König's lemma.
They would give a colouring of the $n$-element subsets of $\N$ whose restriction to each $\set{1, \ldots, N}$ is bad.
The infinite Ramsey theorem gives an infinite homogeneous set $H$ for it.
An initial segment of $H$ with $\max(m, \min H)$ elements is then large and homogeneous, a contradiction.
Part 2 is proved with models.
In a non-standard model of $\mathsf{PA}$, $\mathrm{PH}$ gives initial segments that are themselves models of $\mathsf{PA}$.
From this, $\mathsf{PA}$ plus $\mathrm{PH}$ proves the consistency of $\mathsf{PA}$.
The function that sends $(n, k, m)$ to the least $N$ grows faster than every function that $\mathsf{PA}$ proves total.

Without the word "large", the statement is the ordinary finite Ramsey theorem, which is provable in $\mathsf{PA}$.

## Explanations

### L1 human

The theorem gives a natural statement about colouring finite sets that is true but cannot be proved from the usual axioms of arithmetic.
It differs from the finite Ramsey theorem by one small demand: the same-coloured set must have at least as many elements as its smallest member.
This small change makes the required numbers grow so fast that arithmetic cannot prove they exist.

### L2 human

Paris and Harrington proved the theorem in 1977.
It was one of the first natural examples from combinatorics of a true statement independent of $\mathsf{PA}$, after the artificial sentences of [[Gödel's incompleteness theorems|X9WYNYE29C]].
[[Goodstein's theorem|XQMNJF241J]] is another example of the same kind.