Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

Question

I tried to prove by contradiction.

$L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. $$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\}$$ $$L_{2}=\emptyset$$ then, $$\overline L_{1}={HALT_{TM}}=\big\{ \langle M, w \rangle \mid M\text{ is TM and }M\text{ halts on input }w \big\}$$ $$\overline L_{2}=\Sigma^{*}$$ The intersection, $\overline{L_{1}}\cap \overline{L_{2}}$ is $\overline L_{1}={HALT_{TM}}$ is decidable and this is the contradiction.

Is it true?

Thanks.

Answer 1

Unfortunately your proof is not correct. The claim you want to prove or disprove is:

The union of any undecidable language and any finite language is undecidable.

To do a proof by contradiction, you need to take the opposite:

The union of some undecidable language and some finite language is decidable.

Note that the "any" (universal quantifier) turns into "some" (existential quantifier) when you apply the negation.

You showed that a contradiction follows from:

The union of any undecidable language and any finite language is decidable.

But unfortunately, that only proves:

The union of some undecidable language and some finite language is undecidable.

In other words, you can't just pick specific languages and show that their union is decidable: you need to show that your proof will work for any arbitrary $L_1$ and $L_2$ fitting the requirements.

I would suggest that you instead start with an arbitrary undecidable $L_1$ and finite $L_2$ and, from there, show that $L_1 \cup L_2$ is undecidable. Here's a hint to get you started: is $L_1 \setminus L_2$ decidable or not?

Answer 2

I start with $L_{1} \cup L_{2}$ is decidable.

Decidable languages are closed under difference. So, $(L_{1} \cup L_{2}) \setminus L_{2}$ must be decidable.

$(L_{1} \cup L_{2}) \setminus L_{2}= L_{1}$ but $L_{1}$ is undecidable.

Answer 3

By contradiction. Suppose that for all $L_1$ undecidable and $L_2$ finite $\overline{L_1} \cap \overline{L_2}$ is decidable. Pick $L_1$ any undecidable language. The language $L_2 = \varnothing$ is certainly finite, it's complement is $\overline{L_2} = \Sigma^*$, so that $\overline{L_1} \cap \overline{L_2} = \overline{L_1}$, and that one isn't decidable if $L_1$ isn't.