patternMinor
If $A,B$ are r.e. and $A\cup B,A \cap B$ are recursive, then so are $A,B$
Viewed 0 times
arecapcuprecursivethenand
Problem
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?
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?
Solution
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.
$$
\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.
Context
StackExchange Computer Science Q#98108, answer score: 3
Revisions (0)
No revisions yet.