# Grzegorczyk-hierarchy, growth-rate and functions with finite image

Grzegorczyk-hierarchy divides primitive recursive functions in distinct classes with respect to their growth-rate. It seems that the higher we go the hierarchy, the more tools we have to define functions with finite image that can't be defined in the lower levels of the hierarchy. I have been trying to define functions with finite image that exist only in "high enough" in the hierarchy, but so far I haven't succeeded.

How would one define a finite image function for every $i$ that is in $\mathcal{E}_i$ but not in the lower levels?

-

I'm not an expert on subrecursive hierarchies, so the following idea comes with no warranty, but it looks reasonable to me. Once $i$ is not absurdly small ($i\geq 3$ should suffice), the class $\mathcal E_{i+1}$ should contain a binary function $u$ that is universal for $\mathcal E_{i}$ functions in the sense that, for every unary $\mathcal E_{i}$ function $f$, there is an index $e$ such that $f(n)=u(e,n)$ for all $n$. If that's right, then you can diagonalize, defining $g(n)=0$ when $u(n,n)>0$ and $g(n)=1$ when $u(n,n)=0$, to get a 2-valued function $g$ that is in $\mathcal E_{i+1}$ but not in $\mathcal E_{i}$.