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

Theorem

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

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

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

Proof

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

\(>\)

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

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

\(\ds \)

\(=\)

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

Ackermann-Péter Function at (2,y)

\(\ds \)

\(>\)

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

\(\ds \)

\(\ge\)

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

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

$\blacksquare$