Reduction and m-completeness

Question

I read in several textbooks on many-to-one reductions that $A \leq_m B$ if there exists a computable function $f$ such that $x \in A$ iff $f(x) \in B$. This means that $A = f^{-1}(B)$, or that $A$ is the pre-image of $B$.

But I don't understand why there there also exist sets $A'$ and $B'$ where $A' \leq_m B'$ but $B' \nleq_m A'$. Since there is already a computable function $f$ (from the definition) that maps elements in $A'$ with elements in $B'$, isn't it straightforward that there should be another computable 'pullback' function $f'$ that maps elements in $B'$ to elements in $A'$?

I think I am missing something here ....

Answer 1

isn't it straightforward that there should be another computable 'pullback' function

It's always dangerous to assert that some object "easily" exists without actually building it. If you try to actually define $\hat{f}$ (I'm writing this instead of your "$f'$," since apostrophes mean something incomputability theory) precisely in terms of $f$, you'll find that you can't, regardless of how plausible it seems.

Let's think about a particular example. Let $A=\{$even numbers$\}$, and $B$ be any noncomputable set. Without loss of generality, suppose $0\in B$ and $1\not\in B$. Now consider the function $$f(x)=x\,\,\mbox{mod }2.$$ Clearly $f$ is an $m$-reduction of $A$ to $B$: if $a\in A$, then $f(a)\in B$, and if $a\not\in A$, then $f(a)\not\in B$. But there's no way to reverse this: what do you think, e.g., $17$ should map to, in a putative $m$-reduction of $B$ to $A$?

---

The above example might seem to hinge on $f$ being non-injective. But this isn't the case: e.g. let $A$ be as above, and now take $B$ to be somenon computable set which contains all nonzero powers of $2$ and no nonzero powers of $3$. Now let $g$ be the function given by

• $g(x)=2^{x+1}$ if $x$ is even,

• $g(x)=3^{x+1}$ if $x$ is odd.

The function $g$ is injective, and an $m$-reduction of $A$ to $B$; but there's still no way to "reverse" it to get an $m$-reduction of $B$ to $A$ (e.g. where should $17$ go?).

---

So the (non)injectivity of the $m$-reduction $f$ is a red herring. Things change drastically, however, if $f$ is surjective. The following is true:

Suppose $f:\mathbb{N}\rightarrow\mathbb{N}$ is an $m$-reduction of $A$ to $B$, and $f$ is surjective. Then there is an $m$-reduction $\hat{f}$ from $B$ to $A$.

Namely, take $\hat{f}(x)$ to be the least $y$ such that $f(y)=x$; such a $y$ always exists since $f$ is surjective, and $\hat{f}$ is computable since $f$.