# Ackermann-Péter Function: Proof by induction that A(x,y) < A(x,y+1)

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$

I want to prove by induction over x that $$A(x,y) < A(x,y+1) \; \forall x,y \in \mathbb{N}$$

Basis: $x = 0$

$$A(0,y) = y+1 < y+2 = A(0,y+1)$$

So far so easy, but I'm completely stuck with the induction step. Could you please help me to go on?

-

I'll just detail the induction step on $x$.

Let's suppose that $\ \displaystyle A(x,y) < A(x,y+1)\ \forall y \in \mathbb{N}\$ and notice that this implies that $\ \displaystyle A(x,y) < A(x,w)\ \forall y,w \in \mathbb{N} |w>y$.

Then :
$A(x+1,0)=A(x,1)\$ and $\ A(x+1,1)=A(x,A(x+1,0))=A(x,A(x,1))$

Notice that the smallest possible result is $0+1=1$ and since $\ 1\le A(x,0)<A(x,1)$ we deduce $1 < A(x,1)$ and infer (by considering $y=1,\ w=A(x,1)$ in the induction hypothesis) that $\ A(x+1,0) < A(x+1,1)$

Let's do a induction on $y$ too and suppose that $A(x+1,z) < A(x+1,z+1)$ for $0\le z\le y\$ then :

$A(x+1,y+1)=A(x,A(x+1,y))\$ and $\ A(x+1,y+2)=A(x,A(x+1,y+1))$

but we supposed that $\ A(x+1,y) < A(x+1,y+1)\$ so that we may use our induction on $x$ again to conclude that $\ A(x+1,y+1) < A(x+1,y+2)\$ and that : $$\ A(x+1,y) < A(x+1,y+1)\ \ \forall\; y \in \mathbb{N}$$

-