characterization of primitive recursive functions of one variable

It is possible to characterize primitive recursive functions of onevariable in terms of operations involving only functions of a singlevariable. To describe how this goes, it is useful to first definesome notation.

Definition 1.

Define the constant function $K\mathrm{:}\mathrm{N}\mathrm{\to }\mathrm{N}$ by $K\mathit{}\mathrm{(}n\mathrm{)}\mathrm{=}\mathrm{1}$ for all $n$.

Definition 2.

Define the identity function $I\mathrm{:}\mathrm{N}\mathrm{\to }\mathrm{N}$ by $I\mathit{}\mathrm{(}n\mathrm{)}\mathrm{=}n$ for all $n$.

Definition 3.

Define the excess over square function$E\mathrm{:}\mathrm{N}\mathrm{\to }\mathrm{N}$ by$E\mathit{}\mathrm{(}n\mathrm{)}\mathrm{=}n\mathrm{-}{m}^{\mathrm{2}}$, where $m$ is the largest integer such that$m^{\mathrm{2}}\mathrm{\le }n$.

Definition 4.

Given a function $f\mathrm{:}\mathrm{N}\mathrm{\to }\mathrm{N}$, definethe function $R\mathit{}\mathrm{(}f\mathrm{)}\mathrm{:}\mathrm{N}\mathrm{\to }\mathrm{N}$ by thefollowing conditions:

• $R(f)(0)=0$

• $R(f)(n+1)=f(R(f)(n))$ for all integers $n\ge 0$.

Theorem 1.

The class of primitive recursive functions of a single variable isthe smallest class $X$ of functions which contains the functions$E$ and $K$ defined above and is closed under the followingthree operations:

1. If $f\in X$ and $g\in X$, then $f\circ g\in X$.

2. If $f\in X$, then $f+I\in X$.

3. If $f\in X$, then $R(f)\in X$.