I am studying a qualifying exam and this computability theory question has been bothering me for days, so I am hoping to get help.
An infinite set $X\subset\omega$ is called immune if it contains no infinite c.e. set. A c.e. set is called simple if its complement is immune.
The question asks: Let $A$ be a simple set. Show that there is a partial computable $\psi$ such that whenever $W_e$ is an infinite c.e. set, we have $\psi(e)\downarrow\in W_e\cap A$. Also, show that $\psi$ cannot be total.
I solved the first half of this question without much difficulty. My constructed partial computable $\psi$ is as follows: Let $(a_m)_{m\in\omega}$ be a one-to-one computable enumeration of $A$. We define $\psi$ as follows: on input $n$, search for $\langle s,m\rangle$ in the increasing order such that $\varphi_{n,s}(a_m)\downarrow$. If we find such $\langle s,m\rangle$, then halt with the output $a_m$.
It is also not hard to see that my constructed $\psi$ is not a total function. Pick $a\in A^c$. If we let $e$ be such that $W_e=\{a\}$, then $\psi(e)\uparrow$. But what I am stuck is that I couldn't prove that: for any partial computable $\psi$ with the above property, $\psi$ is not total.
Please help me!
This actually has nothing to do with simplicity! It's a recursion theorem trick.
Suppose that $\psi$ were a partial function satisfying your hypothesis. There is$^*$ a total computable function $F$ such that, for every $a$, $W_{F(a)}$ (intuitively speaking) waits until it sees $\psi(a)\downarrow$ at which point it enumerates everything but the output of $\psi(a)$. Formally, we have $$W_{F(a)}=\{x:\exists y(\psi(a)[y]\downarrow\not=x)\}$$ (where "$[y]$" means "run for $y$-many steps").
Now by the recursion theorem, there is a $c$ such that $W_{F(c)}=W_c$; intuitively, $W_c$ runs $\psi$ on its own index and then plays havoc with the result. Specifically, if $\psi(c)\downarrow$ then $W_c$ is infinite but $\psi(c)$ fails to be an element of $W_c$, let alone of $W_c\cap A$.
Note that $A$ played no role here at all and infinitude was unnecessary! What we've actually shown is the following:
$^*$Per your previous question, you may find this rather blithe of me. Depending which formalism you use, carefully proving the existence of such an $F$ is either a quick exercise with Kleene's $T$-predicate or a tedious construction involving a universal Turing machine. Either way, though, it's not particularly hard, and this sort of recursion theorem trickery is a fundamental tool in the subject so it's worth spending as much time as you need justifying this to your own satisfaction.