Let L be a set of recursive funtions with $L = \{i\in \mathbb{N}|f_i\space is\space surjective\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$?

I can't think of a way to show either of the two.


Rice-Shapiro proves that $L$ is not RE nor coRE.

Let $F$ be the set of computable surjective functions. $L$ is the the index set associated to $F$.

Assume by contradiction $L$ is RE. By Rice-Shapiro (compactness), since the identity function belongs to $F$, some finite restriction of the identity must belong to $L$ as well. But a finite-domain function can not be surjective -- contradiction.

Assume by contradiction $\bar L$ is RE. The always undefined function $g$ belongs to $\bar F$, so by Rice-Shapiro (monotonicity), $\bar F$ contains any computable extension of $g$, including the identity function, which is surjective. Contradiction.

  • $\begingroup$ I don't quite understand the second proof. How does Rice-Shapiro state that F^c contains the identity function? $\endgroup$ – Yamahari Jan 10 '19 at 13:02
  • $\begingroup$ @Yamahari $F^c$ contains the always undefined function, so by RS we can extend it in any computable way (say to the identity) and still be inside $F^c$. Pedantically: RS states that the identity belongs to $F^c$ IFF some finite restriction of the identity belongs to $F^c$. The latter is true, so the former must also be true (it's an IFF, not only an implication). $\endgroup$ – chi Jan 10 '19 at 13:58

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.