# Is the set of surjective recursive functions in RE/coRE?

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.
• @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). – chi Jan 10 at 13:58