Paris–Harrington theorem

A strengthened finite Ramsey theorem asserting that sufficiently large finite sets contain homogeneous subsets whose size is at least their least element. Its natural-number formulation is true but unprovable in Peano arithmetic.

Finite Ramsey theorem: A theorem stating that sufficiently large finite structures contain large homogeneous substructures. The Paris–Harrington theorem strengthens this finite combinatorial result.
Jeff Paris: A British mathematician and logician known for work in mathematical logic and proof theory. He co-discovered the theorem that bears his name.
First-order logic: A formal language and proof system for statements about objects, relations, and quantifiers. The theorem’s arithmetic formulation is expressed in first-order logic.
Goodstein's theorem: A theorem stating that every Goodstein sequence of natural numbers eventually reaches zero. Like Paris–Harrington, it is true but unprovable in Peano arithmetic.
Infinite Ramsey theorem: A theorem asserting that finite colorings of fixed-size subsets of an infinite set admit an infinite homogeneous subset. Its infinite conclusion differs from the strengthened theorem’s finite conclusion.
Ramsey theory: The study of conditions that force order or homogeneous structure within sufficiently large systems. The theorem is a finitary result in this broader area.
Leo Harrington: An American mathematician and logician whose work includes recursion theory and mathematical logic. He co-discovered the theorem with Jeff Paris.
Mathematical induction: A proof principle establishing a property for all natural numbers from a base case and an inductive step. Peano arithmetic includes induction, yet cannot prove the theorem.
Ordinal analysis: A proof-theoretic method that measures formal theories using ordinal notations. It helps explain why Peano arithmetic cannot establish the theorem.
Compactness theorem: A first-order theory has a model if every finite subset of its sentences has a model. Compactness helps connect finite combinatorial assertions with formal theories and their models.

Linked from 4 pages

Gödel's first incompleteness theoremBroader topic: The first natural combinatorial independence result, published in 1977.