A $2$-ary predicate $R$ in [Grzegroczyk-hierarchy](http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy) is binary-valued function $R\colon\mathbb{N}^2\to\{0,1\}$. We say $R$ encodes function $f:\mathbb{N}\to\mathbb{N}$ if $R(x,y)$ is true if and only if $f(x)=y$. 


Let us assume that $i>2$ and $j>i$. Is there a function $f\in\mathcal{E}\_j\setminus\mathcal{E}\_i$ and predicate $R\in\mathcal{E}\_i$ such that $R$ encodes $f$? Thus I want to know if it is possible to encode a function in higher level in the hierarchy with a predicate in lower level, or I would like to see a proof that this is not possible. I would guess this has been addressed in literature but I was not able to find a reference.



Predicates encoding functions in Grzegorczyk-hierarchy
The general principle is that the *faster* a function grows, the *easier* it is to compute its graph, because the extremely long output of the function is given to us as an input, which provides immense computational power.


For the specific question, it is well known that e.g. graphs of all kinds of variants of the Ackermann function $A(m,n)$ (and therefore all the unary functions $A\_m(n)=A(m,n)$, which are in $\mathcal E\_m\smallsetminus\mathcal E\_{m-1}$, give or take $1$) are definable by $\Delta\_0$-formulas, and therefore in $\mathcal E\_2$. For an early reference, [Proskurin](http://link.springer.com/article/10.1007%2FBF01629447) shows it is even in $\mathcal E^\*\_0$.


