Why isn't it enough to enforce $w \in A \Rightarrow f(w) \in B$ before allowing a reduction from A to B?

Question

From my textbook, I can see that

A language A is mapping reducible to language B if there is a computable function such that for every $w$, $w \in A \Leftrightarrow f(w) \in B$.

Now, what I fail to grasp is on why it isn't just enough to enforce that for every $w$, $w \in A \Rightarrow f(w) \in B$. Intuitively, it seems that this would be enough. With this, we know we can map every element of $A$ onto $B$. Shouldn't this be enough? Why is it not?

I guess the $\Leftarrow$ part must have something to do with not allowing elements outside of $A$ to be mapped onto $B$. Is that it? What would be the problem that would originate?

Answer 1

Let's take $B=\{0\}$. Now define a function $f(w)=0$. This is a reduction satisfying your condition, but it's useless since it can't differentiate elements of $A$ from nonelements of $A$, which is the whole point of reductions.

In reductions we try to move from the problem of deciding if something is in A, to deciding if something is in B. With a reduction we are able to say "if it's in B, the original was in A; and if it is not in B, the original was not in A". Your type of reduction enables us to say only the second statement, not the first.

Answer 2

Gadi A has the right answer, but I want to point out that things go spectacularly wrong without the "if and only if". Suppose that $B$ has any element $b$ and let $f_b$ be the function such that $f_b(n) = b$ for all $n$. Then $f_b$ would be a reduction in your weaker sense from any set $A$ to the set $B$. So, in particular, any two nonempty sets would be reducible to each other in the weaker form of "reducibility".

Answer 3

The word problem for groups was shown unsolvable by (computably) associating to each Turing machine $M$ a finitely presented group $G_{M}$ such that $M$ halts on input word $w$ if and only if $w$ is equivalent to the identity in $G_{M}$. More precisely, let $A_{\text{TM}}$ be the accepting language for Turing machines (also known as the halting set) and let $\text{Ident}$ be the language of words $\langle{G,w}\rangle$ such that $w$ is equivalent to the identity in the group $G$. A computable function $f: A_{\text{TM}} \to \text{Ident}$ was constructed so that $\langle{M,w}\rangle \in A_{\text{TM}}$ $\Longleftrightarrow$ $f(\langle{M, w}\rangle) \in \text{Ident}$. Thus to decide if machine $M$ accepts input $w$ (i.e. if $\langle{M,w}\rangle \in A_{\text{TM}}$), it suffices to compute $f(\langle{M,w}\rangle)$ and decide if that is in $\text{Ident}$. But $A_{\text{TM}}$ is undecidable, so $\text{Ident}$ must also be.

However, this argument wouldn't work if we only had $\langle{M,w}\rangle \in A_{\text{TM}}$ $\Longrightarrow$ $f(\langle{M, w}\rangle) \in \text{Ident}$, because then, as Gadi and Carl pointed out, even if we could decide if $f(\langle{M,w}\rangle) \in \text{Ident}$, it would give us no information about whether or not $\langle{M,w}\rangle \in A_{\text{TM}}$ because in the case where $f(\langle{M,w}\rangle) \in \text{Ident}$ holds, we could still have $\langle{M,w}\rangle \notin A_{\text{TM}}$.

It is worth noting that, conversely, if we only had $\langle{M,w}\rangle \in A_{\text{TM}}$ $\Longleftarrow$ $f(\langle{M, w}\rangle) = \langle{G, w}\rangle \in \text{Ident}$, the case where $f(\langle{M,w}\rangle) \notin \text{Ident}$ gives no information.