4
$\begingroup$

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?

Thanks in advance!

1 Answers 1

2

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) 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}$