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

Theorem

For every $y \in \N$:

$\map A {1, y} = y + 2$

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

Proof

Proceed by induction on $y$.

Basis for the Induction

Suppose $y = 0$.

Then:

\(\ds \map A {1, 0}\)

\(=\)

\(\ds \map A {0, 1}\)

Definition of Ackermann-Péter Function

\(\ds \)

\(=\)

\(\ds 2\)

Definition of Ackermann-Péter Function

This is the basis for the induction

$\Box$

Induction Hypothesis

This is the induction hypothesis:

Suppose that:

$\map A {1, y} = y + 2$

We need to show that:

$\map A {1, y + 1} = y + 3$

Induction Step

This is the induction step:

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

\(=\)

\(\ds \map A {0, \map A {1, y} }\)

Definition of Ackermann-Péter Function

\(\ds \)

\(=\)

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

Induction Hypothesis

\(\ds \)

\(=\)

\(\ds y + 3\)

Definition of Ackermann-Péter Function

$\Box$

Thus, by Principle of Mathematical Induction, the result holds for all $y$.

$\blacksquare$