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.

  • $\begingroup$ 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? $\endgroup$
    – 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.

  • $\begingroup$ 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$). $\endgroup$
    – Ran G.
    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


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.