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.

  • 1
    $\begingroup$ What is $W_e$? The $e$th RE set? $\endgroup$ – David Richerby Jan 23 '17 at 15:06
  • $\begingroup$ Yes I think, also it should be subset of I, but should not be infinite $\endgroup$ – shcolf Jan 23 '17 at 15:12
  • 2
    $\begingroup$ Given that Emil Post couldn't prove that these things exist, and proving it required the development of a whole new method, this might be too big a question for Stack Exchange. But maybe it's possible to give a reasonable length exposition -- it's not my area so I don't know. $\endgroup$ – David Richerby Jan 23 '17 at 15:40
  • $\begingroup$ It's not true that immune sets are difficult to find. Emile Post was looking for an intermediate Turing degree, which is not the same thing, and is quite easily described. $\endgroup$ – Andrej Bauer Mar 13 '17 at 7:12
  • $\begingroup$ I added an answer with a reference to the famous paper by Emile Post in which he constructs an immune set. $\endgroup$ – Andrej Bauer Mar 13 '17 at 9:54

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.


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).

  • $\begingroup$ Note that the immunity of $R$ is actually intuitive by the following argument: If there exists an algorithm $f$ that outputs an infinite sequence of random numbers, then $f$ can be easily modified to output a specific arbitrarily large random number, which contradicts its Kolmogorov randomness. The application of Roger's fixed point theorem is just to formalize the intuitive concept of "easily modified". $\endgroup$ – Imperishable Night Apr 4 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.