You are here
Homealternative characterization of primitive recursiveness
Primary tabs
alternative characterization of primitive recursiveness
One useful feature regarding the extended notion of primitive recursiveness described in the parent entry is that it can be used to characterize the original notion of primitive recursiveness. As in the parent entry, we use the notation
$\mathcal{S}:=\{f:\mathbb{N}^{m}\to\mathbb{N}\mid\mbox{any }m\geq 1\},\qquad% \mathcal{V}:=\{f:\mathbb{N}^{m}\to\mathbb{N}^{n}\mid\mbox{any }m,n\geq 1\}.$ 
In addition, let
$\mathcal{V}(m,n):=\{f\in\mathcal{V}\mid f:\mathbb{N}^{m}\to\mathbb{N}^{n}\}.$ 
Finally, denote $\mathcal{PR}$ the set of primitive recursive functions in the traditional sense (as a subset of $\mathcal{S}$), and $\mathcal{PR}^{{\prime}}$ the set of primitive recursive vectorvalued functions (a subset of $\mathcal{V}$). It is clear that $\mathcal{PR}=\mathcal{PR}^{{\prime}}\cap\mathcal{S}$.
Let $\mathcal{D}$ be the smallest subset of $\mathcal{V}$ such that
1. $\mathcal{D}$ contains the zero function $z$, the successor function $s$, and the projection functions $p_{m}^{k}$ (see the definition of primitive recursive functions for more detail),
2. $\mathcal{D}$ is closed under functional composition in $\mathcal{V}$,
3. $\mathcal{D}$ is closed under extension of coordinates: that is, if $f_{1},\ldots,f_{n}\in\mathcal{V}(m,1)$ are in $\mathcal{D}$, so is $f:=(f_{1},\ldots,f_{n})\in\mathcal{V}(m,n)$, given by $f(\boldsymbol{x})=(f_{1}(\boldsymbol{x}),\ldots,f_{n}(\boldsymbol{x}))$,
4. $\mathcal{D}$ is closed under iterated composition: if $f\in\mathcal{V}(m,m)$ is in $\mathcal{D}$, and so is $g\in\mathcal{V}(m+1,n)$, given by $g(\boldsymbol{x},n)=f^{n}(\boldsymbol{x})$ (where $f^{0}$ is the identity function).
We now state the characterization.
Proposition 1.
$\mathcal{PR}^{{\prime}}=\mathcal{D}$.
Proof.
First, observe that condition 1 is satisfied by both $\mathcal{PR}^{{\prime}}$ and $\mathcal{D}$. To see that $\mathcal{D}\subseteq\mathcal{PR}^{{\prime}}$, note that condition 3 is just the definition in the parent entry, and conditions 2 and 4 are discussed and proved, also in the parent entry. So we have one inclusion. To see the other inclusion $\mathcal{PR}^{{\prime}}\subseteq\mathcal{D}$, we need to verify the two closure properties:
1. functional composition (in $\mathcal{S}$): suppose $g_{1},\ldots,g_{m}\in\mathcal{V}(k,1)$ and $h\in\mathcal{V}(m,1)$ are in $\mathcal{D}$, we want to show that $f:=h(g_{1},\ldots,g_{m})\in\mathcal{V}(k,1)$ is in $\mathcal{D}$ too. First, form $g=(g_{1},\ldots,g_{m})$. Then $g\in\mathcal{D}$ by extension of coordinates. Then $f=h\circ g\in\mathcal{D}$ by functional composition (in $\mathcal{V}$).
2. primitive recursion: suppose $g\in\mathcal{V}(k,1)$ and $h\in\mathcal{V}(k+2,1)$ are both in $\mathcal{D}$, we want to show that $f\in\mathcal{V}(k+1,1)$ given by $f(\boldsymbol{x},0)=g(\boldsymbol{x})$ and $f(\boldsymbol{x},n+1)=h(\boldsymbol{x},n,f(\boldsymbol{x},n))$ is in $\mathcal{D}$ too. First, define a function $H\in\mathcal{V}(k+2,k+2)$ by
$H(\boldsymbol{x},y,z):=(\boldsymbol{x},s(y),h(\boldsymbol{x},y,z)).$ Then $H$ is formed by extension of coordinates via the projection functions $p_{i}^{{k+2}}$ (with $i=1,\ldots,k$) producing the first $k$ coordinates (the coordinates of $\boldsymbol{x}$), the function $s\circ p_{{k+1}}^{{k+2}}$ producing the $k+1$st coordinate $s(y)$, and $h$ producing the last coordinate. Since each of the coordinate functions is in $D$, so is $H$.
Next, the function $F\in\mathcal{V}(k+3,k+2)$ given by $F(\boldsymbol{x},y,z,m)=H^{m}(\boldsymbol{x},y,z)$ is in $D$ by iterated composition. We now verify by induction on $n$ that
$F(\boldsymbol{x},0,g(\boldsymbol{x}),n)=(\boldsymbol{x},n,f(\boldsymbol{x},n)).$ 
$F(\boldsymbol{x},0,g(\boldsymbol{x}),0)=(\boldsymbol{x},0,g(\boldsymbol{x})$, and its third coordinate is $f(\boldsymbol{x},0)$, as desired.

Suppose now that $F(\boldsymbol{x},0,g(\boldsymbol{x}),n)=(\boldsymbol{x},n,f(\boldsymbol{x},n))$. Then
$\displaystyle F(\boldsymbol{x},0,g(\boldsymbol{x}),n+1)$ $\displaystyle=$ $\displaystyle H(\boldsymbol{x},n,f(\boldsymbol{x},n))$ $\displaystyle=$ $\displaystyle(\boldsymbol{x},s(n),h(\boldsymbol{x},n,f(\boldsymbol{x},n)))$ $\displaystyle=$ $\displaystyle(\boldsymbol{x},n+1,f(\boldsymbol{x},n+1)).$
As a result, $f(\boldsymbol{x},n)=p_{{k+2}}^{{k+2}}\circ F(\boldsymbol{x},0,g(\boldsymbol{x}% ),n)$ is in $\mathcal{D}$ also.

Therefore, $\mathcal{PR}^{{\prime}}\subseteq\mathcal{D}$, and the proof is complete. ∎
Remark. According to the characterization above, one sees that primitive recursion is in a sense a special form of iterated composition. The above characterization is helpful in proving, among other things, that every URMcomputable function is recursive, and that the Ackermann function is not 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