Proving Ackermann's Function is Not Primitive Recursive

[mathmari]

Hey!

I am looking at the proof that the Ackermann's function is not primitive recursive.

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 this we need the following properties concerning the values of $A$.

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

Thus the value of $A$ is greater than that of either of its arguments, $A$ is strictly monotonic in each argument, and the value of $x$ has a greater influence on the value of $A$ than does the value of $y$.

We will prove that Ackermann's function is not primitive recursive by showing that it "grows faster" than any primitive recursive function. That means that we need a precise way of comparing the "growth rate" of the two-variable function $A$ with that of an arbitrary $n-$variable function. What we shall attempt to do is show that for any given $n-$variable primitive recursive function $f$, there exists a natural number $k$ such that $$A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n) \tag {*}$$ for all values of $x_1, \dots , x_n$.
The proof is accomplished by induction on the number of compositions and primitive recursions needed to define the function $f$. In order to carry out the induction step of the proof, we need two auxiliary results. The results of these results ensures that if the functions $g_1, \dots , g_m$ and $h$ satisfy $(*)$, so does the function $f$ obtained from $g_1, \dots , g_m$ and $h$ by functional composition.

Lemma 1. Let the $n-$variable function $f=h \circ (g_1, \dots , g_m)$ be obtained from the functions $g_1, \dots , g_m$ and $h$ by composition. Assume the existence of natural numbers $k_1, \dots , k_m$, and $k_0$ such that $$A(k_i, \max (x_1, \dots , x_n)) > g_i (x_1, \dots , x_n) \text{ for } 1 \leq i \leq m\\ \text{ and } \\ A(k_0, \max (y_1, \dots , y_m )) > h(y_1, \dots , y_m)$$ for all $x_1, \dots , x_n$ and $y_1, \dots , y_m$. Define $k$ to be the natural number $\max (k_0, k_1, \dots , k_m)+2$. Then $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n)$ for all $x_1, \dots , x_n$.

Lemma 2. Let the $(n+1)-$variable function $f$ be defined by primitive recursion from the $n-$variable function $g$ and the $(n+2)-$variable function $h$, so that $$f(x_1, \dots , x_n, 0)=g(x_1, \dots , x_n) \\ f(x_1, \dots x_n, y+1)=h(x_1, \dots , x_n , y, f(x_1, \dots , x_n, y))$$ Assume the existence of natural numbers $k_g$ and $k_h$ such that $$A(k_g ,\max (x_1, \dots , x_n)) > g(x_1, \dots , x_n) \\ \text{ and } \\ A(k_h, \max (x_1, \dots , x_n , y , z)) > h(x_1, \dots , x_n , y, z)$$ for all $x_1, \dots ,x_n, y$ and $z$. Define $k$ to be the natural number $\max (k_g, k_h)+3$. Then $A(k, \max (x_1, \dots , x_n , y)) > f(x_1, \dots ,x_n , y)$ for all $x_1, \dots , x_n, y$. Theorem 1. For each $n-$variable primitive recursive function $f$, there exists a natural number $k$ such that $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n)$, for all $x_1, \dots , x_n$.

Proof. By iduction on the number of compositions and primitive recursions needed to define $f$. We use $\hat{x}$ to denote $\max (x_1, \dots , x_n)$.

Basis. If the derivation of $f$ requires no compositions or primitive recursions, three cases are possible.

1. If $f$ is the constant function whose value is $c$, choose $k=c$. Property $5$ then guarantees that $A(k, \hat {x})=A(c, \hat{x})>c=f(x_1, \dots , x_n)$.
   
2. If $f$ is the projection function whose valuee is $x_i$, choose $k=0$. Then $A(k,\hat{x})=A(0,\hat(x))=\hat(x)+1>x_i=f(x_1, \dots , x_n)$.
   
3. If $f$ is the successor function, choose $k=1$. Then $A(k,x)=A(1,x)>A(0,x)=x+1=f(x)$.

Induction step. Assume the statement of the theorem to be true for all functions requiring $w$ or fewer compositions and primitve recursions. Let $f$ be a function requiring a total of $w+1$ compositions and primitive recursions. Two cases are possible.

1. If $f$ is derived from functions $g_1, \dots , g_m$ and $h$ by composition, the induction hypothesis must apply to each of $g_1, \dots , g_m$, and $h$. Lemma $1$ then guarantees the existence of a number $k$ such that $A(k,\hat{x})>f(x_1, \dots , x_n)$.
   
2. If $f$ is derived from the functions $g$ and $h$ by primitive recursion, the induction hypothesis must apply to $g$ and $h$. Lemma $2$ then guarantees the existence of a number $k$ such that $A(k, \hat{x})>f(x_1, \dots , x_n)$.

Theorem $1$ provides a formal expression of the notopn that $A$ "grows faster" than any primitive recursive function. It is now a simple matter to establish:

Theorem 2. Ackermann's function is not primitive recursive.

Proof. Assume hat Ackermann's function is primitive recursive. Then according to Theorem 1, there must exist a natral number $k$ such that $$A(k, \max (x,y)) > A(x,y)$$ for all $x$ and $y$ . Setting $x=y=k$ then yields the contradiction $$A(k,k) > A(k,k)$$ from which we conclude that $A$ cannot be primitive recursive. ___________________________________________________________________________________________________________At the sentence:
"Thus the value of $A$ is greater than that of either of its arguments, $A$ is strictly monotonic in each argument, and the value of $x$ has a greater influence on the value of $A$ than does the value of $y$. "

• "the value of $A$ is greater than that of either of its arguments" are the properties $1$, $5$, or not?? (Wondering)
• "$A$ is strictly monotonic in each argument" are the propertis $2$, $3$, $6$, right?? (Wondering)
• Could you explain the part " the value of $x$ has a greater influence on the value of $A$ than does the value of $y$" ?? (Wondering)

At the part:
"We will prove that Ackermann's function is not primitive recursive by showing that it "grows faster" than any primitive recursive function. That means that we need a precise way of comparing the "growth rate" of the two-variable function $A$ with that of an arbitrary $n-$variable function. What we shall attempt to do is show that for any given $n-$variable primitive recursive function $f$, there exists a natural number $k$ such that $$A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n) \tag {*}$$ for all values of $x_1, \dots , x_n$.
The proof is accomplished by induction on the number of compositions and primitive recursions needed to define the function $f$. "

Could you explain to me why we want to show that for any given $n-$variable primitive recursive function $f$, there exists a natural number $k$ such that $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n) $ for all values of $x_1, \dots , x_n$ in order to show that the Ackermann's function "grows faster" than any primitive recursive function ?? (Wondering)

Also, why do we use induction on the number of compositions and primitive recursions needed to define the function $f$ ?? (Wondering) Could you explain to me the two Lemmas ?? (Wondering)

 

[Valkarie]

The two lemmas are used to show that if the functions $g_1, \dots , g_m$ and $h$ satisfy the property $(*)$, then so does the function $f$ obtained from $g_1, \dots , g_m$ and $h$ by functional composition. Lemma 1 states that if the $n-$variable function $f=h \circ (g_1, \dots , g_m)$ is obtained from the functions $g_1, \dots , g_m$ and $h$ by composition, and there exist natural numbers $k_1, \dots , k_m$, and $k_0$ such that for all values of $x_1, \dots , x_n$ and $y_1, \dots , y_m$ we have $$A(k_i, \max (x_1, \dots , x_n)) > g_i (x_1, \dots , x_n) \text{ for } 1 \leq i \leq m\\ \text{ and } \\ A(k_0, \max (y_1, \dots , y_m )) > h(y_1, \dots , y_m),$$ then defining $k$ to be the natural number $\max (k_0, k_1, \dots , k_m)+2$ will ensure that $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n)$ for all $x_1, \dots , x_n$. Lemma 2 states that if the $(n+1)-$variable function $f$ is defined by primitive recursion from the $n-$variable function $g$ and the $(n+2)-$variable function $h$, so that for all $x_1, \dots ,x_n, y$ and $z$ we have $$f(x_1, \dots , x_n, 0)=g(x_1, \dots , x_n) \\ f(x_1, \dots x_n, y+1)=h(x