Reducibility

Question

If L1 is reducible to L2 and L1 is recursively enumerable then what can we say about L2?

Answer 1

Given that L1 $\leqslant$ L2 (L1 Reduciable L2)

It means L2 is atleast harder problem as L1.

And Here Given that L1 is Recursive Enumerable.

So, L2 Must be either Recursive Enumerable Language or Non-Recursive Enumerable Language.

Answer 2

L1 reducible to L2

It refers

(L2 is decidable) ==> L1 is decidable

Again

L1 is Undecidable then L2 is Undecidable(Contrapositive form)

Again

L2 is REL ==>L1 is REL

again

L1 is non REL ==> L2 is non REL

Answer 3

we cant say anything about L2.

Comments

L2 cant always be recursive.
if L1 is reducible to L2. and if L2 is recursive then L1 is recursive which means L1 is recursively ennumerable.
this is a case when L2 can be recursive when L1 is recursively ennumerable.
but we cant say that L2 can be always recursive

---

So if L1 is recursively enumerable but not recursive then L2 wii be RE only.

---

i think some times L2 may not even be RE too.
bcoz L1 reducible to L2 , L1 is RE, it means L2 cant be easier than RE.
so it can be RE or not even RE