Simple set

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.