Cheap and Secure Web Hosting Provider : See Now

[Solved]: Is the identity function a many-one reduction from a language to super-set?

, , No Comments
Problem Detail: 

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?

Asked By : Jeremy burgess

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback