Definition of an immune set

Question

I'm reading a theorem about existence of a simple set.

The definition of an immune set can be found from here

A set ${\displaystyle I\subseteq \mathbb {N} }$ is called immune if ${\displaystyle I}$ is infinite, but for every index ${\displaystyle e}$, we have ${\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I}$. Or equivalently: there is no infinite subset of ${\displaystyle I}$ that is recursively enumerable.

I am not able to understand this definition, because I couldn't come up with example.

Answer 1

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:

1. 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$.

2. 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:

1. $I$ must be large enough (infinite).
2. $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.

Answer 2

An interesting example of immune set is the set of random numbers in Kolmogorov complexity.

The Kolmogorov complexity $k(n)$ of a number $n$ is the smallest $i$ such that $\varphi_i(0) = n$. The idea is that we are comparing a number with alternative, effective descriptions of it.

A number is called random if $n \le k(n)$, that is, when it is its own shorter description.

Let $\mathcal{R}$ be the set of random numbers. It is easy to see that $R$ is not empty, and $\overline{R}$ is r.e.

Let us prove that $R$ is immune.

Let $A$ be an infinite subset of $R$. Let us suppose that it is r.e. and let $f$ be an effective enumeration for it, that is $A = cod(f)$.

By the $s_{mn}$ theorem, there exists a total computable function $h$ such that $$\varphi_{h(i)}(x) = f(\mu n. f(n) > i)$$ Note that $h(i)$ "describes" a random number in $A$ larger than $i$ (that appears in the enumeration $f$ the earliest), and hence (being random) not describable with a program smaller or equal to $i$.

Now, take a fixed point $m$ for $h$. Then, the program $m$ describes a number that cannot be described by a program smaller or equal to $m$, which is clearly an absurdity. Hence, A cannot be r.e.

I could have been a bit more formal, but the idea of the proof is much more interesting than the details. Note the obvious analogy with Berry's paradox (the smallest number that cannot be defined with less than $m$ characters, where $m$ is the length of this definition).