3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ This looks very promising, I will go through the details before marking this an answer. Thank you. $\endgroup$ – user10891 Mar 26 '13 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy