[proofplan] We take total computable witnesses $f: \mathbb{N} \to \mathbb{N}$ for $A \le_m B$ and $g: \mathbb{N} \to \mathbb{N}$ for $B \le_m C$. The candidate witness for $A \le_m C$ is the composition $h = g \circ f$. We verify directly that $h$ is total computable and that membership in $A$ is equivalent to membership of $h(x)$ in $C$ for every input $x \in \mathbb{N}$. [/proofplan] [step:Choose computable witnesses for the two reductions] By the hypotheses $A \le_m B$ and $B \le_m C$, there exist total computable maps \begin{align*} f: \mathbb{N} &\to \mathbb{N}, \\ x &\mapsto f(x), \end{align*} and \begin{align*} g: \mathbb{N} &\to \mathbb{N}, \\ y &\mapsto g(y), \end{align*} such that, for every $x \in \mathbb{N}$ and every $y \in \mathbb{N}$, \begin{align*} x \in A &\iff f(x) \in B, \\ y \in B &\iff g(y) \in C. \end{align*} These are precisely the witnessing conditions for the two many-one reductions. [/step] [step:Compose the witnesses to obtain a total computable map] Define \begin{align*} h: \mathbb{N} &\to \mathbb{N}, \\ x &\mapsto g(f(x)). \end{align*} Since $f$ is total, $f(x)$ is defined for every $x \in \mathbb{N}$. Since $g$ is total, $g(f(x))$ is then defined for every $x \in \mathbb{N}$. Hence $h$ is total. To compute $h(x)$, first run the algorithm computing $f$ on input $x$, obtaining $f(x)$; then run the algorithm computing $g$ on input $f(x)$, obtaining $g(f(x))$. Both computations halt because $f$ and $g$ are total computable. Therefore $h$ is computable. [guided] We need a single computable transformation from instances of membership in $A$ to instances of membership in $C$. The natural candidate is to first use the reduction from $A$ to $B$, and then use the reduction from $B$ to $C$. Thus we define \begin{align*} h: \mathbb{N} &\to \mathbb{N}, \\ x &\mapsto g(f(x)). \end{align*} We verify totality first. Let $x \in \mathbb{N}$. Because $f: \mathbb{N} \to \mathbb{N}$ is total, the value $f(x)$ exists and belongs to $\mathbb{N}$. Because $g: \mathbb{N} \to \mathbb{N}$ is total, the value $g(f(x))$ exists and belongs to $\mathbb{N}$. Hence $h(x)$ is defined for every $x \in \mathbb{N}$, so $h$ is total. We now verify computability. On input $x$, an algorithm for $h$ performs two finite computations: first compute $f(x)$ using the algorithm for $f$, and then compute $g(f(x))$ using the algorithm for $g$. The first computation halts because $f$ is total computable, and the second computation halts because $g$ is total computable on every natural-number input. The output is exactly $h(x) = g(f(x))$. Therefore $h$ is computable. [/guided] [/step] [step:Verify that the composition preserves membership exactly] Let $x \in \mathbb{N}$. Since $f$ witnesses $A \le_m B$, \begin{align*} x \in A \iff f(x) \in B. \end{align*} Since $g$ witnesses $B \le_m C$, applying its witnessing equivalence to the natural number $y = f(x)$ gives \begin{align*} f(x) \in B \iff g(f(x)) \in C. \end{align*} Combining these two equivalences and using the definition $h(x) = g(f(x))$, we obtain \begin{align*} x \in A \iff h(x) \in C. \end{align*} Thus $h$ witnesses $A \le_m C$. [/step] [step:Conclude the many-one reduction] We have constructed a total computable map $h: \mathbb{N} \to \mathbb{N}$ such that, for every $x \in \mathbb{N}$, \begin{align*} x \in A \iff h(x) \in C. \end{align*} By the definition of many-one reducibility, $A \le_m C$. [/step]