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

Question

For $L_1,L_2 \in RE - R $ , I want to prove or disprove if the following can occur:

What I did:

I think any two disjoint languages suffice, since the empty set is decidable.
I think something along the lines of a language and its complement but I'm struggling to think of an example.
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. — Joey Eremondi, Commented Apr 15, 2014 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, Commented Apr 15, 2014 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. — John Kemeny, Commented Apr 15, 2014 at 21:01

David Richerby · Accepted Answer · 2014-04-15 21:19:17Z

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

Yuval Filmus · Accepted Answer · 2014-04-15 21:11:47Z

2

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

answered Apr 15, 2014 at 21:11

Yuval Filmus

279k27 gold badges316 silver badges512 bronze badges

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

Add a comment |

2 Answers 2