patternMinor
Can the following conditions hold all together?
Viewed 0 times
canthealltogetherfollowingholdconditions
Problem
Let $L_1, L_2$ be languages.
Can the following conditions hold:
-
$L_1,L_2\notin RE$.
-
$L_1\cap L_2\in R$
-
$L_1\cup L_2\in R$
-
$\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?
Can the following conditions hold:
-
$L_1,L_2\notin RE$.
-
$L_1\cap L_2\in R$
-
$L_1\cup L_2\in R$
-
$\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?
Solution
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.
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.
Context
StackExchange Computer Science Q#69541, answer score: 6
Revisions (0)
No revisions yet.