importance of primitive recursion

In this entry, we show that the operation of primitive recursion is an important ingredient in the definition of primitive recursive functions. Very basic arithmetic functions, such as addition, depend on primitive recursion in an essential way. One can not go very far without it.

One way to prove this is to come up with a property on those functions which are derivable from the initial functions using functional composition alone, and then find a primitive recursive function that fails this property. Thus, we begin with the following definition:

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

1.

(initial functions): $z,s,p_{m}^{k}\in\mathcal{PR}_{0}$ for all positive integers $m, k$ with $m\leq k$ .
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.

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

$\mathcal{X}_{n}\subseteq\mathcal{X}_{n+1}$ ,
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
Canonical name	ImportanceOfPrimitiveRecursion
Date of creation	2013-03-22 19:05:21
Last modified on	2013-03-22 19:05:21
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	12
Author	CWoo (3771)
Entry type	Feature
Classification	msc 03D20

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