|
Can I use principles of set theory in order to solve the following question?
|
||||
|
|
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. |
||||
|
|
|
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 |
|||
|
|
