Proving a language is not recognizable

Solution 1:

Your proof is essentially correct, but a bit more convoluted than necessary: you don't need to distinguish between cases, and you don't need to run $R$ and $Q$ in parallel (if you use a decider for $L_2$). The following argument by contraposition suffices.

Suppose that $L_1$ is recognisable by some recogniser $Q$. By assumption $L_2$ is decidable by some decider $M$. We'll put these machines together to make a machine $T$ that recognises $L_1\cup L_2$. First, on input $w$, the machine $T$ runs $M$ on $w$. If $M$ accepts, then $T$ stops and accepts; if $M$ rejects, then $T$ runs $R$ on $w$. If $R$ accepts, then $T$ stops and accepts; if $R$ rejects, then $T$ stops and rejects. Note that

• on input $w\in L_2$, the subprocedure $M$ of $T$ will accept, so $T$ will accept $w$;
• on input $w\in L_1\setminus L_2$, $M$ will reject but the subprocedure $R$ will accept, so $T$ will accept $w$;
• on input $w\notin L_1\cup L_2$, $M$ will reject and $R$ will reject or loop, so $T$ will reject $w$ or loop.

Thus, $T$ is a recogniser for the set $L_1\cup L_2=L$, contradictory to the assumption that $L$ is not recognisable.