= Solution
Let $(W_e)_{e\in\mathbb N}$ enumerate all <computably enumerable sets>, with finite uniformly computable approximations $W_{e,s}$ increasing to $W_e$. For example, take $W_e=\operatorname{dom}\varphi_e$ and
$$
W_{e,s}=\{x<s:\varphi_e(x)\text{ halts within }s\text{ steps}\}.
$$
We construct a <simple set> by meeting the requirements $R_e$: if $W_e$ is infinite, then $W_e\cap X\ne\varnothing$. Begin with no enumerated elements and all requirements unmarked. At stage $s$, process $e=0,1,\ldots,s$ in this order. For an unmarked $R_e$, if there is an $x\in W_{e,s}$ with $x>2e$, enumerate the least such $x$ into $X$ and mark $R_e$ permanently. All membership tests at a stage are finite, and marking requires no test for eventual infinitude. The <sparse-witness construction of a simple set> therefore gives a <computably enumerable set> $X$; it is <semidecidable> by simulating this enumeration and halting when the input appears.
Each requirement enumerates at most one element. If an element in $[0,2n]$ is enumerated by $R_e$, then $2e<x\leq2n$, so $e<n$. At most $n$ elements of that interval can therefore enter $X$, even if some requirements choose the same element. Consequently
$$
\boxed{|[0,2n]\setminus X|\geq(2n+1)-n=n+1.}
$$
The <complement of a set> $\mathbb N\setminus X$ is infinite.
If $W_e$ is infinite, it contains some $x>2e$, and that element eventually belongs to $W_{e,s}$ at a stage with $s\geq e$. If $R_e$ has already acted, it already placed an element of $W_e$ in $X$. Otherwise it acts by this stage and does so now. Thus every infinite <semidecidable set> meets $X$. Equivalently, its infinite <complement of a set> is an <immune set>. \b[The constructed $X$ is semidecidable, coinfinite, and meets every infinite semidecidable set.]
As a useful check on the construction, $X$ cannot be a <computable set>. If it were, its infinite <complement of a set> would also be a <computably enumerable set> disjoint from $X$, contradicting the property just proved. The argument requires neither deciding which $W_e$ are infinite nor protecting a prechosen infinite list of omitted numbers; the numerical witness bound provides all the required room.
Back to article page
