4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The question is too vague. What is a “similar result”? In particular, elementary functions are defined as the smallest class that contains some basic functions and is closed under composition, bounded summation, and bounded products. Why is that not enough for you? $\endgroup$
    – Emil Jeřábek
    Commented May 28, 2020 at 12:15
  • 1
    $\begingroup$ I am not familiar with the proof of the results that you mention. However, giving this two results, I think that I have a natural conjecture of what an analogue for elementary functions could be. Namely my conjecture would be that the class of all unary elementary functions is the least class containing, $S,\mathrm{Exc},\mathsf{exp}$ and closed under compositions, additions, and bounded inversions. Here $\mathsf{exp}(x)=2^x$ and $g$-bounded inversion of $f$ is $x\longmapsto \min(\{g(x)\}\cup\{y\mid f(y)=x\})$. $\endgroup$
    – Fedor Pakhomov
    Commented May 28, 2020 at 17:10
  • $\begingroup$ Let me explain what I mean by "similar result". The theorems I mentioned provide a definition of the collections of unary computable/primitive recursive functions. I was wondering if anyone is aware of a similar characterization for the unary elementary functions. The suggested conjecture is indeed natural. $\endgroup$
    – Alessandro Andretta
    Commented May 30, 2020 at 8:34

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .