Is the reverse of a closed under operation maintainable? I'm looking at the following question from this handout:


  The class of decidable languages is closed under union


My question is, does this hold in reverse? Is there a phrase for this?
Basically, if $L_1 ∪ L_2$ is decidable would $L_1$ and $L_2$ be decidable as well?

I believe it does, by making one machine $M$ to emulate both on any given input string and have the following:

Save a copy of input somewhere (multitape)
Run M1
    If it accepts, accept
Reset the tape using copy
Run M2
    If it accepts, accept
Both machines have rejected, so reject


Does this work? If so, would this also apply in the case of intersection as well?
No, if $L_1\cup L_2$ is decidable $L_1$ and $L_2$ are not necessarily decidable.

Here's an example.

$$\begin{align} 
L_1 &amp;= \text{any language that is not decidable.}\\
L_2 &amp;= \Sigma^*\setminus L_1.
\end{align}$$
$L_1\cup L_2$ is $\Sigma^*$, which is decidable. However, $L_1$ is not decidable. In fact, $L_2$ is not decidable, either.



The proof given in the preformatted block of the question is a proof for the original proposition, "if $L_1$ and $L_2$ are decidable,  then $L_1\cup L_2$ is decidable". It is not a proof for its converse proposition.

To prove its converse proposition, all you can assume is a Turing machines that decides $L_1\cup L_2$. There is no way that you can construct a Turing machine that can decide $L_1$ from that machine.



Intuitively, one condition cannot imply two other conditions. That is, "$L_1 \cup L_2$ is decidable" cannot imply both "$L_1$ is decidable" and "$L_2$ is decidable"

Here are a few related exercises.

Exercise 1. Does $L_1 \cup L_2$ is regular imply $L_1$ is regular and $L_2$ is regular?

Exercise 2. Does $L_1 \cup L_2$ is context-free imply $L_1$ is context-free and $L_2$ is context-free?

Exercise 3. Does $L_1 \cup L_2$ is recursively enumerable imply $L_1$ is recursively enumerable and $L_2$ is recursively enumerable?

Exercise 4. Raise a question similar to the above question.

Exercise 5. If you know that $L_1\cup L_2$ and $L_1$ are both decidable, does that imply $L_2$ is decidable?





The case with intersection is the same. Please check question if $L_1$ and $L_2$ are languages over the same alphabet and $L_1\cup L_2$ is context free, at least one of them must be context free, its answer and its exercises.