Let $W\subseteq\omega$ be an infinite c.e. set. Show that there is an infinite $X\subseteq W$ such that $X$ is computable.

Question

If I can prove that $X$ is c.e. and $\omega \setminus X$ is c.e. then I can prove that $X$ is computable by the theorem "Let $W \subseteq \omega$. Then $W$ is computable iff both $W$ and $\omega \setminus W$ are c.e". But I'm not able to proceed on how should I do this.

Answer 1

Take a computable surjection $f : \omega \to W$.

Define $V = \{f(x) \mid x \in \omega$ and $\forall y < x (f(y) < f(x))\}$. Clearly, $V \subseteq W$.

Then $V$ is decidable. For to decide whether $v \in V$, simply keep generating $f(x)$ for $x = 0, 1, \ldots$ until we come up with the first output $\geq v$. If this is $v$, then $v \in V$; otherwise, $v \notin V$.

And $V$ is infinite. For if $f(x) \in V$, take the smallest $y$ such that $f(y) > f(x)$; then $f(y) \in V$.