Primitive Recursive

Loop Types

In programming terminology a for loop requires that the number of steps in the loop is bounded, prior to entering the loop, in terms of functions and parameters previously computed.

An until/while loop has no such prior bound and is allowed to continue looping until some condition is met, and so it may require an unbounded search and also may never halt.

Primitive Recursive (definition 1)

A function $f:{\mathbb{N}}^k\to \mathbb{N}$ is primitive recursive if it can be computed using only “for” loops. The number of loops can depend on the function.

A relation/set $R\subseteq {\mathbb{N}}^k$ is primitive recursive if its characteristic function is primitive recursive. The characteristic function ${\chi }_R$ is define by

1 & (a_1, \dots, a_k) \in R, \ 0 & (a_1, \dots, a_k) \notin R. \end{cases}$$ We think of the statement $R(a_1,\dots ,a_k)=1$ as saying $R$ is true of $(a_1,\dots ,a_k)$.

Initial Functions

The following functions $f:{\mathbb{N}}^n\to \mathbb{N}$ ($n\ge 1$) are initial functions:

• the zero functions, $O_n(x_1,\dots ,x_n)=0$ for $n\ge 1$,
• the successor function $S(x)=x+1$,
• the projection functions $p_i^n(x_1,\dots ,x_n)=x_i$ for $1\le i\le n$.
  The function $f:{\mathbb{N}}^n\to \mathbb{N}$ ($n\ge 1$) is obtained by composition from $h,g_1,\dots ,g_p$, $f(x_1,\dots ,x_n)=h(g_1(x_1,\dots ,x_n),\dots ,g_p(x_1,\dots ,x_n)).$ The function $f:{\mathbb{N}}^{n+1}\to \mathbb{N}$ ($n\ge 0$) is obtained by primitive recursion from $g$ and $h$ if $f(x_1,\dots ,x_n,0)=g(x_1,\dots ,x_n),$ $f(x_1,\dots ,x_n,y)=h(x_1,\dots ,x_n,y,f(x_1,\dots ,x_n,y-1))(\text{for all }y\ge 1).$ That is, $f(\bar{x},0)=g(\bar{x}),f(\bar{x},y)=h(\bar{x},y,f(\bar{x},y-1))\text{ if }y\ge 1.$

Primitive Recursive (definition 2)

A function $f:{\mathbb{N}}^n\to \mathbb{N}$ is primitive recursive if it is an initial function, or is obtained from primitive recursive functions by composition or by primitive recursion.

Equivalently, the function $f$ is primitive recursive if there is a sequence of functions $f_1,f_2,\cdots ,f_k$such that $f$ is $f_k$ and such that each $f_j$ is an initial function or is obtained from previous $f_i$ by composition or primitive recursion.

A set $R\subset {\mathbb{N}}^k$ is primitive recursive iff its characteristic function ${\chi }_R$ is primitive recursive.

Remark

the set of primitive recursive functions is a proper subset of computable functions. On the other hand, we can give an algorithm for listing all primitive recursive functions (e.g. first list all appropriate definitional sequences of length at most 100 in which all functions are at most 10-ary, then those of length 200 in which all functions are at most 20-ary, etc.). From this we can effectively list all unary primitive recursive functions. Let $\phi (n)={\phi }_n(n)+1$ where ${\phi }_n$ is the $n$-th unary primitive recursive function. Clearly $\phi$ is computable but not primitive recursive. Thus the primitive recursive functions are a proper subset of the set of all computable functions. (Although we have yet to give a precise definition of this latter set.)

Theorem

The above two definitions of primitive recursive are equivalent.

Non-negative subtraction

Non-negative subtraction is defined by $x\dot{-}y=\max \{0,x-y\}.$

Theorem

(1) The functions $x+y$, $x\cdot y$, $x^y$, $x!$, $x\dot{-}y$, and the constant functions, are primitive recursive. The relations $<,\le ,>,\ge$ and $=$ are primitive recursive. (2) If $R$ and $S$ are primitive recursive subsets of ${\mathbb{N}}^k$, then so are ${\mathbb{N}}^k\setminus R$, $R\cap S$, $R\cup S$. (3) If $R(x_1,\dots ,x_n,y)$ is primitive recursive, then so are $S(x_1,\dots ,x_n,x_{n+1}):=\forall y\le x_{n+1}R(x_1,\dots ,x_n,y),$ $T(x_1,\dots ,x_n,x_{n+1}):=\exists y\le x_{n+1}R(x_1,\dots ,x_n,y),\text{and}$ $W(x_1,\dots ,x_n,x_{n+1}):=\mu y\le x_{n+1}R(x_1,\dots ,x_n,y),$ where $\mu y\le x_{n+1}R(x_1,\dots ,x_n,y)$ is the least $y<x_{n+1}$ such that $R(x_1,\dots ,x_n,y)$ if such a $y$ exists, and is $x_{n+1}$ otherwise. (4) Suppose $g_1,\dots ,g_k:{\mathbb{N}}^n\to \mathbb{N}$ are primitive recursive functions and $Q_1,\dots ,Q_k$ are primitive recursive subsets of ${\mathbb{N}}^n$. Suppose $R_1,\dots ,R_k$ are primitive recursive sets forming a partition of ${\mathbb{N}}^n$. Let $f:{\mathbb{N}}^n\to \mathbb{N}$ and $P\subseteq {\mathbb{N}}^n$, be defined by $f(\bar{x})=\{\begin{array}{ll}{g}_1(\bar{x})& \bar{x}\in R_1,\\ ⋮& \\ g_k(\bar{x})& \bar{x}\in R_k,\end{array}\text{and}$
$\bar{x}\in P⟺\{\begin{array}{ll}\bar{x}\in Q_1& \bar{x}\in R_1,\\ ⋮& \\ \bar{x}\in Q_k& \bar{x}\in R_k.\end{array}$ Then $f$ and $P$ are primitive recursive.

Defining in $\mathfrak{N}$ and Representing in P.A. a P.R. function

If $f$ is primitive recursive, then $f$ is both definable (in $\mathfrak{N}$ in the language $\mathcal{L}$) and representable in $PA$, by a ${\Sigma }_1$-formula.

Representing a P.R. relation by a ${\Sigma }_1$-Formula

If $A\subseteq {\mathbb{N}}^k$ is primitive recursive, then $A$ is both definable (in $\mathfrak{N}$ in the language $\mathcal{L}$) and representable in $PA$, by a ${\Sigma }_1$-formula.

Proof If $A$ is p.r. then so is its characteristic function ${\chi }_A$. If ${\chi }_A$ is represented by the ${\Sigma }_1$-formula $\phi (x_1,\dots ,x_n,y)$ then $A$ is represented by $\phi (x_1,\dots ,x_n,1)$.