A total function $f: \mathbb{N} \to \mathbb{N}$ is monotone iff $f(x) < f(y)$ whenever $x < y$. Show that if $A$ is the range of a monotone recursive function then $A$ is recursive.

Hint: first show that the relations defined by $y = f(x)$ and $y < f(x)$ are recursive.

The hint part is easy. The graph relation of a recursive total function is a recursive relation. Since $f$ is a recursive total function, then the graph relation $y = f(x)$ is a recursive relation.

Using composition on the primitive recursive functions of modified (non-negative) difference and the signum function, we can see that $y < f(x)$ is recursive.

\begin{align*} \mathbf{1}_{y < f(x)}(x,y) &= \text{sg}(f(x) - y)) \\ \end{align*}

From there, if we can show a recursive construction of the following function then we will complete the problem:

\begin{align*} \mathbf{1}_{A}(y) &= \exists x (y = f(x)) \\ \end{align*}

This construction uses unbounded existential quantification, which is not necessarily recursive, so that won't solve the problem.

From here, I'm stuck on what to try.


1 Answer 1


So the trick is to use the fact that it's monotone. For all monotone functions $f$ of the natural numbers you have that $n\leq f$. So to check whether $y$ is in the image all you need to do is check all $x\leq y$ since for any $x>y$ you have $f(x)>y$. This gives the bound you need.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.