# Must reductions be injective?

From Sipser,

Language A is mapping reducible to language B, written $A \leq_m B$, if there is a computable function $f : \Sigma^* \rightarrow \Sigma^*$, where for every $w$, $w ∈ A \Leftrightarrow f(w) \in B$. The function $f$ is called the reduction from A to B.

A function is injective if every element in the co-domain is mapped to by at most one element of the domain.

I'm confused on how $w \notin A$ are handled. It seems that for $w \in A$ every element must map to a unique $b \in B$. Because $w \in A \Leftarrow f(w) \in B$.

New question then, is there any use to having an injective reduction? I've noticed that many proofs of NP-hardness seem to have reductions that are injective (at least on $w \in A$). If reductions are not injective ~~ Why don't we simply define our reduction function $R$ as follows, check if $w \in A$, If $w \in A$ then map to a constant $b \in B$. Else, map to a constant $c \notin B$?

• There's no need for the mapping function to be injective. In fact, it's allowable for all $w\in A$ to map to a single element in $B$ and all of $\overline{A}$ to map to a single element in $\overline{B}$. [For example, this is part of the usual proof that every decidable language (except the trivial ones) is mapping reducible to any other.] Apr 27 '17 at 17:00
• Take the definition literally.
– Raphael
Apr 27 '17 at 18:14

The function $f$ does not need to be injective. It would be fine to map every $w \in A$ to the same element $w' \in B$ (and to map every $w \in \Sigma^* \setminus A$ to the same $w'' \in \Sigma^* \setminus B$). In fact, for every decidable language $A$, we have $A \leq_m B$ for every $B$ such that $B \neq \Sigma^*$ and $B \neq \emptyset$.

• Heh. Got in a few seconds before you. +1 anyway Apr 27 '17 at 17:02
• @RickDecker New question then, is there any use to having an injective reduction? I've noticed that many proofs of NP-hardness seem to have reductions that are injective (at least for $w \in A$). If reductions are not injective ~~ Why don't we simply define our reduction function R as follows, check if $w \in A$, If $w \in A$ then map to a constant $b \in B$. Else, map to a constant $c \notin B$? Apr 27 '17 at 17:21
• The reason you can't do that in the context of NP-hardness proofs is that we have the additional constraint that $f$ is computable in polynomial time. If $A$ is NP-hard you can't check $w \in A$ in poly. time unless P = NP. Apr 27 '17 at 17:27