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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Jun 27 '16 at 6:39
  • 1
    $\begingroup$ 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! $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ You might consider not encouraging undesirable posting behaviour in the future. Up to you. Your decision -- I respect whatever you decide, either way. $\endgroup$ – D.W. Jun 27 '16 at 16:50

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.