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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Nov 5, 2014 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
    Commented Nov 5, 2014 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
    Commented Nov 5, 2014 at 21:01

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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