Strict Upper Bound for Composition of Ackermann-Péter Functions

Theorem

For all $x, y, z \in \N$:

$\map A {x + y + 2, z} > \map A {x, \map A {y, z}}$

where $A$ is the Ackermann-Péter function.

Proof

We have:

$x + y + 1 > y$

giving us:

$\paren 1 \quad \map A {x + y + 1, z} > \map A {y, z}$

by Ackermann-Péter Function is Strictly Increasing on First Argument.

Therefore:

\(\ds \map A {x + y + 2, z}\)

\(\ge\)

\(\ds \map A {x + y + 1, z + 1}\)

Increasing Second Argument of Ackermann-Péter Function is Not Greater than Increasing First Argument

\(\ds \)

\(=\)

\(\ds \map A {x + y, \map A {x + y + 1, z} }\)

Definition of Ackermann-Péter Function

\(\ds \)

\(>\)

\(\ds \map A {x + y, \map A {y, z} }\)

Ackermann-Péter Function is Strictly Increasing on Second Argument and $\paren 1$

\(\ds \)

\(\ge\)

\(\ds \map A {x, \map A {y, z} }\)

Ackermann-Péter Function is Strictly Increasing on First Argument

$\blacksquare$