# mapping reductions from R to RE

Let $$L_1$$ be some language in $$R$$. Let $$L_2$$ be some language in $$RE$$. Is it necessarily that $$L_1 \leq_m L_2$$ ? I know that for non trivial $$L_1$$,$$L_1$$ in $$R$$ it is right to say that $$L_1 \leq_m L_2$$. But I can't prove the first case.

and another question: I am almost certain that the following is true, though I have not found any reference to it on the Internet: The identity function is a mapping reduction from $$\emptyset$$ to $$\emptyset$$.

• Unfold the definitions, you don't need the internet to tell if the identity function is a reduction from a language to itself. Think about what happens if $L_1$ or $L_2$ are trivial. – Ariel Jun 19 '20 at 9:53
• Have you read my question? I wrote that for non trivial – Ella Jun 19 '20 at 11:31
• Can you state precisely what restrictions, if any, you have on $L_1$ and $L_2$? – Steven Jun 19 '20 at 11:38
• I don't have any restrictions. When talking about reductions we say that $L_1\leq_mL_2$ means (in a way) that " $L_1$ is easier than $L_2$". I'm trying to figure out if there is a mapping reduction from any $L_1$ to any $L_2$ that is "harder". In the original question I refer to the private case, where the easier class is $R$ and the hardest one is $RE$ – Ella Jun 19 '20 at 11:43
• If you have no restrictions on $L_2$ then the claim is false. See my answer. – Steven Jun 19 '20 at 11:49

If $$L_2 \neq \Sigma^*$$ and $$L_2 \neq \emptyset$$ then $$L_1 \in R$$ and $$L_2 \in RE$$ implies $$L_1 \le_m L_2$$.

Let $$T$$ be a Turing machine that decides $$L_1$$. Let $$a,b \in \Sigma^*$$ such that $$a \in L_2$$ and $$b \not\in L_2$$. For $$x \in \Sigma^*$$, define $$\phi(x) = \begin{cases} a & \text{ if T(x) accepts }\\ b & \text{ if T(x) rejects } \end{cases}$$. It is easy to check that $$\phi$$ is a mapping reduction from $$L_1$$ to $$L_2$$.

If $$L_2 = \Sigma^*$$ then $$L_1 \in R$$ and $$L_2 \in RE$$ does not imply $$L_1 \le_m L_2$$.

This can be seen, e.g., by choosing $$L_1 = \emptyset$$.

If $$L_2 = \emptyset$$ then $$L_1 \in R$$ and $$L_2 \in RE$$ does not imply $$L_1 \le_m L_2$$.

This can be seen, e.g., by choosing $$L_1 = \Sigma^*$$.

• thank you very much! – Ella Jun 19 '20 at 12:18