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:

  1. All \(n\)-element subsets of \(Y\) are monochromatic
  2. \(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].

Sources

  1. 1.0 1.1 Bovykin, Andrey I. and Weisstein, Eric W. "Paris-Harrington Theorem." From MathWorld--A Wolfram Web Resource. [1]. Accessed 2021-04-27
Community content is available under CC-BY-SA unless otherwise noted.