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},\mathrm{\dots},{x}_{n})={x}_{i}$ for $i=1,\mathrm{\dots},n$; in particular, we have the identity function^{} $\mathrm{id}(x)=x$, which is just ${p}_{1}^{1}$.
With the help of functional composition, more functions can be derived:

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}:=\underset{n\text{times}}{\underset{\u23df}{s\circ s\circ \mathrm{\cdots}\circ s}},$$ 
2.
(constant functions^{}) ${\mathrm{const}}_{1}(x)=1$, which is just $s(z(x))$; more generally, ${\mathrm{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},\mathrm{\dots},{x}_{n})$ is primitive recursive, then so is any function $g$ obtained from $f$ by permuting the variables ${x}_{i}$:
$$g({x}_{1},\mathrm{\dots},{x}_{n})=f({x}_{\sigma (1)},\mathrm{\dots},{x}_{\sigma (n)}),$$ where $\sigma $ is a permutation on $\{1,\mathrm{\dots},n\}$;

2.
(removing a variable) if $f({x}_{1},\mathrm{\dots},{x}_{n},{x}_{n+1})$ is primitive recursive, then so is $g$ defined by
$$g({x}_{1},\mathrm{\dots},{x}_{n}):=f({x}_{1},\mathrm{\dots},{x}_{n},{x}_{n});$$ 
3.
(adding a variable) if $f({x}_{1},\mathrm{\dots},{x}_{n})$ is primitive recursive, then so is $g$ defined by
$$g({x}_{1},\mathrm{\dots},{x}_{n},{x}_{n+1}):=f({x}_{1},\mathrm{\dots},{x}_{n}).$$
Proof.
All of the above can be proved by appropriately substituting the suitable projection functions:

1.
For each $i=1,\mathrm{\dots},n$, let ${h}_{i}={p}_{\sigma (i)}^{n}$. Then each ${h}_{i}$ is primitive recursive, and therefore $g=f({h}_{1},\mathrm{\dots},{h}_{n})$ is primitive recursive also.

2.
For each $i=1,\mathrm{\dots},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},\mathrm{\dots},{h}_{n+1})$ is primitive recursive also.

3.
For each $i=1,\mathrm{\dots},n$, let ${h}_{i}={p}_{i}^{n+1}$. Then each ${h}_{i}$ is primitive recursive, and therefore $g=f({h}_{1},\mathrm{\dots},{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}\mathrm{:}{\mathrm{N}}^{{k}_{i}}\mathrm{\to}\mathrm{N}$, where $i\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}n$, and $h\mathrm{:}{\mathrm{N}}^{n}\mathrm{\to}\mathrm{N}$ are primitive recursive, then the function $f$, given by
$$f({x}_{1},\mathrm{\dots},{x}_{m})=h({g}_{1}({x}_{{t}_{1}(1)},\mathrm{\dots},{x}_{{t}_{1}({k}_{1})}),\mathrm{\dots},{g}_{n}({x}_{{t}_{n}(1)},\mathrm{\dots},{x}_{{t}_{n}({k}_{n})})),$$ 
where each ${t}_{i}$ is a function on $\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}{k}_{i}\mathrm{\}}$, and $m\mathrm{\ge}\mathrm{max}\mathit{}\mathrm{\{}{k}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{k}_{n}\mathrm{\}}$, is also primitive recursive.
Proof.
Define ${h}_{i}({x}_{1},\mathrm{\dots},{x}_{m}):={g}_{i}({x}_{{t}_{i}(1)},\mathrm{\dots},{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},\mathrm{\dots},{h}_{n})$ is also primitive recursive. ∎
Title  primitive recursive functions without primitive recursion 

Canonical name  PrimitiveRecursiveFunctionsWithoutPrimitiveRecursion 
Date of creation  20130322 19:08:09 
Last modified on  20130322 19:08:09 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Example 
Classification  msc 03D20 