Image of a strictly increasing computable function is computable?

Question

I'm trying to show that if $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and strictly increasing, then $f(\mathbb{N})$ (the characteristic function of its image) is computable. My problem is that it seems too straightforward: if $f$ is strictly increasing, doesn't that just immediately provide a bound for existential quantification? So we have $g(y)=1\ iff\ \exists x\leq y: f(x)=y$ be computable as well. Am I missing something here? I ask because this proof seems like it'd work just fine with primitive recursive functions as well. I was expecting that I'd need to use unbounded minimization at some point.

Answer 1

I think I now understand your question and your point about primitive recursive functions: what you have here is construction that transforms a recursive function $f : \Bbb{N} \to \Bbb{N}$ that enumerates a subset of $\Bbb{N}$ in increasing order into a recursive function $g : \Bbb{N} \to \{0, 1\}$ that decides membership of the image of $f$. It so happens that your construction makes no use of minimisation, so if $f$ is primitive recursive, then so is $g$. That's just a nice feature of your proof. (Here my "recursive functions" are your "computable functions" or "$\mu$-recursive functions".)

The point of the exercise is that, in general, the image of a recursive function $f$ is recursively enumerable but not necessarily recursive. If $f$ happens to be strictly increasing, you get the stronger property that its image is recursive. The wikipedia page on r.e. sets may be of interest to you.