bounded recursion

In this entry, the following notations are used:

$ℱ=\bigcup \{F_k\mid k\in \mathbb{N}\}$, where for each $k\in \mathbb{N}$, and $F_k=\{f\mid f:{\mathbb{N}}^k\to \mathbb{N}\}$.

Definition. A function $f\in F_{m+1}$ is said to be defined by bounded recursion via functions $g\in F_m$, $h\in F_{m+2}$, and $k\in F_{m+1}$ if, for any $𝒙\in {\mathbb{N}}^m$ and $y\in \mathbb{N}$,

1. $f$ is defined by primitive recursion via $g$ and $h$:

   • $f(𝒙,0)=g(𝒙)$,

   • $f(𝒙,y+1)=h(𝒙,y,f(𝒙,y))$;

2. $f$ is bounded from above by $k$:

   • $f(𝒙,y)\le k(𝒙,y)$.

Clearly, a function that is defined by bounded recursion is defined by primitive recursion. Conversely, a function is defined by primitive recursion, it is also defined by bounded recursion, since it is bounded by itself. However, the two concepts are not exactly the same. To make this precise, we first define what it means for a set of number-theoretic functions be closed under bounded recursion:

Definition. A set $ℬ\subseteq ℱ$ is said to be closed under bounded recursion if, for any $f$ defined by bounded recursion via $g,h,k\in ℬ$, then $f\in ℬ$.

It is clear that $ℱ$ is closed under both primitive recursion and bounded recursion, and so are $𝒫ℛ$, the set of all primitive recursive functions, as well as $ℛ\cap ℱ$, the set of all total recursive functions. However,

Proposition 1.

The set $\mathrm{E}\mathit{}\mathrm{R}$ of all elementary recursive functions is closed under bounded recursion, but not primitive recursion.

Since the exponential function, the $i$-th prime function, and the function ${(x)}_y$ (the exponent of $y$ in $x$) are elementary recursive, we have the following corollary:

Corollary 1.

If $f$ is defined by course-of-values recursion via an elementary recursive function $h$, and $f$ is bounded from above by an elementary recursive function $k$, then $f$ is elementary recursive.