Are there two languages $L_1,L_2 \notin RE$ such that $L_1 \nleq L_2$ and $L_2 \nleq L_1$?

Question

My Solution

Yes there are. Take $L_\Sigma *$ and $L^c_\Sigma *$. Both are not in $RE$.

(Here comes the messy part)

Lets assume for contradiction that there is a reduction $L_\Sigma * \leq L^c_\Sigma *$ . Then there is a computable function $f: \Sigma^* \rightarrow \Sigma^*$, that can tell for every TM $M$ if $L(M) = \Sigma^*$ or $L(M) \neq \Sigma^*$ .Then we can solve the halting problem, which is a contradiction.

Question

I think that the statement in the headline is True, however, I wasn't convinced by my own explanation.

Does anyone have a better explanation? let alone proof?

Edit:

$\Sigma$ is the alphabeit.

$L_\Sigma ^* $ is the set of all turing machines that their language is $\Sigma ^*$

$A \leq B$ is a reduction from A to B.

Answer 1

Here is the answer:

The number of languages that uphold the $\leq$ reduction relation is bounded by the number of computable reduction functions.

The number of computable reduction functions is bounded by the number of Turing machines.

The number of Turing machines is countable, $א_0$.

Thus, there is only a countable set of languages that uphold the $\leq$ reduction relation.

Since the cardinality of $RE$ is as of the continuum, there must be at least two languages $L_1, L_2 \notin RE$ such that $L_1 \nleq L_2$ and $L_2 \nleq L_1$.