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?

  • $\begingroup$ Why do you doubt your reasoning? $\endgroup$
    – Raphael
    Jan 9, 2014 at 16:55
  • $\begingroup$ 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$? $\endgroup$
    – TheNotMe
    Jan 9, 2014 at 16:58
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Jan 9, 2014 at 17:12

1 Answer 1


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.

  • $\begingroup$ 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/… $\endgroup$
    – TheNotMe
    Jan 10, 2014 at 14:31
  • $\begingroup$ @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? $\endgroup$
    – Raphael
    Jan 10, 2014 at 15:02
  • $\begingroup$ I can't see a mistake in my/your reasoning, but I thought I should show you that... $\endgroup$
    – TheNotMe
    Jan 10, 2014 at 19:41
  • $\begingroup$ So who's right? $\endgroup$ Jun 23, 2022 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.