characterization of primitive recursive functions of one variable

It is possible to characterize primitive recursive functions of one variable in terms of operations involving only functions of a single variable. To describe how this goes, it is useful to first define some 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}$, define the function $R\mathit{}\mathrm{(}f\mathrm{)}\mathrm{:}\mathrm{N}\mathrm{\to }\mathrm{N}$ by the following 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 is the smallest class $X$ of functions which contains the functions $E$ and $K$ defined above and is closed under the following three 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$.

Title	characterization of primitive recursive functions of one variable
Canonical name	CharacterizationOfPrimitiveRecursiveFunctionsOfOneVariable
Date of creation	2013-03-22 16:45:25
Last modified on	2013-03-22 16:45:25
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	9
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 03D20