Can a RE language be reduced to a non-RE language?

Question

In our lecture notes about many-one reduction we showed that the following statements hold: $$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$ $$(I)\space L' \in RE \implies L\in RE$$ $$(II)\space L \notin RE \implies L'\notin RE$$

Now I was wondering if this would also be true if you'd reverse these statements i.e. $$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$ $$(I)\space L \in RE \implies L'\in RE$$ $$(II)\space L' \notin RE \implies L\notin RE$$

Answer 1

First, note that if $p$ and $q$ are any two statements, the implication $p\implies q$ is logically equivalent to $(\lnot q)\implies(\lnot p)$. This equivalence is known as "taking the contrapositive".

Because of this, your statements $(I)$ and $(II)$ are equivalent. That is, the first two properties you mention are equivalent (and they follow from $L \leq_m L'$). The second two properties are also equivalent. Your question then becomes:

$(I)$ If $L \leq_m L'$ and $L \in RE$, can we conclude $L' \not\in RE$ ?

In general, no, we can not conclude that.

For instance, take $L=\{0\}$. This is a decidable language (we can test the input string against $0$, and accept iff they are equal), so it is also a $RE$ language.

Now, note that we can many-one reduce $L$ to absolutely any set $L'$ except the empty set and the full set ($\Sigma^*$). This includes non-$RE$ sets like the complement of the halting problem.

Indeed, to find a reduction, take any word $w\in L'$ and any other word $x\notin L'$. Then, the reduction function behaves as follows: it tests its input, if it is equal to $0$, then it returns $w$, otherwise it return $x$.

By construction, this is a reduction, so $L \leq_m L'$, even if $L\in RE$ and $L'\notin RE$.

Answer 2

The first statement:

$$(I)\space L' \in RE \implies L\in RE$$

says if L' is an element of RE, then L is an element of RE. This is true because L is contained in L'.

The second statement:

$$(II)\space L \notin RE \implies L'\notin RE$$

syas that if L is not an element of RE, then L' cannot be an element of RE. This is true because L is contained in L' and if the property does not hold for the smaller set, then it can't be true for the larger set it is contained in.

Your statement I:

$$(I)\space L \in RE \implies L'\in RE$$

says that if the smaller set is in RE, then the larger set is also in RE. That does not need to be true. There can be elements of the larger set for which the propety does not hold.

Your second statement is true, though:

$$(II)\space L' \notin RE \implies L\notin RE$$

and says that if the larger set is not in RE, then the smaller set cannot be in RE.