# There exist countably many enumerable disjoint and inseparable sets

I want to formally prove that there are countably many disjoint enumerable sets such that any two of them cannot be separated by a decidable set.

I know that there exist a computable function $f$ that takes only values 0 and 1, and this can be used to define two sets (let's say $\mathcal{A}$ and $\mathcal{B}$, where $\mathcal{A}=\{x$ $s.t. f(x)=1\}$ and $\mathcal{B}=\{x$ $s.t. f(x)=0\}$).

Could you please help me to extend this arguments to find (countably) many such sets?

• "separated by a decidable set" -- what does that mean? Is this decidable set given, or should it say "any"? – Raphael Oct 17 '17 at 18:15
• "extend this argument" -- you have not given any argument. You stated a fact. What argument do you have in mind? – Raphael Oct 17 '17 at 18:16
• @Raphael it means that if two enumerable sets cannot be separated by a decidable set, none of them is decidable. I know this is a fact and that it is the fact used to prove the statement for the two sets mentioned above. I was wondering if this could be somehow be generalised to show there are countably many of these sets. I would really appreciate your hints. – FunnyBuzer Oct 17 '17 at 18:41
• I don't know what "A, B are separable by C" means. Maybe I forgot, but maybe it's non-standard terminology that you should explain. Does it have to do with some set difference? – Raphael Oct 17 '17 at 20:33
• @Raphael Two sets $A,B$ are separated by $C$ if $C$ contains $A$ and is disjoint from $B$ (i.e. $\overline{C}$ contains $\overline{B}$). – Yuval Filmus Oct 17 '17 at 20:44

## 2 Answers

Let $\phi$ be an enumeration of the set of recursive partial functions.

For each $i\in\mathbb N$, let $X_i = \{ n\ |\ \phi_n(0)=i \}$.

These sets are pairwise disjoint by construction. Each $X_i$ is recursively enumerable but not recursive.

These sets are pairwise inseparable. By contradiction assume there exist $i\neq j$, and a recursive set $A$ with $X_i \subseteq A$ and $X_j \subseteq \mathbb N\setminus A$. We reach a contradiction as follows. The function

$$g(k,y) = \begin{cases} j & \mbox{if } k \in A \\ i & \mbox{o.w.} \end{cases}$$ is computable, hence $g=\phi_c$ for some $c$. Now exploit the s-m-n lemma to define $h(k) = \mathsf s(c,k)$, so that $\phi_{h(k)}(y) = g(k,y)$. Since $h$ is recursive total, by the second recursion theorem for some $k$ we have $\phi_{h(k)} = \phi_k$. Let us take one such $k$. Finally,

$$\phi_k(0) = \phi_{h(k)}(0) = g(k,0) = \begin{cases} j & \mbox{if } k \in A \\ i & \mbox{o.w.} \end{cases}$$

Now, the result above is either $j$ or $i$. If it is $j$, then $k\in X_j$, hence $k\notin A$, hence the result above is $i$ -- contradiction. If it is $i$, then $k\in X_i$, hence $k\in A$, hence the result above is $j$ -- contradiction.

Suppose $A$ and $B$ are computably enumerable disjoint inseparable sets. For each $n$, so are the sets $A_n = \{a + n \mid a \in A\}$ and $B_n = \{b + n \mid b \in B\}$. The pairs $(A_n, B_n)$ are all different. Indeed, let $a_0 \in A$ be the minimal element of $A$. The minimal element of $A_m$ is $a_0 + m$. So if $A_m = A_n$ then they both have the same minimal element, $a_0 + m = a_0 + n$, therefore $m = n$.