# Many-one reducibility

A relation between sets of natural numbers, expressing the notion of relative difficulty of computation. We say that $A$ is many-one reducible ($\mathrm{m}$-reducible) to $B$, $A \le_{\mathrm{m}} B$, if there is a general recursive function $\phi$ such that $x \in A$ if and only if $\phi(x) \in B$. This defines a pre-order on sets of natural numbers, and the equivalence classes are $\mathrm{m}$-degrees; they refine the Turing degrees.
Many-one reduction may also be regarded as a relation between functions on natural numbers: in this case, the characteristic functions of sets of natural numbers, with the pre-order $f \le_{\mathrm{m}} g$ if there is a recursive $\phi$ such that $f(x) = g(\phi(x))$ for all $x$.
We obtain the relation of $1$-reducibility (one-one reducibility) $A \le_{1} B$ if we restrict $\phi$ in this definition to being an injection. This is a strictly weaker notion. Sets $A$,$B$ are $1$-equivalent if and only if there is a computable permutation $\pi$ of $\mathbf{N}$ that maps $A$ onto $B$. The classes of $1$-complete, $\mathrm{m}$-complete and creative sets coincide.