[Solved]: Can $\emptyset$ be reducible to any other language?

Problem Detail: 

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?

Asked By : TheNotMe

Answered By : Andrej Bauer

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 \eq \emptyset$.

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19628