= Nonempty computably enumerable sets are primitive recursive ranges
{title2=$X=\operatorname{ran}(f)$}
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=\langle x,t\rangle$ 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.
Back to article page
