elementary recursive function
Informally, elementary recursive functions are functions^{} that can be obtained from functions encountered in elementary schools: addition^{}, multiplication, subtraction^{}, and division, using basic operations^{} such as substitutions and finite summation and product^{}. Before stating the formal definition, the following notations are used:
$\mathcal{F}=\bigcup \{{F}_{k}\mid k\in \mathbb{N}\}$, where for each $k\in \mathbb{N}\text{,}{F}_{k}=\{f\mid f:{\mathbb{N}}^{k}\to \mathbb{N}\}$.
Definition. The set of elementary recursive functions, or elementary functions for short, is the smallest subset $\mathcal{E}\mathcal{R}$ of $\mathcal{F}$ where:

1.
(addition) $\mathrm{add}\in \mathcal{E}\mathcal{R}\cap {F}_{2}$, given by $\mathrm{add}(m,n):=m+n$;

2.
(multiplication) $\mathrm{mult}\in \mathcal{E}\mathcal{R}\cap {F}_{2}$, given by $\mathrm{mult}(m,n):=mn$;

3.
(difference^{}) $\mathrm{diff}\in \mathcal{E}\mathcal{R}\cap {F}_{2}$, given by $\mathrm{diff}(m,n):=mn$;

4.
(quotient) $\mathrm{quo}\in \mathcal{E}\mathcal{R}\cap {F}_{2}$, given by $\mathrm{quo}(m,n):=[m/n]$, which is the largest nonnegative integer $z$ such that $nz\le m$ (by convention, $\mathrm{quo}(0,0):=1$);

5.
(projection) ${p}_{m}^{k}\in \mathcal{E}\mathcal{R}\cap {F}_{k}$, where $m\le k$, given by ${p}_{m}^{k}({n}_{1},\mathrm{\dots},{n}_{k}):={n}_{m}$;

6.
$\mathcal{E}\mathcal{R}$ is closed under composition: If $\{{g}_{1},\mathrm{\dots},{g}_{m}\}\subseteq \mathcal{E}\mathcal{R}\cap {F}_{k}$ and $h\in \mathcal{E}\mathcal{R}\cap {F}_{m}$, then $f\in \mathcal{E}\mathcal{R}\cap {F}_{k}$, where
$$f({n}_{1},\mathrm{\dots},{n}_{k})=h({g}_{1}({n}_{1},\mathrm{\dots},{n}_{k}),\mathrm{\dots},{g}_{m}({n}_{1},\mathrm{\dots},{n}_{k}));$$ 
7.
$\mathcal{E}\mathcal{R}$ is closed under bounded sum: if $f\in \mathcal{E}\mathcal{R}\cap {F}_{k}$, then ${f}_{s}\in \mathcal{E}\mathcal{R}\cap {F}_{k}$, where
$${f}_{s}(\bm{x},y):=\sum _{i=0}^{y}f(\bm{x},i);$$ 
8.
$\mathcal{E}\mathcal{R}$ is closed under bounded product: if $f\in \mathcal{E}\mathcal{R}\cap {F}_{k}$, then ${f}_{p}\in \mathcal{E}\mathcal{R}\cap {F}_{k}$, where
$${f}_{p}(\bm{x},y):=\prod _{i=0}^{y}f(\bm{x},i).$$
Examples.

•
The initial functions in the definition of primitive recursive functions^{} are elementary:

(a)
The zero function $z(x)$ is $\mathrm{diff}(x,x)$.

(b)
The constant function^{} ${\mathrm{const}}_{1}(x):=1$ is $\mathrm{quo}(x,x)$.

(c)
The successor function $s(x)$ can be obtained by substituting (by composition) the constant function ${\mathrm{const}}_{1}$ and the projection function ${p}_{1}^{1}$, into the addition function $\mathrm{add}({p}_{1}^{1}(x),{\mathrm{const}}_{1}(x))$.

(a)

•
Multiplication $\mathrm{mult}$ in 2 above may be removed from the definition, since
$$\mathrm{mult}(x,y)=\mathrm{diff}(f(x,y),{p}_{1}^{2}(x,y)),\text{where}f(x,y):=\sum _{i=0}^{y}{p}_{1}^{2}(x,i)$$ 
•
Many other basic functions, such as the restricted subtraction, exponential function^{}, the $i$th prime function, are all elementary. One may replace the difference function in 3 above by the restricted subtraction without changing $\mathcal{E}\mathcal{R}$.
Remarks

•
Consider the set $\mathcal{P}\mathcal{R}$ of primitive recursive functions. The functions in the first five groups above are all in $\mathcal{P}\mathcal{R}$. In addition, $\mathcal{P}\mathcal{R}$ is closed under the operations in 6, 7, and 8 above, we see that $\mathcal{E}\mathcal{R}\subseteq \mathcal{P}\mathcal{R}$, since $\mathcal{E}\mathcal{R}$, as defined, is the smallest such set.

•
Furthermore, $\mathcal{E}\mathcal{R}\ne \mathcal{P}\mathcal{R}$. For example, the superexponential function, given by $f(x,0)=m$, and $f(x,n+1)=\mathrm{exp}(m,f(x,n))$, where $m>1$, can be shown to be nonelementary.

•
In addition, it can be shown that $\mathcal{E}\mathcal{R}$ is the set of primitive recursive functions that can be obtained from the zero function, the successor function, and the projection functions via composition, and no more than three applications of primitive recursion.

•
By taking the closure of $\mathcal{E}\mathcal{R}$ with respect to unbounded minimization, one obtains $\mathcal{R}$, the set of all recursive functions (partial or total). In fact, by replacing bounded sum and bounded product with unbounded minimization, and the difference function with restricted subtraction, one obtains $\mathcal{R}$.
Title  elementary recursive function 

Canonical name  ElementaryRecursiveFunction 
Date of creation  20130322 19:06:48 
Last modified on  20130322 19:06:48 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  9 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D20 
Synonym  elementary 
Related topic  BoundedRecursion 
Defines  elementary recursive 