$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}$

Question

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.

Answer 1

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:

1. For each $s_i \in \Sigma^*$ (in lexicographic order):
2. 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.
3. If $M$ halts, $s_i \in A$, which means certainly $s_i \not\in \overline{A} \cap B$, so print $s_i$.
4. 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.

Answer 2

I believe 'C' is not also turing decideable. Consider the following 3 cases:

Case 1 : Intersection of A and B is empty set and neither of them is empty. Then A and B become Turing Decidable, therefore C also becomes turing decidable. Closure properties for TM.

Case 2: Intersection of A and B is either of them (Lets say A-B = A). Then, language (B-A) transforms to an undecidable, as its equivalent to the language which is empty. C = A-B = A, is Turing recognizable.

Case 3: Intersection of A and B is non-empty. Now, for C - TM for A should accept which would as its acceptor and TM for B should reject as it shouldnt belong to it. BUT since, B is an Turing recognizable(not decider) only (assuming from your query), it means it might never halt for the input which doesnt belongs to it. Thereby, the TM accepting C might never halts for strings belonging to C.Thereby, C doesnt have any acceptor.