$A$ and $B$ are Turing-recognizable and their union is $\Sigma^*$, find a decidable $C$ with $A - B \subseteq C$ and $B - A \subseteq \overline{C}$ Sorry for long title - the question is a bit unwieldy. To state the question precisely, I'm wondering about the following proposition:


  Let $\Sigma = \{0,1\}$. If $A$ and $B$ are Turing-recognizable and $A \cup B = \Sigma^*$, then there exists a Turing-decidable language $C$ such that $A \cap \overline{B} \subseteq C$ and $\overline{A} \cap B \subseteq \overline{C}$ (equivalently, $A - B \subseteq C$ and $B - A \subseteq \overline{C}$


So, my current train of thought is as follows.
Because $A \cup B$ is $\Sigma^*$, we have that $\Sigma^*$ is partitioned into exactly three disjoint sets: $A - B$, $A \cap B$, and $B - A$. That is, given $x \in \Sigma^*$, $x$ is in exactly one of these sets.

The basic way I can think of to obtain a decidable language is to enumerate one in lexicographic order (which always yields a decidable language). So one idea would be to enumerate $\Sigma^*$ in lexicographic order, and print a string if and only if it is not in $B - A$, but that poses a problem because we would have to decide membership in $B - A$, but they are merely recognizable.

I've thought about enumerating $A$ and $B$ but since they're only recognizable, the enumerations could be in any arbitrary order, making it impossible to compare them to test for membership in $A-B$ or $B-A$.

Finally, I know that $A$ and $B$ (if they are infinite) have infinite decidable subsets, but I don't think that will help.

I'd appreciate some hints if anyone has any.

Edit: Missed a hypothesis that $\Sigma = \{0,1\}$, which I'm not sure is relevant (I wouldn't think so), but it might be.
Got it. The question makes it seem more complicated than it really is.

Let $M$ and $N$ be TMs that recognize $A$ and $B$, respectively.
Construct an enumerator $E$ that behaves as follows:


For each $s_i \in \Sigma^*$ (in lexicographic order):
Run $M$ and $N$ on $s_i$ simultaneously. It must be the case that $s_i$ is in at least one of $A$ or $B$. So, at least one machine is guaranteed to halt.
If $M$ halts, $s_i \in A$, which means certainly $s_i \not\in \overline{A} \cap B$, so print $s_i$.
If $N$ halts, $s_i \in B$, which means certainly $s_i \not\in A \cap \overline{B}$, so do not print $s_i$.


So $E$ prints at least all the strings in $A \cap \overline{B}$, and definitely does not print strings in $\overline{A} \cap B$.
$E$ enumerates a language in lexicographic order, so its language is decidable and satisfies the conditions.