Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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