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.

  • $\begingroup$ You're not missing anything there, that's a good definition of $g$. $\endgroup$ – BrianO Feb 14 '16 at 23:34
  • $\begingroup$ BrianO is right. But I am intrigued to know what you meant by your point about "primitive recursive functions" here. $\endgroup$ – Rob Arthan Feb 14 '16 at 23:53
  • $\begingroup$ @RobArthan A guess: if $f$ is p.r. then so is $g$. @ OP: which of course doesn't mean that $g$ will always be p.r. If f weren't strictly increasing, then yes, it would be an unbounded search for an $x$, which might not exist. $\endgroup$ – BrianO Feb 15 '16 at 0:04
  • $\begingroup$ @BrianO: In addition to trying to help with the question, I was actually sneakily looking for some data relating to this question of mine about terminology. The OP uses the terms "computable" and "primitive recursive". $\endgroup$ – Rob Arthan Feb 15 '16 at 0:10
  • $\begingroup$ @RobArthan Yes! Certainly I thought of that question of yours, and almost thought to ask "Whadya mean, 'computable'?" It seems that now we have three words for the same notion, at least when applied to sets: "computable", "decidable", "recursive". "Computable" is already overloaded, I too think this usage increases the load past the breaking point. $\endgroup$ – BrianO Feb 15 '16 at 0:22

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.

| cite | improve this answer | |

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.