Paris-Harrington theorem

The Paris-Harrington theorem is a theorem giving rise to a fast-growing functionBovykin, Andrey I. and Weisstein, Eric W. "Paris-Harrington Theorem." From MathWorld--A Wolfram Web Resource. . Accessed 2021-04-27.
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 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.
==Sources==
Category:Functions
Category:Theorems