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:
- $emptyset leq B$ is equivalent to $$exists f : Sigma^{*} to Sigma^{*} . forall x in Sigma^{*} . f(x) notin B,$$ which is equivalent to $B neq Sigma^{*}$.
- $A leq emptyset$ is equivalent to $$exists f : Sigma^{*} to Sigma^{*} . forall x in Sigma^{*} . x notin 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
