Let $L_1, L_2$ be languages.

Can the following conditions hold:

  1. $L_1,L_2\notin RE$.

  2. $L_1\cap L_2\in R$

  3. $L_1\cup L_2\in R$

  4. $\overline{L}_1, \overline{L}_2 \in RE / R$

I believe the above cannot hold at the same time. I thought since $L_1\cap L_2\in R$ and $L_1\cup L_2\in R$ then $\overline{L}_1\cup \overline{L}_2\in R$ and $\overline{L}_1\cap \overline{L}_2\in R$. Then I know that $L_2 \ L_1 = L_2 \cap \overline{L_1}$. And now I want to somehow use condition 4 to reach a contradiction, but I don't see how...

Or perhaps I'm wrong and they can hold together?


Conditions $2,3,4$ imply $L_1 \in RE$, contradicting $1$.

Here's how to semi-decide $L_1$. Take a candidate $x$. If $x \in L_1 \cap L_2$ (decidable by $2$), accept. If $x \notin L_1 \cup L_2$ (decidable by $3$), diverge (we know $x \notin L_1$ for sure).

We now know that $$x \in (L_1\setminus L_2) \cup (L_2\setminus L_1) \qquad (*)$$

Exploiting $4$, we run semi-deciders for $\overline{L_1}, \overline{L_2}$ on $x$ in parallel. By $(*)$, (exactly) one of these must eventually halt.

If the former halts, we infer $x \notin L_1$, so we diverge. If the second one halts, we infer $x \notin L_2$, and by $(*)$ we obtain $x\in L_1$, so we accept.


I voted for the answer by chi, as it gives a nice explanation how the algorithm is stringed together.

At the same time I wondered whether there would be an "abstract" solution where one uses basic facts about recursive and recursively enumerable languages. (If you reconsider chi's construction after reading my answer you will recognize the ingredients.)

Now, if I am not mistaken [but we will not use the fourth fact, thanks to an idea of chi in the comments],

  • $R$ is closed under boolean operations,
  • $RE$ is closed under intersection and union,
  • $R\subset RE$, and
  • if both $L$ and $\overline L$ are in $RE$, then $L$ is in $R$.

Note that, by 2,3 the intersection $L_1\cap L_2$ and the union $L_1 \cup L_2$ are in $R$, and hence in $RE$.

Then by 4, $L_1 = ((L_1\cup L_2) \cap \overline{L_2}) \cup (L_1\cap L_2)$ is in $RE$.

Now $L_1$ is in $RE$, contradicting 1.

  • $\begingroup$ This is better than my solution. I actually tried something like this but gave up too soon. By the way, you don't even need the last result you mention. Since 1 states $L_1 \notin RE$, we already contradict that before going one step further proving $L_1 \in R$ in the last line. $\endgroup$
    – chi
    Feb 1 '17 at 19:26
  • $\begingroup$ Thank you @chi for your kind words. But it must be stressed that also I was running in circles until I saw your solution. You are right. I will shortcut the argument ... and loose $L, \overline L$ result. $\endgroup$ Feb 2 '17 at 13:08

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.