Standard construction of a (co-c.e.) immune set
Let us follow the standard construction by Emile Post from his famous 1944 paper (see section 5) introducing reducibilities in computability theory.
The standard example of an immune set is as follows. Consider the set
$$P = \{\langle m, n\rangle \mid n > 2 m \land n \in W_m \},$$
where $\langle {-}, {-}\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is an acceptable pairing function. There is a computable selection function $f$ for $P$, i.e., a partial function $f$ such that: for every $m \in \mathbb{N}$, if there is $n \in \mathbb{N}$ such that $\langle m, n \rangle \in P$ then $f(m)$ is defined and $\langle m, f (m) \rangle \in P$. (Why does such an $f$ exist? Exercise!)
Observe that $f$ is defined at infinitely many values. Indeed, there are infinitely many $m \in \mathbb{N}$ such that $W_m$ is infinite, and at least at all of those $f(m)$ is defined.
Now let $S$ be the image of $f$, i.e.,
$$S = \{n \mid \exists m \in \mathbb{N} . f(m) = n\}.$$
We claim that the complement $I = \mathbb{N} \setminus S$ is immune:
Because $f(m) > 2 m$ for every $m$ at which $f$ is defined, the set $I$ is infinite. Indeed, among the numbers $0, 1, \ldots, k$, at most $k/2$ can be enumerated by $f$, so at least all the rest will be in $I$.
Suppose we had an infinite c.e. set $U \subseteq I$. There is $m$ such that $U = W_m$. Because $U$ is infinite, $f(m)$ is defined, hence $f(m) \in W_m = U \subseteq I$. On the other hand, by the definition of $I$ we also have $f(m) \in S \not\in I$, a contradiction. Therefore $U$ cannot be infinite.
The intuition behind the construction
Here is an informal explanation of $I$. The set $I$ has to satisfy two opposing conditions:
- $I$ must be large enough (infinite).
- $I$ must not be too large (for every infinite $W_m$, it has to avoid an element of $W_m$).
If we only cared about the first condition, we would take $I = \mathbb{N}$. If we only cared about the second condition, we would take $I = \emptyset$. But the two conditions work against each other.
Our first atempt could be this: for each infinite c.e. set $W_m$, pick an element $f(m) \in W_m$, let $S = \{f(m) \mid \text{$W_m$ is infinite}\}$ and let $I = \mathbb{N} \setminus S$. Then we satisfied the second condition, since $f$ enumerated one element of each infinite $W_m$, and we avoided all of those. However, there is no guarantee that $I$ is large enough – what if $S = \mathbb{N}$?. We can do better by making sure that
$f$ is computable so that $I$ will end up being co-c.e.
force $f$ to pick ever larger elements, so that we can be sure that it skips lots of numbers, which then end up being in $I$.
We achieve both of these with our constuction.
Let me finish with an interesting observation. In the effective topos, an immune set is an example of a subset of $\mathbb{N}$ which is neiter finite nor infinite.