Let $L_1$ and $L_2$ be two undecidable languages.
1) Is it possible that $L_1 – L_2$ is regular and $L_1 – L_2 \neq \emptyset$ ?
Well I know that if I let $L_1 = L_2$ then $L_1 – L_2 = \emptyset$ which is obviously regular. In the case of this question however, I cannot set $L_1 = L_2$ if the outcome is an empty set, which makes me wonder what would $L_1 – L_2$ actually look like if they were not equal to each other.
2) Is it possible that $L_1 \cup L_2$ is decidable and $L_1 \neq \neg L_2$ ?
This one is also tricky, since the obvious solution here would be to let $L_1 = \neg L_2 $
Does anyone here have an idea as to how to finish my solutions here? I need to prove my solutions in both cases.
Here are some hints:
If $L$ is undecidable, then adding or removing a finite number of words from $L$ doesn’t change this.
If $L$ is a language over $\{0,1\}$ then we can also think of it as a language over $\{0,1,2\}$.
Of course, other solutions are possible.
Sure, both are possible. For (1), take $K_1, K_2$ to be disjoint languages with $K_1$ regular and $K_2$ undecidable. Then $L_1=K_1\cup K_2$, $L_2=K_2$ works.
For (2), the answer is also yes: take $L_1=\neg L_2\cup p$ for any single word $p$.
In general, Boolean operations can “hide” lots of information.