Let be $A, B \subset \mathbb{N}$ are recursively enumerable, $A\cup B$ and $A \cap B$ recursive. I want to show that $A$ and $B$ are recursive.

By negation theorem $X \subset \mathbb{N}$ is recursive iff $X$ and $X^c$ are recursively enumerable.

How do I complete the proof using that?


1 Answer 1


The basic observation is $$ \begin{align*} A^c &= (A^c \cap B^c) \cup (A^c \cap B) \\ &= (A \cup B)^c \cup (B \cap (A^c \cup B^c)) \\ &= (A \cup B)^c \cup (B \cap (A \cap B)^c). \end{align*} $$ Using this you can recursively enumerate $A^c$. I'll let you figure out how.

  • $\begingroup$ Of course! By negation theorem $(A \cup B)^c, B$ and $(A \cap B)^c$ are r.e., thus $A^c$ is too because is union and intersecction of r.e. Thank you! $\endgroup$
    – Tom Ryddle
    Oct 4, 2018 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.