View source for Paris-Harrington Theorem

The '''Paris-Harrington theorem''' is a strengthened version of the finite [[Ramsey Theory|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|proof theory]] and [[Combinatorics|combinatorics]] built from graph colorings alone.

[[Category:Mathematics]]
[[Category:Logic]]
[[Category:Combinatorics]]