[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*}
[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]
[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]
