[proofplan] A one-one reduction is a many-one reduction with an additional injectivity requirement. We take the same total computable function witnessing $A \le_1 B$ and use it as the many-one reduction witness. The membership equivalence is unchanged, and the injectivity hypothesis is simply not needed for many-one reducibility. [/proofplan] [step:Choose the one-one reduction witness] Assume $A \le_1 B$. By definition, there exists a total computable injective map \begin{align*} f: \mathbb{N} &\to \mathbb{N} \end{align*} such that, for every $x \in \mathbb{N}$, \begin{align*} x \in A \iff f(x) \in B. \end{align*} [/step] [step:Reuse the same computable map as a many-one reduction witness] Define the map \begin{align*} g: \mathbb{N} &\to \mathbb{N} \\ x &\mapsto f(x). \end{align*} Since $f$ is total and computable, $g$ is total and computable. For every $x \in \mathbb{N}$, the defining equality $g(x) = f(x)$ and the reduction property of $f$ give \begin{align*} x \in A \iff f(x) \in B \iff g(x) \in B. \end{align*} Thus $g$ satisfies the membership-preservation condition required for $A \le_m B$. [guided] The only difference between the two notions is that a one-one reduction requires the witnessing function to be injective, while a many-one reduction does not. We therefore keep the same function and ignore the extra property. Define \begin{align*} g: \mathbb{N} &\to \mathbb{N} \\ x &\mapsto f(x). \end{align*} Because $g$ is the same map as $f$, and $f$ is total computable by the hypothesis $A \le_1 B$, the map $g$ is also total computable. Now fix an arbitrary $x \in \mathbb{N}$. The one-one reduction witness $f$ satisfies \begin{align*} x \in A \iff f(x) \in B. \end{align*} Since $g(x) = f(x)$ by definition of $g$, this becomes \begin{align*} x \in A \iff g(x) \in B. \end{align*} This is exactly the condition required for $g$ to witness $A \le_m B$. The injectivity of $f$ is not used because many-one reducibility only asks for a total computable membership-preserving map. [/guided] [/step] [step:Conclude many-one reducibility] The map $g: \mathbb{N} \to \mathbb{N}$ is total computable and satisfies, for every $x \in \mathbb{N}$, \begin{align*} x \in A \iff g(x) \in B. \end{align*} Therefore $g$ witnesses $A \le_m B$. Hence $A \le_1 B$ implies $A \le_m B$. [/step]