# primitive recursive functions without primitive recursion

To begin with, we list the initial functions:

1. 1.

(zero function) $z(x)=0$,

2. 2.

(successor function) $s(x)=x+1$,

3. 3.

(projection functions) $p_{i}^{n}(x_{1},\ldots,x_{n})=x_{i}$ for $i=1,\ldots,n$; in particular, we have the identity function  $\operatorname{id}(x)=x$, which is just $p_{1}^{1}$.

With the help of functional composition, more functions can be derived:

1. 1.

(addition  by a fixed number $n$) $s_{n}(x)=x+n$, which can be obtained by repeated application of the successor function $s$:

 $s_{n}:=\underbrace{s\circ s\circ\cdots\circ s}_{n\mbox{ times}},$
2. 2.

(constant functions  ) $\operatorname{const}_{1}(x)=1$, which is just $s(z(x))$; more generally, $\operatorname{const}_{n}(x)=n$ is $s_{n}(z(x))$, where $s_{n}$ is defined previously.

Next, we list some properties derivable  using functional composition which are preserved by primitive recursiveness.

1. 1.

(permutation  of variables) if $f(x_{1},\ldots,x_{n})$ is primitive recursive, then so is any function $g$ obtained from $f$ by permuting the variables $x_{i}$:

 $g(x_{1},\ldots,x_{n})=f(x_{\sigma(1)},\ldots,x_{\sigma(n)}),$

where $\sigma$ is a permutation on $\{1,\ldots,n\}$;

2. 2.

(removing a variable) if $f(x_{1},\ldots,x_{n},x_{n+1})$ is primitive recursive, then so is $g$ defined by

 $g(x_{1},\ldots,x_{n}):=f(x_{1},\ldots,x_{n},x_{n});$
3. 3.

(adding a variable) if $f(x_{1},\ldots,x_{n})$ is primitive recursive, then so is $g$ defined by

 $g(x_{1},\ldots,x_{n},x_{n+1}):=f(x_{1},\ldots,x_{n}).$
###### Proof.

All of the above can be proved by appropriately substituting the suitable projection functions:

1. 1.

For each $i=1,\ldots,n$, let $h_{i}=p_{\sigma(i)}^{n}$. Then each $h_{i}$ is primitive recursive, and therefore $g=f(h_{1},\ldots,h_{n})$ is primitive recursive also.

2. 2.

For each $i=1,\ldots,n$, let $h_{i}=p_{i}^{n}$, and $h_{n+1}=p_{n}^{n}$. Then each $h_{i}$ is primitive, and therefore $g=f(h_{1},\ldots,h_{n+1})$ is primitive recursive also.

3. 3.

For each $i=1,\ldots,n$, let $h_{i}=p_{i}^{n+1}$. Then each $h_{i}$ is primitive recursive, and therefore $g=f(h_{1},\ldots,h_{n})$ is primitive recursive also.

As a corollary, we see that primitive recursiveness is preserved under generalized composition, in the following sense:

###### Corollary 1.

If $g_{i}:\mathbb{N}^{k_{i}}\to\mathbb{N}$, where $i=1,\ldots,n$, and $h:\mathbb{N}^{n}\to\mathbb{N}$ are primitive recursive, then the function $f$, given by

 $f(x_{1},\ldots,x_{m})=h(g_{1}(x_{t_{1}(1)},\ldots,x_{t_{1}(k_{1})}),\ldots,g_{% n}(x_{t_{n}(1)},\ldots,x_{t_{n}(k_{n})})),$

where each $t_{i}$ is a function on $\{1,\ldots,k_{i}\}$, and $m\geq\max\{k_{1},\ldots,k_{n}\}$, is also primitive recursive.

###### Proof.

Define $h_{i}(x_{1},\ldots,x_{m}):=g_{i}(x_{t_{i}(1)},\ldots,x_{t_{i}(k_{i})})$. Then by repeated applications of the properties listed above, we see that $h_{i}$ is primitive recursive. Hence $f=h(h_{1},\ldots,h_{n})$ is also primitive recursive. ∎

Title primitive recursive functions without primitive recursion PrimitiveRecursiveFunctionsWithoutPrimitiveRecursion 2013-03-22 19:08:09 2013-03-22 19:08:09 CWoo (3771) CWoo (3771) 7 CWoo (3771) Example msc 03D20