2
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Why do you doubt your reasoning? $\endgroup$ – Raphael♦ Jan 9 '14 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 '14 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 '14 at 17:12
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '14 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 '14 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 '14 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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