[Solved]: Reduction between $\Sigma^*$ and $\emptyset$

Problem Detail: 

Throughout the subject of reductions, I was wondering:

If we take $L_1 = \Sigma^* $ and $L_2 = \emptyset$, is $L_1 \leq L_2$? is $L_2 \leq L_1$?

What I mean is, Is there some sort of reduction between any of the two with the other one?

I tried this:

Let us try $L_2 \leq L_1$, we need to show that such a reduction exists. Suppose f(x) is that reduction function in which $x \in L_2$ iff $f(x) \in L_1$.

But there aren't any $x$ in $\emptyset = L_2$, does that show that such a reduction doesn't exist?

Asked By : TheNotMe

Answered By : Raphael

Let $f : \Sigma^* \to \Sigma^*$ any total function. Then, the statement $x \in L_2$ is always false since $L_2 = \emptyset$, and conversely $f(x) \in L_1$ is always true since $L_1 = \Sigma^*$. So, clearly, the equivalence

$\qquad\displaystyle x \in L_2 \iff f(x) \in L_1$

is false for $f$ and all $x \in \Sigma^*$ (it would have been sufficient to find one example-$x$); in fact,

$\qquad\displaystyle x \in L_2 \iff f(x) \notin L_1$

holds for all $x$. So $f$ is not a reduction function.

Since we picked $f$ arbitrarily, there can be no reduction from $L_2$ to $L_1$. A similar argument works for the other direction.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19599