# Are co-semidecidable languages separated by decidable ones?

Can I use principles of set theory in order to solve the following question?

For every $A,B \in \mathsf{co\text{-}RE}$ with $A \cap B = \emptyset$, there is a separating language $C$ with $A \subseteq C$ and $B \cap C = \emptyset$ so that $C$ is recursive.

• Please take more care when phrasing questions; I attempted to make your question readable, please check I got the problem right. What do you mean with "principles of set theory" in this context? What have you tried to do in order to approach this problem?
– Raphael
Feb 17 '13 at 10:06

This is a classical exercise in computability. Since $A,B\in coRE$, there exist TMs $M,N$ that recognize $\overline{A}$ and $\overline{B}$ respectively.

Consider the following TM $K$: Given a word $w$, run in parallel $M$ and $N$ on $w$. That is, simulate $M$ for a single step, and then $N$ for a single step, and repeat.

If $M$ accepts at any point, reject. If $N$ accepts at any point, accept. (if both accept, reject, so we first check $M$ for acceptance).

Define $C=L(K)$.

If $A\cap B=\emptyset$, then $\overline{A}\cup\overline{B}=\Sigma^*$, so either $M$ or $N$ eventually accepts, so $K$ always halts. Thus, $C$ is decidable.

We claim that $C$ satisfies the requirements: if $x\in A$, then $M$ never accepts $x$, so $N$ accepts $x$, so $K$ accepts, so $x\in C$. Thus, $A\subseteq C$.

If, by way of contradiction, $x\in B\cap C$, then $K$ accepts $x$, which means $N$ accepts $x$, so $x\notin B$ - contradiction. So $B\cap C=\emptyset$.

We conclude that $C$ satisfies the requirements.

• just note that $K$ runs 1 step of M and 1 of N. Then it is never the case that both accept (if one accepts, we stop running $K$). Dec 28 '14 at 1:05

The thing you are trying to prove is called the "separation principle" for $\Pi^0_1$ sets (remember co-r.e. sets are $\Pi^0_1$ and r.e. sets are $\Sigma^0_1$ in the arithmetical hierarchy).

The dual "reduction principle" for $\Sigma^0_1$ sets states that given two $\Sigma^0_1$ sets $X,Y$ whose union is $\mathbb{N}$, it is possible to find $\Sigma^0_1$ sets $X',Y'$ with $X' \subseteq X$, $Y' \subseteq Y$, $X' \cap Y' = \emptyset$, and $X' \cup Y' = \mathbb{N}$. This is proved in the way Shaull indicates: put a number into $X'$ if it enters $X$ before $Y$, put it in $Y'$ if it enters $Y$ before $X$, and put "ties" into $X'$. Note that $X'$ and $Y'$ will be complements of each other and thus computable.

The question is then answered by starting with $\Pi^0_1$ sets $A,B$, letting $X= A^c$ and $Y=B^c$ be the complementary $\Sigma^0_1$ sets, and applying the reduction principle. Then you can just let $C = Y'$. A small Venn diagram calculation shows that $C$ is indeed a separating set for $A$ and $B$. For example, because $C= Y' \subseteq Y = B^c$, we have that $C \cap B = \emptyset$.

The reduction principle and separation principle are two classical principles that a class of sets may or may not satisfy. For example, the reduction principle holds for $\Sigma^0_1$ sets, but not for $\Pi^0_1$ sets. Dually, the separation principle holds for $\Pi^0_1$ sets (as in the question) but not for $\Sigma^0_1$ sets. Much more is known about which other classes of sets satisfy these principles, which date back to work of Kuratowski. For example see the Encyclopedia of Mathematics or section 7 of a classic article by John Addison, Separation principles in the hierarchies of classical and effective descriptive set theory, Fundamenta Mathematicae 46, 1958