[proofplan] We first express totality of $\varphi_e$ as a $\forall\exists$ arithmetical condition by using a decidable bounded halting predicate. For hardness, we take an arbitrary $\Pi^0_2$ set $A$, write membership in normal form as $\forall u\,\exists v\,R(x,u,v)$ with $R$ computable, and build a partial computable function that halts on input $u$ exactly when such a witness $v$ is found. The [s-m-n theorem](/theorems/5398) then turns this uniform construction into a computable map $x \mapsto e_x$, and totality of $\varphi_{e_x}$ is exactly membership of $x$ in $A$. [/proofplan]

[step:Express totality as a $\Pi^0_2$ condition] Let $H \subseteq \mathbb{N}^3$ be the bounded halting predicate defined by \begin{align*} H(e,u,s) \iff \text{the computation of }\varphi_e(u)\text{ halts within }s\text{ steps}. \end{align*} The predicate $H$ is computable because the first $s$ steps of a computation in the fixed acceptable enumeration can be simulated effectively. For every $e \in \mathbb{N}$, \begin{align*} e \in \operatorname{TOT} &\iff \forall u \in \mathbb{N},\ \varphi_e(u)\downarrow \\ &\iff \forall u \in \mathbb{N},\ \exists s \in \mathbb{N},\ H(e,u,s). \end{align*} Since $H$ is computable, this is a $\Pi^0_2$ definition of $\operatorname{TOT}$. Hence $\operatorname{TOT} \in \Pi^0_2$. [/step]

[step:Represent an arbitrary $\Pi^0_2$ set by a computable predicate] Let $A \subseteq \mathbb{N}$ be an arbitrary $\Pi^0_2$ set. By the definition of the class $\Pi^0_2$, there exists a computable predicate \begin{align*} R: \mathbb{N}^3 \to \{0,1\} \end{align*} such that, for every $x \in \mathbb{N}$, \begin{align*} x \in A \iff \forall u \in \mathbb{N},\ \exists v \in \mathbb{N},\ R(x,u,v)=1. \end{align*} We fix this predicate $R$ for the rest of the proof. [/step]

[step:Build a uniform search procedure whose domain records the witnesses]Define a two-input partial computable function \begin{align*} \Psi: \mathbb{N}^2 \rightharpoonup \mathbb{N} \end{align*} as follows. On input $(x,u) \in \mathbb{N}^2$, the procedure searches through all possible witnesses in the order $v = 0,1,2,3,\dots$ until it finds a value satisfying $R(x,u,v)=1$; when it finds such a $v$, it halts and outputs $0$. Because $R$ is computable, the search procedure is partial computable. For every $x,u \in \mathbb{N}$, \begin{align*} \Psi(x,u)\downarrow \iff \exists v \in \mathbb{N},\ R(x,u,v)=1. \end{align*}[/step]

[guided]The goal is to convert the statement \begin{align*} \forall u \in \mathbb{N},\ \exists v \in \mathbb{N},\ R(x,u,v)=1 \end{align*} into a statement saying that a single partial computable function is total. The natural way to do this is to make the input $u$ ask for its own witness $v$. Define \begin{align*} \Psi: \mathbb{N}^2 \rightharpoonup \mathbb{N} \end{align*} by the following algorithm: given $(x,u) \in \mathbb{N}^2$, compute $R(x,u,0)$, then $R(x,u,1)$, then $R(x,u,2)$, and continue in increasing order. If the first value $v$ with $R(x,u,v)=1$ is found, halt and output $0$. This algorithm is partial computable because $R$ is computable and the search over all values of $v \in \mathbb{N}$ is effective. If a witness $v$ exists, then the search reaches such a witness after finitely many stages and halts. If no witness exists, then every tested value fails and the search never halts. Therefore, for every $x,u \in \mathbb{N}$, \begin{align*} \Psi(x,u)\downarrow \iff \exists v \in \mathbb{N},\ R(x,u,v)=1. \end{align*} This equivalence is the key encoding: totality in the $u$-variable will become the universal quantifier $\forall u$ in the $\Pi^0_2$ definition of $A$.[/guided]

[step:Uniformly convert the search procedure into indices] By the s-m-n theorem (citing a result not yet in the wiki: s-m-n theorem), applied to the two-input partial computable function $\Psi$, there exists a total computable function \begin{align*} f: \mathbb{N} \to \mathbb{N} \end{align*} such that, for every $x,u \in \mathbb{N}$, \begin{align*} \varphi_{f(x)}(u) = \Psi(x,u) \end{align*} as partial computations. In particular, \begin{align*} \varphi_{f(x)}(u)\downarrow \iff \Psi(x,u)\downarrow. \end{align*} [/step]

[step:Verify that the computable map is a many-one reduction] For every $x \in \mathbb{N}$, using the definition of $\operatorname{TOT}$, the defining property of $f$, and the construction of $\Psi$, we have \begin{align*} f(x) \in \operatorname{TOT} &\iff \forall u \in \mathbb{N},\ \varphi_{f(x)}(u)\downarrow \\ &\iff \forall u \in \mathbb{N},\ \Psi(x,u)\downarrow \\ &\iff \forall u \in \mathbb{N},\ \exists v \in \mathbb{N},\ R(x,u,v)=1 \\ &\iff x \in A. \end{align*} Thus $f$ is a total computable many-one reduction from $A$ to $\operatorname{TOT}$. Since $A \in \Pi^0_2$ was arbitrary, every $\Pi^0_2$ set many-one reduces to $\operatorname{TOT}$. Together with $\operatorname{TOT} \in \Pi^0_2$, this proves that $\operatorname{TOT}$ is many-one complete for $\Pi^0_2$. [/step]