Properties of Ackermann's function

594 Views Asked by At

I want to show the following properties of Ackermann's function:

  1. $A(x,y)>y$.

  2. $A(x,y+1)>A(x,y)$.

  3. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$.

  4. $A(x+1, y) \geq A(x,y+1)$.

  5. $A(x,y)>x$.

  6. If $x_2>x_1$, then $A(x_2, y)>A(x_1, y)$.

  7. $A(x+2, y)>A(x,2y)$.

I'm looking for hints to prove the properties $3$ and $6$. I think that I should use properties $2$ and $4$ respectively but I'm unsure how to do so.

My try for $3$

By induction on $x$, for the base case $x = 0$ we have:

$y_2 > y_1 \implies A(0,y_2)=y_2+1>y_1+1=A(0,y_1)$

where we have used the inequality in the hypothesis and the definition of the Ackermann's function.

For the inductive hypothesis, assuming the property holds for $x=n$, that means:

$y_2 > y_1 \implies A(n,y_2)>A(n,y_1)$ (I.H)

in the inductive step we want to show that:

$y_2 \implies A(n+1,y_2)>A(n+1,y_1)$.

I don't know how to continue from here.

My try for $5$

By $4$, we have:

$A(x+1, y) \geq A(x,y+1)$

So, we have:

$A(x,y) \geq A(x-1, y+1) \geq A(x-2, y+2) \geq \dots \geq A(0,x+y)=x+y+1>x$.

How can I formalize this reasoning.