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

$$𝒮:=\{f:{\mathbb{N}}^m\to \mathbb{N}\mid \text{any }m\ge 1\},𝒱:=\{f:{\mathbb{N}}^m\to {\mathbb{N}}^n\mid \text{any }m,n\ge 1\}.$$

In addition, let

$$𝒱(m,n):=\{f\in 𝒱\mid f:{\mathbb{N}}^m\to {\mathbb{N}}^n\}.$$

Finally, denote $𝒫ℛ$ the set of primitive recursive functions in the traditional sense (as a subset of $𝒮$), and $𝒫{ℛ}^{\prime }$ the set of primitive recursive vector-valued functions (a subset of $𝒱$). It is clear that $𝒫ℛ=𝒫{ℛ}^{\prime }\cap 𝒮$.

Let $𝒟$ be the smallest subset of $𝒱$ such that

1. $𝒟$ 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. $𝒟$ is closed under functional composition in $𝒱$,

3. $𝒟$ is closed under extension of coordinates: that is, if $f_1,\mathrm{\dots },f_n\in 𝒱(m,1)$ are in $𝒟$, so is $f:=(f_1,\mathrm{\dots },f_n)\in 𝒱(m,n)$, given by $f(𝒙)=(f_1(𝒙),\mathrm{\dots },f_n(𝒙))$,

4. $𝒟$ is closed under iterated composition: if $f\in 𝒱(m,m)$ is in $𝒟$, and so is $g\in 𝒱(m+1,n)$, given by $g(𝒙,n)=f^n(𝒙)$ (where $f^0$ is the identity function).

We now state the characterization.

Proposition 1.

$𝒫{ℛ}^{\prime }=𝒟$.

Proof.

First, observe that condition 1 is satisfied by both $𝒫{ℛ}^{\prime }$ and $𝒟$. To see that $𝒟\subseteq 𝒫{ℛ}^{\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 $𝒫{ℛ}^{\prime }\subseteq 𝒟$, we need to verify the two closure properties:

1. functional composition (in $𝒮$): suppose $g_1,\mathrm{\dots },g_m\in 𝒱(k,1)$ and $h\in 𝒱(m,1)$ are in $𝒟$, we want to show that $f:=h(g_1,\mathrm{\dots },g_m)\in 𝒱(k,1)$ is in $𝒟$ too. First, form $g=(g_1,\mathrm{\dots },g_m)$. Then $g\in 𝒟$ by extension of coordinates. Then $f=h\circ g\in 𝒟$ by functional composition (in $𝒱$).

2. primitive recursion: suppose $g\in 𝒱(k,1)$ and $h\in 𝒱(k+2,1)$ are both in $𝒟$, we want to show that $f\in 𝒱(k+1,1)$ given by $f(𝒙,0)=g(𝒙)$ and $f(𝒙,n+1)=h(𝒙,n,f(𝒙,n))$ is in $𝒟$ too. First, define a function $H\in 𝒱(k+2,k+2)$ by

   $$H(𝒙,y,z):=(𝒙,s(y),h(𝒙,y,z)).$$

   Then $H$ is formed by extension of coordinates via the projection functions $p_i^{k+2}$ (with $i=1,\mathrm{\dots },k$) producing the first $k$ coordinates (the coordinates of $𝒙$), 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 𝒱(k+3,k+2)$ given by $F(𝒙,y,z,m)=H^m(𝒙,y,z)$ is in $D$ by iterated composition. We now verify by induction on $n$ that

   $$F(𝒙,0,g(𝒙),n)=(𝒙,n,f(𝒙,n)).$$

   • $F(𝒙,0,g(𝒙),0)=(𝒙,0,g(𝒙)$, and its third coordinate is $f(𝒙,0)$, as desired.

   • Suppose now that $F(𝒙,0,g(𝒙),n)=(𝒙,n,f(𝒙,n))$. Then

     $F(𝒙,0,g(𝒙),n+1)$ $=$ $H(𝒙,n,f(𝒙,n))$

     $=$ $(𝒙,s(n),h(𝒙,n,f(𝒙,n)))$

     $=$ $(𝒙,n+1,f(𝒙,n+1)).$

   As a result, $f(𝒙,n)=p_{k+2}^{k+2}\circ F(𝒙,0,g(𝒙),n)$ is in $𝒟$ also.

Therefore, $𝒫{ℛ}^{\prime }\subseteq 𝒟$, 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 URM-computable function is recursive, and that the Ackermann function is not primitive recursive.

Title	alternative characterization of primitive recursiveness
Canonical name	AlternativeCharacterizationOfPrimitiveRecursiveness
Date of creation	2013-03-22 19:06:44
Last modified on	2013-03-22 19:06:44
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	5
Author	CWoo (3771)
Entry type	Result
Classification	msc 03D20