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

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$$

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$$.

• I think you missed an apostrophe when you phrased my actual question, but I still understood your answer, thanks ! – Yamahari Dec 6 '18 at 16:02
• @Yamahari Indeed! Should be fixed now. – chi Dec 6 '18 at 16:14

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.

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