The Paris-Harrington theorem is a theorem giving rise to a fast-growing function[1].
For all positive integers \(n\), \(k\), \(m\), there exists an integer \(N\) such that for any coloring of any of the \(n\)-element subsets of \(S=\{a:0<a<N\}\) with \(k\) colors, there exists \(Y\subseteq S\) such that:
- All \(n\)-element subsets of \(Y\) are monochromatic
- \(m\le\vert Y\vert\ge\textrm{min}(Y)\), where \(\vert Y\vert\) denotes cardinality of \(Y\).
Kirby and Paris have proved that this theorem is unprovable in Peano arithmetic.
Fast-growing function[]
We can extract a fast-growing function from this theorem:
- Let \(f(x)\) be the smallest integer \(N\) where the Paris-Harrington theorem holds with \(k=n=x\) and \(m=x+1\).
This function dominates all functions provably recursive in Peano arithmetic[1].