Ackermann-Péter Function is not Primitive Recursive

== Theorem ==
The Ackermann-Péter function is not primitive recursive.
== Proof ==
Let $A : \N^2 \to \N$ denote the Ackermann-Péter function.
It suffices to show that, for every primitive recursive $f : \N^k \to \N$, there exists some $t_f \in \N$ such that:
:$\forall x_1, \dotsc, x_k \in \N: \map f {x_1, \dotsc, x_k} < \map A {t_f, \map \max {x_1, \dotsc, x_k}}$
For, if $A$ were primitive recursive, we would have:
:$\map A {t_A, t_A} < \map A {t_A, \map \max {t_A, t_A}} = \map A {t_A, t_A}$
which is a contradiction.
We will proceed by induction on the definition of $f$.
=== Basic Primitive Recursive Functions ===
If $f$ is the zero function, we have:
:$t_{\Zero} = 0$
as:
If $f$ is a successor function, we have:
:$t_{\Succ} = 1$
as:
If $f$ is a projection function, we have:
:$t_{\pr_j^k} = 0$
as:
=== Substitution ===
Suppose $f : \N^k \to \N$ is obtained by substitution from:
:$g_1, \dotsc, g_m : \N^k \to \N$
:$h : \N^m \to \N$
as:
:$\map f {x_1, \dotsc, x_k} = \map h {\map {g_1} {x_1, \dotsc, x_k}, \dotsc, \map {g_m} {x_1, \dotsc, x_k}}$
Let $t_g = \map \max {t_{g_1}, \dotsc, t_{g_m}}$
Then, we have:
:$t_f = t_h + t_g + 2$
For every $1 \le j \le m$:
Thus:
=== Primitive Recursion ===
Suppose $f : \N^{k + 1} \to \N$ is obtained by primitive recursion from:
:$g : \N^k \to \N$
:$h : \N^{k + 2} \to \N$
as:
:$\map f {x_1, \dotsc, x_k, z} = \begin{cases}
\map g {x_1, \dotsc, x_k} & : z = 0 \\
\map h {x_1, \dotsc, x_k, z - 1, \map f {x_1, \dotsc, x_k, z - 1}} & : z > 0
\end{cases}$
Then, we have:
:$t_f = \map \max {t_g, t_h} + 5$
It suffices to show that, for all $x_1, \dotsc, x_k, z \in \N$:
:$\map f {x_1, \dotsc, x_k, z} < \map A {\map \max {t_g, t_h} + 1, \map \max {x_1, \dotsc, x_k} + z}$
For:
In order to prove that statement, we will perform induction on $z$.
==== Basis for the Induction ====
First, suppose $z = 0$.
Then:
satisfying the basis for the induction.
==== Induction Hypothesis ====
The induction hypothesis is:
:$\map f {x_1, \dotsc, x_k, z} < \map A {\map \max {t_g, t_h} + 1, \map \max {x_1, \dotsc, x_k} + z}$
Assuming that, we want to show:
:$\map f {x_1, \dotsc, x_k, z + 1} < \map A {\map \max {t_g, t_h} + 1, \map \max {x_1, \dotsc, x_k} + z + 1}$
==== Induction Step ====
First, we will show that:
:$\map \max {x_1, \dotsc, x_k, z, \map f {x_1, \dotsc, x_k, z} } < \map A {\map \max {t_g, t_h} + 1, \map \max {x_1, \dotsc, x_k} + z}$
If the greatest among $\set {x_1, \dotsc, x_k, z, \map f {x_1, \dotsc, x_k, z} }$ is some $x_i$, then:
If it is $z$, then:
If it is $\map f {x_1, \dotsc, x_k, z}$, the statement holds by the induction hypothesis.
Thus, by Proof by Cases, the statement:
:$\paren 1 \quad \map \max {x_1, \dotsc, x_k, z, \map f {x_1, \dotsc, x_k, z} } < \map A {\map \max {t_g, t_h} + 1, \map \max {x_1, \dotsc, x_k} + z}$
is true.
Now:
Thus, the induction step is satisfied.
By the Principle of Mathematical Induction, it holds that:
:$\map f {x_1, \dotsc, x_k, z} < \map A {\map \max {t_g, t_h} + 1, \map \max {x_1, \dotsc, x_k} + z}$
for all $z \in \N$.
So, the case is concluded by the remarks above.
By definition, every primitive recursive function $f$ must be obtainable from just those operations, and so necessarily satisfy the required property.
It follows from the remarks at the start of the proof that the Ackermann-Péter function is not primitive recursive.
Category:Ackermann-Péter Function
Category:Primitive Recursive Functions