0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Nov 5 '14 at 20:44
  • $\begingroup$ Ahh so I just need to find an undecidable language that is a subset of another decidable language. Thanks! $\endgroup$ – Jeremy burgess Nov 5 '14 at 20:57
  • $\begingroup$ Please don't delete the function after it has been answered. Other users might be interested in it as well. $\endgroup$ – Yuval Filmus Nov 5 '14 at 21:01
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.