Paris-Harrington Theorem

The Paris-Harrington theorem is a strengthened version of the finite Ramsey theorem that is true but unprovable in Peano Arithmetic. Proved by Jeff Paris and Leo Harrington in 1977, it states that for any positive integers n, k, m, there exists an integer N such that if the n-element subsets of {1, ..., N} are colored with k colors, there exists a monochromatic subset of size at least m that is relatively large — its size exceeds its minimum element.

The relative largeness condition appears minor, but it is precisely what pushes the statement beyond the proof-theoretic strength of Peano Arithmetic. The proof requires transfinite induction up to ε₀, the ordinal Gentzen identified as the exact boundary of PA's consistency. The Paris-Harrington theorem is thus a concrete, finitary combinatorial statement whose truth outstrips the axioms of standard arithmetic — a bridge between proof theory and combinatorics built from graph colorings alone.