HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#98108, answer score: 3

Revisions (0)

No revisions yet.