 Solution

An immune set is an infinite set containing no infinite computably enumerable subset. For binary strings, use an effective bijection with natural numbers when discussing enumeration. Fix an optimal description machine $U$ and define the plain Kolmogorov complexityAn incompressible string has no description shorter than itself, that is, $C_U(\sigma )\ge |\sigma |$. The choice of machine is fixed throughout the proof.

Let $I$ be the set of incompressible strings. There are $2^n$ strings of length $n$, but only $1+2+\cdots +2^{n-1}=2^n-1$ programs of length less than $n$. Each halting program describes at most one string, so at least one string of each length belongs to $I$. Consequently $I$ is infinite.

Suppose an infinite computably enumerable set $E$ were contained in $I$. Define a total computable function $q(n)$ by running an enumeration of $E$ until a string of length at least $n$ appears, and outputting the first such string. This search always terminates because there are only finitely many binary strings of bounded length. A fixed program can reconstruct $q(n)$ from a self-delimiting binary code of $n$. For example, if the binary expansion of $n$ has length $\ell$, encode it using $\ell$ copies of one, a zero separator, and its $\ell$ binary digits. This givesfor a constant $c$ depending on the enumeration algorithm and the optimal description machine, not on $n$. For sufficiently large $n$ this is less than $n\le |q(n)|$, contradicting $q(n)\in I$. Thus the set of incompressible strings is an immune set. This proves immunity of incompressible strings. The argument uses the ability to describe a selected long string by the short threshold specifying how it was selected.