= Solution
A subset $E\subseteq\mathbb N$ is <recursive set>[recursive] when its <indicator function> is a <total computable function>. It is <recursively enumerable set>[recursively enumerable] when it is the domain of a <partial computable function>, equivalently when an algorithm can enumerate its members.
If $E$ is recursive, its indicator decides both $E$ and its complement, so both sets are recursively enumerable. Conversely, suppose programs enumerate $E$ and $\mathbb N\setminus E$. On input $n$, run the two enumerations in parallel by <dovetailing>. Exactly one must eventually print $n$; accept in the first case and reject in the second. This algorithm always halts and decides $E$. Hence
$$
\boxed{E\text{ is recursive}\iff E\text{ and }\mathbb N\setminus E\text{ are recursively enumerable}}.
$$
Back to article page
