Recursively enumerable set

A set is computably enumerable when a program halts precisely on its members. Equivalently, it is the domain of a partial computable function or some algorithm lists its elements.

A computably enumerable set is simple when its complement of a set is an immune set: the complement is infinite and contains no infinite computably enumerable subset. Equivalently, it is coinfinite and meets every infinite computably enumerable set. A simple set is not decidable.

Enumerate all computably enumerable sets as $W_e$. For each $e$, once a witness $x>2e$ appears in $W_e$, enumerate one such witness into $X$ and never act for $e$ again. Every infinite $W_e$ supplies a witness. Only requirements $e<n$ can put numbers into $[0,2n]$, so at least $n+1$ numbers in that interval stay outside $X$. Thus $X$ is a simple set. The proof uses a numerical bound rather than an infinitude test.

An immune set is infinite but contains no infinite computably enumerable subset. Thus its infinitude cannot be witnessed by any effective infinite listing that stays entirely inside the set. Finite strings can be treated as natural-number codes for this definition.

Every nonempty computably enumerable set $X\subseteq \mathbb{N}$ is the range of a primitive recursive function $f:\mathbb{N}\to \mathbb{N}$. Choose $x_0\in X$, decode $n=⟨x,t⟩$ using a primitive recursive pairing function, and output $x$ if the recognizing machine halts within $t$ steps, or $x_0$ otherwise. The bounded halting predicate makes this function primitive recursive, and every member of $X$ occurs for a sufficiently large bound. The empty set is excluded because such a function is total.

A set is computable when an algorithm decides membership for every input and always halts. Equivalently, both the set and its complement are computably enumerable.

For a nonempty set $A$ of words, the following are equivalent: $A$ is computably enumerable, $A$ is the domain of a partial computable function, $A$ is the range of a partial computable function, and $A$ is the range of a total computable function. The nonempty hypothesis is needed only for the last formulation, since the range of a total function cannot be empty.