Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
