Ackermann-Péter Function is Strictly Increasing on First Argument/General Result
Jump to navigation
Jump to search
Theorem
Forall $x, y, z \in \N$ such that:
- $x < y$
we have:
- $\map A {x, z} < \map A {y, z}$
where $A$ is the Ackermann-Péter function.
Proof
Let $y$ be expressed as:
- $y = x + k$
for some $k \in \N_{>0}$.
Proceed by induction on $k$.
Basis for the Induction
Suppose $k = 1$.
Then:
- $\map A {x, z} < \map A {x + 1, z}$
by Ackermann-Péter Function is Strictly Increasing on First Argument.
This is the basis for the induction.
$\Box$
Induction Hypothesis
The induction hypothesis is:
- $\map A {x, z} < \map A {x + k, z}$
We want to show:
- $\map A {x, z} < \map A {x + k + 1, z}$
Induction Step
\(\ds \map A {x + k + 1, z}\) | \(>\) | \(\ds \map A {x + k, z}\) | Ackermann-Péter Function is Strictly Increasing on First Argument | |||||||||||
\(\ds \) | \(>\) | \(\ds \map A {x, z}\) | Induction Hypothesis |
Thus, the induction step is satisfied.
$\Box$
Thus, by Principle of Mathematical Induction, the result holds forall $x, y, z \in \N$.
$\blacksquare$