importance of primitive recursion

Definition. Let $\mathcal{PR}_{0}$ be the smallest subset of the set $\mathcal{PR}$ of primitive recursive functions such that

1. 1.

(initial functions): $z,s,p_{m}^{k}\in\mathcal{PR}_{0}$ for all positive integers $m,k$ with $m\leq k$.

2. 2.

(closure under functional composition): if $f,g_{1},\ldots,g_{m}\in\mathcal{PR}_{0}$ with $f$ $m$-ary and $g_{i}$ $n$-ary, then the $n$-ary function $h:=f(g_{1},\ldots,g_{m})\in\mathcal{PR}_{0}$ as well.

From the definition above, we observe that any function $f(x_{1},\ldots,x_{n})$ obtained without the use of the successor function $s$ must be bounded by $\max\{x_{1},\ldots,x_{n}\}$. Now, since one application of $s$ increments the input by $1$, a finite applications of $s$ in the construction of $f$ results in $f$ being bounded by $\max\{x_{1},\ldots,x_{n}\}$ plus some fixed integer. This is the property we seek, and we prove it formally:

Proposition 1.

For any $f\in\mathcal{PR}_{0}$ with arity $n$, the following condition is satisfied:

(*) there is an integer $r\geq 0$ such that $f(x_{1},\ldots,x_{n})\leq\max\{x_{1},\ldots,x_{n}\}+r$.

Proof.

For each integer $n\geq 0$, let $\mathcal{X}_{n}$ be the subset of $\mathcal{PR}_{0}$ that contains all the initial functions, as well as functions derivable from the initial functions by applying functional composition at most $n$ times. The following facts are clear:

1. 1.

$\mathcal{X}_{0}$ is the set of all initial functions,

2. 2.

$\mathcal{X}_{n}\subseteq\mathcal{X}_{n+1}$,

3. 3.

and $\mathcal{PR}_{0}=\bigcup\{\mathcal{X}_{n}\mid n\in\mathbb{N}\}$, where $\mathbb{N}$ contains $0$ in this context.

We prove our assertion by induction  on $n$. In fact, we will prove a stronger assertion:

in the conditon (*) above, $r=n+1$ can be picked for every function in $\mathcal{X}_{n}$.

• For $n=0$, it is clear that all initial functions have the desired property: $r=0$ for $z$ and $p_{m}^{k}$, and $r=1$ for $s$. In either case, we can pick $r=1$.

• Suppose now that we can pick $r=i+1$ for any function in $\mathcal{X}_{i}$.

• Let $f$ be an $k$-ary function in $\mathcal{X}_{i+1}$. If $f\in\mathcal{X}_{i}$, then $r=i+1$ can be picked by assumption. Otherwise, $f=h(g_{1},\ldots,g_{m})$, where $h$ is $m$-ary, and each $g_{j}$ is $k$-ary. Furthermore, $g_{j}\in\mathcal{X}_{i_{j}}$, each $i_{j}\leq i$, and $h\in\mathcal{X}_{t}$, where $t=i-\max\{i_{1},\ldots,i_{m}\}$. Then, by assumption $g_{j}(x_{1},\ldots,x_{k})\leq x+i_{j}+1\leq x+\ell+1$ for all $j\in\{1,\ldots,m\}$, where $x=\max\{x_{1},\ldots,x_{k}\}$ and $\ell=\max\{i_{1},\ldots,i_{m}\}$. As a result,

 $\displaystyle f(x_{1},\ldots,x_{k})$ $\displaystyle=$ $\displaystyle h(g_{1}(x_{1},\ldots,x_{k}),\ldots,g_{m}(x_{1},\ldots,x_{k}))$ $\displaystyle\leq$ $\displaystyle\max\{g_{j}(x_{1},\ldots,x_{k})\mid j=1,\ldots,m\}+t+1$ $\displaystyle\leq$ $\displaystyle(x+\ell+1)+t+1=x+(i+1)+1.$

This proves the stronger assertion.

Now, if we pick any $f\in\mathcal{PR}_{0}$, then $f\in\mathcal{X}_{m}$ for some $m$ by the third fact above. The proof is now complete      by setting $r=m+1$. ∎

Now, we show the following:

Proposition 2.

$\mathcal{PR}_{0}\subset\mathcal{PR}$.

Proof.

We prove that $\operatorname{add}(x,y)=x+y$ does not have property (*) above. But if it does, then $\operatorname{add}(x,y)\leq\max\{x,y\}+r$ for some non-negative integer $r$. Then, for an arbitrary non-negative integer $n$, $2n=\operatorname{add}(n,n)\leq\max\{n,n\}+r=n+r$, so that $n\leq r$, a contradiction   (pick $n=r+1$)! ∎

In fact, the above proof shows the function $f(x)=2x$, simpler than addition in the sense that $f$ is unary, can not be defined in terms of the initial functions and functional composition alone. Primitive recursion is required at least once to define $f$.

Remark. In fact, one can obtain an infinite chain of subsets of $\mathcal{PR}$ in the following manner: $\mathcal{PR}_{n}$ is the smallest set of all primitive recursive functions generated by the initial functions, closed under functional composition, and at most $n$ applications of primitive recursion. Then

 $\mathcal{PR}_{n}\subset\mathcal{PR}_{n+1}\qquad\mbox{and}\qquad\mathcal{PR}=% \bigcup_{i=0}^{\infty}\mathcal{PR}_{i}$

For example, addition is in $\mathcal{PR}_{1}-\mathcal{PR}_{0}$, as was shown earlier. Furthermore, it is not hard to show that multiplication is in $\mathcal{PR}_{2}-\mathcal{PR}_{1}$, and exponentiation is in $\mathcal{PR}_{3}-\mathcal{PR}_{2}$. In fact, the Ackermann function  can be utilized to show that each $\mathcal{PR}_{n}\subset\mathcal{PR}_{n+1}$ is proper. Using this technique, it is possible to show that the Ackermann function is a total recursive function that is not primitive recursive. With respect to the set $\mathcal{ER}$ of elementary recursive functions, it can be shown that $\mathcal{ER}=\mathcal{PR}_{3}$.

Title importance of primitive recursion ImportanceOfPrimitiveRecursion 2013-03-22 19:05:21 2013-03-22 19:05:21 CWoo (3771) CWoo (3771) 12 CWoo (3771) Feature msc 03D20