Intersection/Union of recursively enumerable languages that aren't decidable?

Problem Detail: 

For $L_1, L_2 $ and $L_1 \in RE $ and $ L_1\notin R$ and $L_2 \in RE $ and $ L_2\notin R$

I was asked to prove/disprove if the following can occur:

1. $L_1 \cap L_2 \in R$
2. $L_1 \cup L_2 \in R$
3. $L_1 \cap L_2 \in R$ and $L_1 \cup L_2 \in R$

For 1., I think any two disjoint langauges will suffice (because the empty set is decideable).

For 2., I think something along the lines of a language and its complement but I'm struggling to think of an example.

For 3,. it seems impossible but I have no idea how to prove it.

Any help/further insight would be welcomed!

Asked By : Mark

Answered By : David Richerby

1. Correct. We can have $L_1\cap L_2=\emptyset\in R$. A good answer would give an example of such a pair $L_1$, $L_2$ so you should figure that out on your own.

2. Correct but for the wrong reason. If $L_1$ and its complement are both $RE$, then both are recursive and the question says that neither is recursive. You should prove this yourself, as you'll need it for the next part.

   • Hint for this proof: show how to use machines that accept $L_1$ and $\overline{L_1}$ to give a machine that decides $L_1$.)
   • Hint for the question: take a recursives language $K_1$ and $K_2$ and set $L_1=K_1 \cup \text{something}$ and $L_2=K_2\cup\text{something else}$ in a way that gives $L_1\cup L_2=K_1\cup K_2$.

3. Correct. We know that $L_1\in RE$. Use $L_1\cap L_2\in R$ and $L_1\cup L_2\in R$ to show that $\overline{L_1}\in RE$. By the extra proof I suggested you do in the previous part, that means that $L_1\in R$, contradicting the requirement that $L_1\in RE\setminus R$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23826