Undecidable language problems.

Question

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.

Answer 1

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.

Answer 2

Here are some hints:

1. If $L$ is undecidable, then adding or removing a finite number of words from $L$ doesn't change this.

2. 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.