# Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such that $M_1$ doesn't halt for, and so the machine $M$ which runs $M_1, M_2$ in parallel, may not halt.

• If $w \in L_1$, then $M_1$ must always halt for $w$ – Erbureth says Reinstate Monica May 23 '15 at 13:34
• I've corrected it. was sort of a typo.. – Elimination May 23 '15 at 13:53

Hint: Let $L$ be any language in $\mathsf{RE} - \mathsf{R}$, and consider $$L_1 = 0\Sigma^* \cup 1L, \quad L_2 = 1\Sigma^* \cup 0L.$$

• But $L_1$ mustn't be decidable since it's in $RE-R$. Maybe I'm missing your intention. – Elimination May 23 '15 at 14:12
• No, I think I misinterpreted your $R$ to mean regular rather than recursive. – Yuval Filmus May 23 '15 at 14:18
• I'm looking at the intersection of $L_1, L_2$ but don't see why $L_1 \cap L_2 \in R$ – Elimination May 23 '15 at 14:50
• What has intersection got to do anything with this? You asked about the union $L_1 \cup L_2$. – Andrej Bauer May 23 '15 at 16:16
• You can also give a similar example for intersection: $0L$ and $1L$. – Yuval Filmus May 23 '15 at 20:56