# Is the identity function a many-one reduction from a language to super-set?

I need help with a question.

Prove or disprove the following claim:

Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be two languages such that $L_1 \subseteq L_2$. Then $f$ is a many-to-one reduction from $L_1$ to $L_2$. In particular, if $L_2$ is decidable, $L_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time with the justification. Can anyone help me out?

• In order to disprove this, it is enough to disprove the conclusion that if $L_2$ is decidable then so is $L_1$. Can you think of a counterexample for the latter claim? Nov 5, 2014 at 20:44
• Ahh so I just need to find an undecidable language that is a subset of another decidable language. Thanks! Nov 5, 2014 at 20:57
• Please don't delete the function after it has been answered. Other users might be interested in it as well. Nov 5, 2014 at 21:01

In order to disprove this, it is enough to disprove the conclusion that if $L_2$ is decidable then so is $L_1$. Can you think of a counterexample for the latter claim?
Another option is to directly disprove the fact. For $f$ to be a many-one reduction from $L_1$ to $L_2$ would mean that $x \in L_1$ iff $x \in L_2$, that is, $L_1 = L_2$. So to disprove this you only need to find two languages $L_1,L_2$ such that $L_1 \subsetneq L_2$.