Skip to main content
1 of 3

An analogue to Robinson's theorem for Kalmar-elementary functions

Julia Robinson proved that the family of all total unary computable functions is the smallest class containing $S$, $\mathrm{Exc}$, and closed under composition, addition and inversion of surjective functions. (Here $\mathrm{Exc}(x)=x-\lfloor\sqrt x \rfloor^2$, and the inversion of a surjection $f \colon \mathbb{N} \to \mathbb{N}$ is $f^{-1}(m) ={}$the least $n$ such that $f(n)=m$.)

Raphael Robinson proved a similar result for the family of unary primitive recursive functions: it is the smallest class containing $S$, $\mathrm{Exc}$, and closed under composition, addition and iterations.

(You can find a proof of these results in Monk's book Mathematical logic.)

Is there a similar result for the family of elementary computable functions?