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{P}{\mathcal{R}}_{0}$ be the smallest subset of the set $\mathcal{P}\mathcal{R}$ of primitive recursive functions such that

1.
(initial functions): $z,s,{p}_{m}^{k}\in \mathcal{P}{\mathcal{R}}_{0}$ for all positive integers $m,k$ with $m\le k$.

2.
(closure under functional composition): if $f,{g}_{1},\mathrm{\dots},{g}_{m}\in \mathcal{P}{\mathcal{R}}_{0}$ with $f$ $m$ary and ${g}_{i}$ $n$ary, then the $n$ary function $h:=f({g}_{1},\mathrm{\dots},{g}_{m})\in \mathcal{P}{\mathcal{R}}_{0}$ as well.
From the definition above, we observe that any function $f({x}_{1},\mathrm{\dots},{x}_{n})$ obtained without the use of the successor function $s$ must be bounded by $\mathrm{max}\{{x}_{1},\mathrm{\dots},{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 $\mathrm{max}\{{x}_{1},\mathrm{\dots},{x}_{n}\}$ plus some fixed integer. This is the property we seek, and we prove it formally:
Proposition 1.
For any $f\mathrm{\in}\mathrm{P}\mathit{}{\mathrm{R}}_{\mathrm{0}}$ with arity $n$, the following condition is satisfied:
(*) there is an integer $r\ge 0$ such that $f({x}_{1},\mathrm{\dots},{x}_{n})\le \mathrm{max}\{{x}_{1},\mathrm{\dots},{x}_{n}\}+r$.
Proof.
For each integer $n\ge 0$, let ${\mathcal{X}}_{n}$ be the subset of $\mathcal{P}{\mathcal{R}}_{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{P}{\mathcal{R}}_{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},\mathrm{\dots},{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}\le i$, and $h\in {\mathcal{X}}_{t}$, where $t=i\mathrm{max}\{{i}_{1},\mathrm{\dots},{i}_{m}\}$. Then, by assumption ${g}_{j}({x}_{1},\mathrm{\dots},{x}_{k})\le x+{i}_{j}+1\le x+\mathrm{\ell}+1$ for all $j\in \{1,\mathrm{\dots},m\}$, where $x=\mathrm{max}\{{x}_{1},\mathrm{\dots},{x}_{k}\}$ and $\mathrm{\ell}=\mathrm{max}\{{i}_{1},\mathrm{\dots},{i}_{m}\}$. As a result,
$f({x}_{1},\mathrm{\dots},{x}_{k})$ $=$ $h({g}_{1}({x}_{1},\mathrm{\dots},{x}_{k}),\mathrm{\dots},{g}_{m}({x}_{1},\mathrm{\dots},{x}_{k}))$ $\le $ $\mathrm{max}\{{g}_{j}({x}_{1},\mathrm{\dots},{x}_{k})\mid j=1,\mathrm{\dots},m\}+t+1$ $\le $ $(x+\mathrm{\ell}+1)+t+1=x+(i+1)+1.$ This proves the stronger assertion.
Now, if we pick any $f\in \mathcal{P}{\mathcal{R}}_{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{P}{\mathcal{R}}_{0}\subset \mathcal{P}\mathcal{R}$.
Proof.
We prove that $\mathrm{add}(x,y)=x+y$ does not have property (*) above. But if it does, then $\mathrm{add}(x,y)\le \mathrm{max}\{x,y\}+r$ for some nonnegative integer $r$. Then, for an arbitrary nonnegative integer $n$, $2n=\mathrm{add}(n,n)\le \mathrm{max}\{n,n\}+r=n+r$, so that $n\le 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{P}\mathcal{R}$ in the following manner: $\mathcal{P}{\mathcal{R}}_{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{P}{\mathcal{R}}_{n}\subset \mathcal{P}{\mathcal{R}}_{n+1}\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}\mathcal{P}\mathcal{R}=\bigcup _{i=0}^{\mathrm{\infty}}\mathcal{P}{\mathcal{R}}_{i}$$ 
For example, addition is in $\mathcal{P}{\mathcal{R}}_{1}\mathcal{P}{\mathcal{R}}_{0}$, as was shown earlier. Furthermore, it is not hard to show that multiplication is in $\mathcal{P}{\mathcal{R}}_{2}\mathcal{P}{\mathcal{R}}_{1}$, and exponentiation is in $\mathcal{P}{\mathcal{R}}_{3}\mathcal{P}{\mathcal{R}}_{2}$. In fact, the Ackermann function^{} can be utilized to show that each $\mathcal{P}{\mathcal{R}}_{n}\subset \mathcal{P}{\mathcal{R}}_{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{E}\mathcal{R}$ of elementary recursive functions, it can be shown that $\mathcal{E}\mathcal{R}=\mathcal{P}{\mathcal{R}}_{3}$.
Title  importance of primitive recursion 

Canonical name  ImportanceOfPrimitiveRecursion 
Date of creation  20130322 19:05:21 
Last modified on  20130322 19:05:21 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  12 
Author  CWoo (3771) 
Entry type  Feature 
Classification  msc 03D20 