It is well known that [recursively enumerable sets](http://en.wikipedia.org/wiki/Recursively_enumerable_set) 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](http://en.wikipedia.org/wiki/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. 



Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy
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$.) 


