2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "separated by a decidable set" -- what does that mean? Is this decidable set given, or should it say "any"? $\endgroup$ – Raphael Oct 17 '17 at 18:15
  • 1
    $\begingroup$ "extend this argument" -- you have not given any argument. You stated a fact. What argument do you have in mind? $\endgroup$ – Raphael Oct 17 '17 at 18:16
  • 1
    $\begingroup$ @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. $\endgroup$ – FunnyBuzer Oct 17 '17 at 18:41
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Oct 17 '17 at 20:33
  • 1
    $\begingroup$ @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}$). $\endgroup$ – Yuval Filmus Oct 17 '17 at 20:44
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.