# If $A,B$ are r.e. and $A\cup B,A \cap B$ are recursive, then so are $A,B$

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?

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.
• 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! – Tom Ryddle Oct 4 '18 at 3:56