# Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy

It is well known that recursively enumerable sets can be defined (among many other equivalent alternatives) as the range sets of primitive recusive functions (except for the trivial case of the empty set).

On the other hand, primitive recursive functions can be presented in an stratified way using Grzegorczyk-hierarchy.

I am wondering what it is known about whether recursively enumerable sets can be presented as the range sets of functions in some particular level of Grzegorczyk-hierarchy.

• In case you're interested, the last theorem in Grzegorczyk's paper Some classes of recursive functions, where the hierarchy is introduced, proves that $\mathcal{E}_0$ suffices, as is shown in the answer.
– user10891
Feb 19, 2013 at 12:35

It seems to me that every nonempty computably enumerable set will be the range of a primitive recursive function that is very low in the Grzegorczyk hierarchy, and it seems that even $\cal {E}^1$ suffices. The reason is that if $A$ is a nonempty c.e. set, then it is the domain of some computable function $\varphi_e$, with Turing machine program $e$. Let $k_0$ be the smallest element of $A$. Let $p$ be the primitive recursive function defined so that $p(n)=k$ if $n$ is a Gödel code of the entire computation sequence of program $e$ on input $k$, and this computation sequence successfully attains the halt state, and otherwise $p(n)=k_0$ if $n$ is not such a code. The graph of this function is $\Delta_0$-definable and so $p$ really is primitive recursive. Furthermore, $p$ is not at all a fast growing function, since $p(n)$ is much less than $\max\{n,k_0\}$, and so $p$ arises in very low levels of the Grzegorczyk hierarchy. Specifically, $p(n)$ is definable by recursions that do not need to consult numbers larger than $\max\{n,k_0\}$. So it seems that $p$ is in level $\cal{E}^1$, at the bottom of the hierarchy. Meanwhile, the range of $p$ is precisely $A$, as desired.
(Note that we may slow the growth of $p$ down further, as much as desired, by requiring $n$ to code much more information, before giving the comparatively tiny output $k$.)
• I should have said, "the graph of this function is $\Delta_0$-definable and it is bounded by a primitive recursive function, so $p$ really is primitive recursive." There are very fast-growing functions with $\Delta_0$-definable graphs, but which are not primitive recursive. Nov 14, 2012 at 16:32
For example, the function can be made uniform $\mathrm{AC}^0$, in other words, computable by a logarithmic-time alternating Turing machine with constantly many alternations (actually, 1 or 2 alternations should be enough, but I would have to check).
For another notion of simplicity, if $A$ is an r.e. set and $a_0$ is its least element, then $A$ is the range of a function $f\colon\mathbb N^k\to\mathbb N$ of the form $$f(\vec x)=\max\{p(\vec x),a_0\}$$ where $p$ is a polynomial with integer coefficients. (This follows from the MRDP theorem.)