if $L \notin RE$ and $L' \notin RE$ then $L \cup L' \notin RE$

Question

Question: if $L \notin RE$ and $L' \notin RE$ then $L \cup L' \notin RE$

I need to prove or give a counter-example.

First of all, I want to understand if I'm correct:

(1) If $L \notin RE$, can I conclude that $L \in co-RE$? Because from my understanding if $L \notin RE$, it means for me that for every input $x$ that is not in $L$ the machine says no. Otherwise, it doesn't say no. Which is exactly like on $co-RE$.

If I'm wrong up there,

(2) can I conclude that if $L \notin RE$ then $L^{c} \in RE$ ?

Here is ' my proof' if $L \notin RE$ then $L^c \notin co-RE$ which is $L^c \in (co-RE)^c$ which is $L^c \in RE$

If yes on (2), then I need to prove that if $L^c \in RE$ and $L'^c \in RE$ then $(L \cup L')^c \in RE$ which is $ L^c \cap L'^c \in RE $ - which is true because they've closure in $\cap$.

Now, if I'm correct at (1) or at (2) then we know that there's closure for Union for languages that are in $RE$ or in $co-RE$, so it's true by their definition.

Would love to know if I'm correct on (1) or on (2).

Here's a list of questions I'm struggling with, thus I can't answer the question efficiently:

1. if $L \notin RE$ can I conclude $L \in co-RE$?

2. What's the definition of $L \notin RE$?

3. if $L \notin RE$ then $L^c \notin co-RE$?

4. if $L \notin RE$ then $L^c \notin RE$?

Answer 1

Let $H$ denote the halt set in a reasonable form. Similarly let's denote $L'=\mathbb{N}-L$. Also, you can search for "join" on this page: https://en.wikipedia.org/wiki/Turing_degree.

Question: if $L_1 \notin RE$ and $L_2 \notin RE$ then $L_1 \cup L_2 \notin RE$

This is incorrect. In particular, take $L_1=H \oplus H'$ and $L_2=H' \oplus H$. Neither $L_1$ or $L_2$ are r.e. However, we have $L_1 \cup L_2 =\mathbb{N}$. Of course we have $\mathbb{N} \in RE$.

(1) $L \notin RE$ implies $L \in coRE$

This is incorrect. Define $X=RE \cup coRE$. Now if you take any set $L$ such that $L \notin X$, then clearly $L \notin RE$. However, $L \notin coRE$ would also be true for obvious reasons.

(2) $L \notin RE$ implies $L' \in RE$

This is also incorrect. One way is to define $L=H \oplus H'$. Then $L \notin RE$. But we then have $L'=H' \oplus H$ (and $L' \notin RE$ either).

A second way is to define a set $L$ such that $H \leq_T L$ but $L \nleq_T H$. In that case also $L \notin RE$ (since $L \in RE$ that would imply $L \leq_T H$). But we also have $L' \notin RE$. That's true because if by contradiction we assume $L' \in RE$ then we have $L \in coRE$. However, $L \in coRE$ that would imply $L \leq_T H$.

Answer 2

I assume $L$ is a set of natural numbers, $L'$ is the Turing jump of $L$, also a set of natural numbers, and $L^c$ is its complement. Then if $L$ and $L'$ are both non-RE, $L \cup L'$ can be RE, but typically is not.

Hint for an example of yes: Try defining an infinite set $A$ such that $A$ is contained in $M'$ for every language $M$. Then as long as $L^c$ is contained in $A$, you always have $L \cup L' = \mathbb{N}$, which is RE.

Hint for example of no: Try to get an infinite computable set $B$ that is contained in $M^{\prime c}$ for every language $M$. Then as long as $L$ is contained in $B$, the union $L \cup L'$ is one-one equivalent to the join $L \oplus L'$, and in particular is RE only if $L$ is RE.