Non-recursively enumerable set with non-recursively enumerabale complement.

Question

Is it possible to construct a non-recursively enumerable subset of $\mathbb{N}$, such that it's complement is also not recursively enumerable?

Answer 1

Yes - indeed, most sets have this property.

---

The simplest (and most broadly applicable) way to see this is just by counting.

Remember, there are uncountably many sets of natural numbers (by Cantor's argument), but there are only countably many r.e. sets of natural numbers (since there are only countably many Turing machines). This immediately tells us that not every set of natural numbers is r.e., and with a bit of thought (this is a good exercise) also shows that there are sets of natural numbers which are neither r.e. nor co-r.e. (HINT: otherwise, can you see how to get a "$2$-to-$1$" map from $\mathcal{P}(\mathbb{N})$ to $\mathbb{N}$, and why this is impossible?).

---

We can also do a more computability-flavored argument. Let $A$ be r.e. but not recursive, and consider $$A\oplus (\mathbb{N}\setminus A)=\{2n: n\in A\}\cup\{2n+1: n\not\in A\}.$$ If $A\oplus(\mathbb{N}\setminus A)$ were r.e., then its "odd part" $\{2n+1: n\not\in A\}$ would be r.e., but then $A$ would be both r.e. and co-r.e. and hence recursive; and if $A\oplus (\mathbb{N}\setminus A)$ were co-r.e., then its "even part" $\{2n: n\in A\}$ would be co-r.e., but then $A$ would be both r.e. and co-r.e. and hence recursive (checking this is a good exercise).

---

This, however, still has a drawback: the resulting set $A\oplus (\mathbb{N}\setminus A)$ is still "almost r.e." in the sense that it is Turing equivalent to an r.e. set (namely, $A$ itself). A more satisfying computability-theoretic argument uses the Turing jump: namely, since ${\bf 0}^{''}>_T{\bf 0}^{'}$ and every r.e. set is $\le_T{\bf 0}^{'}$, we know that ${\bf 0}^{''}$ can't be Turing equivalent to any r.e. set. (And remember that r.e. and co-r.e. are the same up to Turing equivalence.)