While solving some question, that involved the empty set $\emptyset$, I was really wondering, is $\emptyset$ reducible to any other language, i.e., $\emptyset \leq A$ such that $A$ is a language over a given alphabet $\Sigma^*$?

I mean, one can never take $x \in \emptyset$, right? or am I missing anything?

Maybe $\emptyset \leq \emptyset$? because if I take a reduction $f$ such that $x \in \emptyset \Leftrightarrow f(x) \in \emptyset$, this is always true, because $x \in \emptyset$ is never true and $f(x) \in \emptyset$ is also never true, so that function is a reduction function in the empty-concept, no?

  • 3
    $\begingroup$ Didn't you get the answer here already? $\endgroup$
    – Raphael
    Jan 10 '14 at 15:38
  • $\begingroup$ Since that research came up, no. $\endgroup$
    – TheNotMe
    Jan 10 '14 at 19:41
  • 1
    $\begingroup$ When you say "any", do you mean "there exists" or "for all"? Hint: try to avoid use of the word "any" as a quantifier, as its meaning is ambiguous. $\endgroup$
    – D.W.
    Jan 11 '14 at 6:44

Recall that: a (many-one) reduction from $A \subseteq \Sigma^{*}$ to $B \subseteq \Sigma^{*}$ is a map $f : \Sigma^{*} \to \Sigma^{*}$ such that $x \in A \iff f(x) \in B$ for all $x \in \Sigma^{*}$. We usually put extra conditions on $f$, such as polytime computable, but let us not dwell on that here. We write $A \leq B$ when there is such an $f$ and say that $A$ is reducible to $B$.

The statement $A \leq B$ may be written in logical notation as $$\exists f : \Sigma^{*} \to \Sigma^{*} . \forall x \in \Sigma^{*} . (x \in A \Leftrightarrow f(x) \in B).$$

It is a basic exercise in logic to figure out that:

  1. $\emptyset \leq B$ is equivalent to $$\exists f : \Sigma^{*} \to \Sigma^{*} . \forall x \in \Sigma^{*} . f(x) \not\in B,$$ which is equivalent to $B \neq \Sigma^{*}$.

  2. $A \leq \emptyset$ is equivalent to $$\exists f : \Sigma^{*} \to \Sigma^{*} . \forall x \in \Sigma^{*} . x \not\in A,$$ which is equivalent to $A = \emptyset$.

Thus, only the empty set is reducible to the empty set, while the empty set is reducible to every set, except $\Sigma^{*}$.

  • $\begingroup$ Extra question on my hands here: What about $\Sigma^*$? is it reducible to any other set except $\Sigma^*?$ $\endgroup$
    – TheNotMe
    Jan 10 '14 at 19:52
  • $\begingroup$ @TheNotMe The last sentence of my answer answers precisely that question! $\endgroup$ Jan 10 '14 at 20:54
  • $\begingroup$ So $\Sigma^*$ is only reducible to $\Sigma^*$ yes? $\endgroup$
    – TheNotMe
    Jan 10 '14 at 21:14

$\emptyset$ can be reduced to any other language $L$ except $\Sigma^*$.

Remember that a reduction from $L_1$ to $L_2$ has to map "yes" instances of $L_1$ to "yes" instances of $L_2$ and "no" instances of $L_1$ to "no" instances of $L_2$. Every input is a "no" instance of the language $\emptyset$ so, to reduce $\emptyset$ to any $L\neq \Sigma^*$, you just need to choose some word $w\notin L$ and your reduction maps everything to $w$. Obviously, for $L=\Sigma^*$, this doesn't work because there's no $w$ you could use.

Similarly, $\Sigma^*$ can be reduced to any other language except $\emptyset$.


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