Proving a Relation with Two Variables: A(x,y)>y

[mathmari]

Hey!

How can we prove by induction the relation $A(x,y)>y, \forall x,y$ ?? (Wondering)

When we have to prove a relation $P(n), n\geq 0$, we do the following steps:

• we show that it stands for $n=0$
  
• we assume that it stands for n=k (Induction hypothesis)
  
• we want to shw that it stands for $n=k+1$ using the Induction hypothesis.

Which are the steps in this case where we have two variables?? (Wondering)

 

[mathmari]

Are the steps the following:

• For x=0 we show that it holds for y=0, we assume that it holds for y=k and then we show that it holds for y=k+1.
  
• We assume that it holds for all x<=j.
  
• To show that it holds for x=j+1 we show that it holds for y=0, we assume that it holds for y=k and then we show that it holds for y=k+1.

?? (Wondering)

 

[alyafey22]

This blog might help.

 

[Andrei1]

Which are the steps in this case where we have two variables?? (Wondering)

For example, the division algorithm theorem has the form \(\displaystyle \forall m\in\mathbb{N}^*\forall n\in\mathbb{N}A(n,\ m)\). Here we let \(\displaystyle m\) be some arbitrary positive natural number and then we can prove \(\displaystyle \forall n\in\mathbb{N}A(n,\ m)\) by induction on \(\displaystyle n\) (strong induction).

 

[Evgeny.Makarov]

How can we prove by induction the relation $A(x,y)>y, \forall x,y$ ?

Is $A(x,y)$ the Ackermann function by chance?

There are several ways of proving $\forall m,n.\,P(m,n)$ by induction.

(1) Fix an arbitrary $m$ as in a direct proof and prove $\forall n.\,P(m,n)$ by induction on $n$. Then in proving the induction step $P(m,n+1)$ one can only to use the induction hypothesis $P(m,n)$ for the same $m$.

(2) Fix an arbitrary $n$ and prove $\forall m.\,P(m,n)$ by induction on $m$. This is similar to (1).

(3) Prove the statement $\forall n.\,P(m,n)$ by induction on $m$. Compared to (2), in the induction step one has to prove $\forall n.\,P(m+1,n)$ and not just $P(m+1,n)$ for some previously fixed $n$. However, this is irrelevant since $n$ is arbitrary anyway. But in this case one has a stronger induction hypothesis: $\forall n.\,P(m,n)$ versus $P(m,n)$ in (2). This means that in proving $P(m+1,n)$ one can use the hypothesis $P(m,n')$ for any $n'$, not necessarily equal to $n$. In other words, whereas in (2) the parameter $n$ is fixed throughout the proof, in this method one can use the induction hypothesis with a different value of the parameter. For some statements, this type of induction goes through while (2) does not.

(4) Prove the statement $\forall m.\,P(m,n)$ by induction on $n$. This is better than (1) similarly to how (3) is better than (2).

(5) Use nested induction: external on $m$ and internal on $n$. This is what you described in post #2. This is even more powerful than (3): one has the same induction hypothesis $\forall n.\,P(m,n)$, but one proves $\forall n.\,P(m+1,n)$ by induction on $n$ and not using a direct proof (the latter doesn't always work).

(6) Use nested induction: external on $n$ and internal on $m$. This is similar to (5).

In each case, induction can be regular or strong.

Usually it is not much work to start with simpler methods and move to more powerful when needed. Or start with (3) or (4). Proofs about Ackermann function often require nested induction.

 

[mathmari]

Is $A(x,y)$ the Ackermann function by chance?

Yes, it is...

The Ackermann's function satisfies the following relations:
$$A(0,y)=y+1, \forall y \\ A(x,0)=A(x-1,1), \forall x \geq 1 \\ A(x,y)=A(x-1, A(x,y-1)), \forall x,y \geq 1$$

To prove the property that $A(x,y) >y$ we use induction on $x$.

Base case: For $x=0$ we have $A(0,y)=y+1$.
Can we say that $A(0,y)=y+1>y, \forall y$ or do we have to prove by induction on $y$ ?? (Wondering)

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

Inductive step: To show that $A(n+1,y)>y$ we use induction on $y$.

Base case: For $y=0$ we have that $A(m+1,0)=A(m,1)\overset{ \text{ I.H.x }}{>}1>0 \Rightarrow A(m+1,0)>0$.

Inductive hypothesis: We assume that it stands for $y=m$, that means that $A(n+1,m)>m$. (I.H.y)

Inductive step: $A(n+1, m+1)=A(n,A(n+1,m))\overset{ \text{ I.H.x }}{>} A(n+1, m) \overset{ \text{ I.H.y }}{>}m \Rightarrow A(n+1, m+1)>m \Rightarrow A(n+1, m+1) \geq m+1$.
​

Is this correct?? (Wondering)

Could I improve something?? (Wondering)

 

[Evgeny.Makarov]

Obviously, showing $A(n+1,m+1)\ge m+1$ is not enough since you need $A(n+1,m+1)> m+1$. But $x>y>z$ implies $x>z+1$ for integer $x,y,z$.

 

[mathmari]

Obviously, showing $A(n+1,m+1)\ge m+1$ is not enough since you need $A(n+1,m+1)> m+1$. But $x>y>z$ implies $x>z+1$ for integer $x,y,z$.

So, is it as followed?? (Wondering)

Base case: For $x=0$ we have $A(0,y)=y+1>y, \forall y$.

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

Inductive step: To show that $A(n+1,y)>y$ we use induction on $y$.

Base case: For $y=0$ we have that $A(m+1,0)=A(m,1)\overset{ \text{ I.H.x }}{>}1>0 \Rightarrow A(m+1,0)>0$.

Inductive hypothesis: We assume that it stands for $y=m$, that means that $A(n+1,m)>m$. (I.H.y)

Inductive step: $A(n+1, m+1)=A(n,A(n+1,m))\overset{ \text{ I.H.x }}{>} A(n+1, m) \overset{ \text{ I.H.y }}{>}m \Rightarrow A(n+1, m+1)>A(n+1, m)>m \Rightarrow A(n+1, m+1)>m+1$.
​

Or could I improve something?? (Wondering)

 

[Evgeny.Makarov]

This is correct.