Fast-Growing Hierarchy Growth Bound Theorem

The Fast-Growing Hierarchy Growth Bound Theorem is an important result in mathematical logic that has significant implications for unprovability results. The theorem highlights a relationship between computable functions that are provably total in first-order Peano Arithmetic (PA) and the fast-growing functions in the Wainer hierarchy.

The theorem is based on work by several mathematicians. Georg Kreisel laid the groundwork in 1952 by investigating connections between recursions over well ordered sets and proofs in PA. These results were subsequently extended by many others; the following form is based on the presentation by Buchholz and Wainer.

Statement

Let $T$ be a Turing machine that computes a function $g:\mathbb {N} \to \mathbb {N}$, terminating on every input. Suppose that PA can prove the statement «$T$ terminates on every input.» Then $g$ cannot grow too fast: There exist $\alpha <\varepsilon _{0}$ and $n_{0}\in \mathbb {N}$ such that $g(n)<F_{\alpha }(n)$ for every $n\geq n_{0}$.

References

Wilfried Buchholz and Stan S. Wainer. Provably computable functions and the fast growing hierarchy. In S. G. Simpson, editor, Logic and Combinatorics, volume 65 of Contemporary Mathematics, pages 179–198. AMS, 1987. [1]