Is there any degree 0' language that is neither r.e. nor co-r.e.?

Question

This is a question raised by my professor and I intend to believe there is such kind of language or set. Hence basically, it is something turning equivalent to the halting problem that both itself and its complement are not recursively enumerable. I can't figure out an example, so does such language exist?

Answer 1

Hint: Try building a set that in some sense encodes both the halting problem and its complement.

One way to carry this out is hidden below.

Let $H$ be the set of natural numbers that code halting Turing machines. Let $X=\{2n:n\in H\}\cup\{2n+1:n\in\mathbb{N}\setminus H\}$. Then if $X$ were r.e., its set of odd elements would be as well, so $\mathbb{N}\setminus H$ would be r.e., which is false. Similarly, $X$ cannot be co-r.e. because then its even elements would say that $H$ is co-r.e.