I am looking at the proof that the Ackermann's function is not primitive recursive.
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 ??
Also, why do we use induction on the number of compositions and primitive recursions needed to define the function $f$ ??
$$$$
EDIT:
The proof that the Ackermann's function is not primitive recursive is the following:
To prove this we need the following properties concerning the values of $A$.
-
$A(x,y)>y$.
-
$A(x,y+1)>A(x,y)$.
-
If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$.
-
$A(x+1, y) \geq A(x,y+1)$.
-
$A(x,y)>x$.
-
If $x_2>x_1$, then $A(x_2, y)>A(x_1, y)$.
-
$A(x+2, y)>A(x,2y)$.
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.
-
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)$.
-
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)$.
-
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.
-
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)$.
-
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.
Best Answer
We want to show that the Ackermann function is not primitive recursive. One way to show that is to show that it does not equal any of the primitive recursive functions. The "grows faster" argument accomplishes this. If the Ackermann function grows faster than any primitive recursive function, it doesn't equal any of them.
In order to make the "grows faster" argument, we have to compare the Ackermann function to all the primitive recursive functions. As the primitive recursive functions are defined with a tree structure using composition and primitive recursion, the induction allows us to cover them all in the same way that arithmetic induction lets us cover all the natural numbers.