Skip to main content
2 of 5
added 113 characters in body; edited tags; edited title
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

If $L_1 \subseteq L_2$, is the identity a many-one reduction from $L_1$ to $L_2$?

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?