Skip to main content
incorporated changes from comments
Source Link
user44143
user44143

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

Is there a similar result for the family of elementary computableunary 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?

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?

Source Link

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?