4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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 '18 at 3:56

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.