2
$\begingroup$

For $L_1,L_2 \in RE - R $ , I want to prove or 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$

What I did:

  1. I think any two disjoint languages suffice, since the empty set is decidable.

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

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

Any help/further insight would be welcomed!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jmite Apr 15 '14 at 20:37
  • $\begingroup$ @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. $\endgroup$ – David Richerby Apr 15 '14 at 20:41
  • $\begingroup$ For your second point, recall that if a language and its complement both are recursively enumerable, then they are recursive as well. $\endgroup$ – Pål GD Apr 15 '14 at 21:01
4
$\begingroup$
  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$.

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.