Polynomial time reducibility

Question

$L_1$ and $L_2$ are two languages defined on the alphabet $\sum$. $L_1$ is reducible to $L_2$ in polynomial time. Which of the following cannot be true?

• $L_1 \in P$ and $L_2$ is finite
• $L_1 \in NP$ and $L_2 \in P$
• $L_1$ is undecidable and $L_2$ is decidable
• $L_1$ is recursively enumerable and $L_2$ is recursive

My reasoning is as follow,

If $A \le_p B$, and $B \in P$, then $A$ can be reduced to $B$ in polynomial time and solved in polynomial time making $A \in P$. Thus I initially figured the 2nd choice as false and thus the right answer.

However using the same argument on mapping reducibility, the 3rd choice seems to be false as well. The fourth choice is the same as the third one.

I was unsuccessful in reasoning anything about the 1st choice.

To put my above arguments in context, I am learning about theory of computation and have just about skimmed the surface of computability and complexity theory. Helo me out.

Answer 1

Three of the options use the same trick: if $C1,C2$ are two classes of languages and $C1 \subseteq C2$; then $L1 \in C2$ doesn't imply that $L1 \notin C1$.

The only choice that cannot be made true is 3: if there is a polynomial time reduction from an undecidable language $L_1$ to a decidable language $L_2$ then $L_1$ becomes decidable, too (just build a Turing Machine that computes the reduction and then solve the problem using the decider for $L_2$) and this is a contraddiction.