Computably enumerable set

Remarks

The following conditions on $A \subseteq \N$ are equivalent.

1. $A$ is computably enumerable.
2. $A$ is empty or the range of a total computable function $\N \to \N$.
3. There is a computable set $R \subseteq \N^2$ such that $A = \set{n : \exists m \, (n, m) \in R}$.

Example: the halting set $K = \set{e : \text{program } e \text{ halts on input } e}$ is computably enumerable. It is the domain of the partial computable function that, on input $e$, runs program $e$ on input $e$ and then outputs $0$.

Non-example: the complement $\N \setminus K$ is not computably enumerable. Otherwise $K$ and its complement would both be computably enumerable, and then $K$ would be computable, which is false.