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

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!

-
Note that for 1, it's not enough to show that some particular $L_1$ and $L_2$ have an intersection in $R$. I'm guessing they want you to show it's true for all RE languages i.e. that RE is closed under intersection. If you're disproving closure, one counter-example is enough though. – jmite Apr 15 '14 at 20:37
@jmite It's absolutely enough to show that some particular $L_1$, $L_2$ have an intersection in $R$! The question asks, is it possible? So an answer to any of the parts would be either a particular $L_1$ and $L_2$ with the required property, a proof that such a pair exists, or a proof that no $L_1$, $L_2$ have that property. – David Richerby Apr 15 '14 at 20:41
For your second point, recall that if a language and its complement both are recursively enumerable, then they are recursive as well. – Pål GD Apr 15 '14 at 21:01

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$.

-

Hint for 2: Consider $L_1 = \{ 0 w : w \in L \} + \{ 1 w : w \in \{0,1\}^* \}$ and let $L_2$ be a complementary language.

Hint for 3: $L_2 \setminus (L_1 \cap L_2) = \overline{L_1} \cap L_2$ and $\overline{L_1 \cup L_2} = \overline{L_1} \cap \overline{L_2}$.

-
What is the explanation for $L_2 \setminus (L_1 \cap L_2) = \overline{L_1} \cap L_2 \in R$? – Elimination May 25 '15 at 12:41
@Elimination It's in RE rather than in R. You're missing the point. Keep thinking. – Yuval Filmus May 25 '15 at 13:42
I actually figured it out and thought I removed my comment. Thank you for responding though :) – Elimination May 25 '15 at 14:09