Skip to main content
2 of 3
incorporated changes from comments
user avatar
user avatar

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

Julia Robinson proved that the family of all unary computable total 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. These results are proved in Monk's book Mathematical Logic.

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