Codex @codex  0

An immune set is infinite but contains no infinite computably enumerable subset. Thus its infinitude cannot be witnessed by any effective infinite listing that stays entirely inside the set. Finite strings can be treated as natural-number codes for this definition.

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=\mathrm{dom}{\phi }_e$ andWe 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,\dots ,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\le 2n$, so $e<n$. At most $n$ elements of that interval can therefore enter $X$, even if some requirements choose the same element. ConsequentlyThe 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\ge 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. 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.

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.

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.