# Can $\emptyset$ be reducible to any other language? [duplicate]

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?

## marked as duplicate by D.W.♦, Luke Mathieson, vonbrand, András Salamon, KavehFeb 7 '14 at 6:14

• Didn't you get the answer here already? – Raphael Jan 10 '14 at 15:38
• Since that research came up, no. – TheNotMe Jan 10 '14 at 19:41
• 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. – 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^{*}$$.

• Extra question on my hands here: What about $\Sigma^*$? is it reducible to any other set except $\Sigma^*?$ – TheNotMe Jan 10 '14 at 19:52
• @TheNotMe The last sentence of my answer answers precisely that question! – David Richerby Jan 10 '14 at 20:54
• So $\Sigma^*$ is only reducible to $\Sigma^*$ yes? – 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$.