# Reduction of RE and Rec languages

Suppose $$L_1$$ is reduces to $$L_2$$ in polynomial time, $$L_1\leq_p^\mathsf{}L_2.$$ we know that if $$L_2$$ is RE then $$L_1$$ is also RE and $$L_2$$ is REC then $$L_1$$ is also REC.

And also I know that if $$L_1$$ is REC then $$L_2$$ is RE and REC is false. Because by taking counterexample $$L_1=\emptyset$$ and $$L_2=$$halting problem. So see from this example and case fails to prove above postulation.

My first question is that or case could be true. I mean if $$L_1$$ is REC then $$L_2$$ is RE or REC$$-$$could it be true?

My second question "if if $$L_1$$ is RE then $$L_2$$ is also RE" $$-$$ could it be true? I don't want any details proof. I want counterexample for true and false case.

• – D.W.
Nov 8 at 4:02

If $$L_1$$ is recursive and $$L_1 \le_p L_2$$, they it is possible that $$L_2$$ is not recursively enumerable (and hence not recursive).
For example pick $$L_1 = \emptyset$$ and $$L_2$$ as the set of (a suitable encoding of) all Turing machines that do not halt on empty input. Clearly $$L_2$$ is not recursively enumerable. A possible Karp reduction from $$L_1$$ to $$L_2$$ is the constant function that returns (the encoding of) a Turing machine that immediately halts.
If $$L_1$$ is recursively enumerable and $$L_1 \le_p L_2$$ then it might be the case that $$L_2$$ is also recursively enumerable. For example pick $$L_1 = L_2 = \emptyset$$, a Karp reduction from $$L_1$$ to $$L_2$$ is the identity function. Notice that, in this example, $$L_1$$ is also recursive.
• How from L1 to L2 is the constant function,L1 isn't contain any string. You mean constant function is from element $\phi$ in $L_1$ to $L_2$ ,set of (a suitable encoding of) all Turing machines that do not halt on empty input? Am I right? Oct 17 at 14:24
• I never said that the function is from $L_1$ to $L_2$. The function is from $\Sigma^*$ to $\Sigma^*$, where $\Sigma$ is the alphabet of both $L_1$ and $L_2$. I said that the function is a Karp reduction from $L_1$ to $L_2$. A Karp-reduction from $L_1$ to $L_2$ is a polynomial-time computable total function $f : \Sigma^* \to \Sigma^*$ such that $x \in L_1 \iff f(x) \in L_2$. See the definition of Many-one reduction and of Karp reduction. Oct 17 at 14:36
• No. The domain of the function is not $L_1$ and the codomain of the function is not $L_2$. In fact, the image of the function (a set with single element) is disjoint from $L_2$. Oct 17 at 14:40