Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
This looks very promising, I will go through the details before marking this an answer. Thank you. –  user10891 Mar 26 '13 at 13:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.