MHB Properties of Ackermann's function

[mathmari]

Hey!

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 have done the following:

1. Induction on $x$.
   
2. Induction on $x$.
   Base case: For $x=0$ we have $A(0,y+1)=y+2>y+1=A(0,y)$, by the definition of $A$.
   
   Inductive hypothesis: We assume that it holds for $x=n$, that means $A(n,y+1)>A(n,y)$ (I.H.x)
   
   Inductive step: We want to show that $A(n+1, y+1)>A(n+1,y)$.
   By the definition of $A$ and by the property $1$ we have $A(n+1, y+1)=A(n,A(n+1, y))>A(n+1,y)$.
   
3. 
   
4. Induction on $y$.
   Base case: For $y=0$ we have $A(x+1, 0)=A(x,1)=A(x,0+1)$.
   
   Inductive hypothesis: We assume that it holds for $y=m$, that means $A(x+1, m) \geq A(x,m+1)$ (I.H.)
   
   Inductive step: We want to show that $A(x+1, m+1) \geq A(x,m+2)$.
   By the definition we have $A(x+1, m+1)=A(x,A(x+1, m))$. By the (I.H.) and the property $1$ we have $A(x+1, m) \geq A(x,m+1)>m+1 \Rightarrow A(x+1, m) \geq A(x,m+1) \geq m+2$. By the property $3$ we have $A(x,A(x+1,m)) \geq A(x,m+2)$. So, we cocnlude that $A(x+1, m+1) \geq A(x,m+2)$.
   
5. By the property $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$.
   But how can we prove this formally??
   
6. 
   
7. Induction on $y$.
   Base case: For $y=0$ we have by the property $6$ $A(x+2, 0)>A(x,0)=A(x,2 \cdot 0)$.
   
   Inductive hypothesis: We assume that it holds for $y=m$, that means $A(x+2, m)>A(x,2m)$ (I.H.)
   
   Inductive step: We want to show that $A(x+2, m+1) > A(x,2(m+1))$.
   By the definition of $A$ we have $A(x+2, m+1)=A(x+1, A(x+2, m))$. By the (I.H.) we have $A(x+2, m)>A(x,2m)$. By the property $3$ we have $A(x+2, m+1)>A(x+1, A(x,2m))$. By the property $4$ we have $A(x+1, A(x,2m)) \geq A(x,A(x,2m)+1)$ According to the property $1$, $A(x,2m)>2m \Rightarrow A(x,2m) \geq 2m+1$ or equivalently $A(x,2m)+1 \geq 2m+2=2(m+1)$. By the property $3$ we have $A(x,A(x,2m)+1) \geq A(x,2(m+1))$. So, $A(x+2, m+1)>A(x,2(m+1))$.

Is this correct?? Could I improve something?? (Wondering)

Could you give me some hints to prove the properties $3, 6$ ?? (Wondering)

 

[mathmari]

At the proof of the properties $3$ and $6$ do we use the properties $2$ and $4$ respectively?

But how? (Wondering)

For example, for the property $3$ would the proof be as follows?

Induction on $x$.

Base case: For $x=0$ we have $A(0,y_2)=y_2+1>y_1+1=A(0,y_1)$

Inductive hypothesis: We assume that it holds for $x=n$, that means $A(n,y_2)>A(n,y_1)$ (I.H)

Inductive step: We want to show that $A(n+1,y_2)>A(n+1,y_1)$.

How can we continue?

 

[mathmari]

I tried again to prove the property $3$:

$y_2>y_1 \Rightarrow y_2=y_1+d, d>0 \Rightarrow d=y_2-y_1>0$

Induction on $d$.

Base case: For $d=1$ we have $A(x, y_2)=A(x, y_1+1) \overset{(2)}{>}A(x, y_1)$.

Inductive hypothesis: We assume that it holds for $d=k$, that means that $A(x, y_2)=A(x, y_1+k)>A(x, y_1)$ (I.H.)

Inductive step: We want to show that $A(x, y_1+(k+1))>A(x, y_1)$
$A(x, y_1+k+1)=A(x, (y_1+k)+1)\overset{(2)}{>}A(x, y_1+k)\overset{ (I.H.) }{>}A(x, y_1)$ Is this correct? Could I improve something? (Wondering)

The proof of the property $6$ is similiar, isn't it?

On which variable do we use the induction for the property $5$ ?

 

[mathmari]

For the property $5$ do we do the following?

We will show that $$A(x, y) \geq A(0, x+y)$$ by induction on $k=x+y$. Base case: For $k=0$ we have $x=y=0$, so $A(0, 0) \geq A(0, 0)$.

Inductive hypothesis: We assume that it stands for $k=n$, $A(x, y) \geq A(0, n)$. (I.H.)

Inductive step: We will show that it stands for $k=n+1$, $x+1+y=n+1$, that means that $A(x+1, y) \geq A(0, n+1)=(n+1)+1=n+2$.
We have that $A(x+1, y) >A(x, y) \overset{ (I.H.) }{\geq} A(0, n)=n+1$.
$A(x+1, y)>n+1 \Rightarrow A(x+1, y) \geq n+2$. So, we have that $A(x, y) \geq A(0, x+y)=x+y+1>x+y$. Is this correct?