HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can the following conditions hold all together?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#69541, answer score: 6

Revisions (0)

No revisions yet.