## You are here

Homeprimitive recursive functions without primitive recursion

## Primary tabs

# primitive recursive functions without primitive recursion

What sorts of functions can be built from the simplest primitive recursive functions (the initial functions) using functional composition alone? In this entry, we list some useful examples:

To begin with, we list the initial functions:

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

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

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. 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. (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. (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. (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. 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. 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. 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. ∎

## Mathematics Subject Classification

03D20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections