# Decidability Turing Machines

Let $\Sigma$ be an alphabet, and suppose that $A$, $B \subseteq \Sigma^*$ are Turing recognizable languages where both $A \cup B$ and $A \cap B$ are decidable. Prove that $A$ is decidable.

Is this true? I have tried to prove it by considering the intersection and complement of the sets, but I think I am missing something.

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jun 27 '16 at 6:39
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Jun 27 '16 at 6:39

Given an $x$ (for which you want to check membership in $A$), I would start by checking if $x \in A \cap B$, which is possible, since $A \cap B$ is decidable. If $x \in A \cap B$ you also know that $x \in A$.
If $x \not\in A \cap B$, you can continue and ask whether $x \in A \cup B$.
If so, either $x \in A$ or $x \in B$. Since $A$ and $B$ are Turing recognizable, you can enumerate both sets in an interleaved fashion. Let $a_i \in A$ and $b_i \in B$ be the respective elements in the enumeration. Since $x \in A \cup B$, there is an $i$, such that $a_i = x$ or $b_i = x$, but not both. If $a_i = x$, then $x \in A$, else $x \not\in A$.
If $x \not\in A\cup B$, then $x \not\in A$.