# Reduction between $\Sigma^*$ and $\emptyset$

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?

• Why do you doubt your reasoning? – Raphael Jan 9 '14 at 16:55
• because I merely said that "there aren't any $x$'s we can take", that isn't a mathematical proof. Also, for the other direction, if I take any $y$ in $L_1$, it surely won't be in the $\emptyset$, unless it is the $\emptyset$, but yet again, the $\emptyset$ is not $\in \emptyset$. Does that mean that $L_1 \leq L_2$ but $L_2 \nleq L_1$? – TheNotMe Jan 9 '14 at 16:58
• I think you got a) the right intuition and b) the right argument, which is cool. I've posted an answer which writes it down in order; you make your argument a proof by starting with an arbitrary $f$ and showing that it is not a reduction. – Raphael Jan 9 '14 at 17:12

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.

• Raphael, there is a paper making a claim that the empty set is reducible to any other language. Page 43, paragraph one: citeseerx.ist.psu.edu/viewdoc/… – TheNotMe Jan 10 '14 at 14:31
• @TheNotMe It's not clear to me whether they use the same notion of reduction. In our setting, the empty set can certainly be reduced to any set but $\Sigma^*$. Is there a mistake in my reasoning? – Raphael Jan 10 '14 at 15:02
• I can't see a mistake in my/your reasoning, but I thought I should show you that... – TheNotMe Jan 10 '14 at 19:41