= Solution
Membership is immediate from the supplied characterization of $\Pi_2$. Define the partial computable function
$$
F(v,x)=f_{v,1}(x).
$$
Then
$$
v\in\mathbf{Tot}
\quad\Longleftrightarrow\quad
W_v=\mathbb W
\quad\Longleftrightarrow\quad
(\forall x\in\mathbb W)\ F(v,x)\mathbin\downarrow,
$$
so $\mathbf{Tot}\in\Pi_2$.
Now let $P\in\Pi_2$. There is a partial computable $f$ such that
$$
w\in P
\quad\Longleftrightarrow\quad
(\forall x\in\mathbb W)\ f(w,x)\mathbin\downarrow.
$$
For each $w$, define a unary partial function
$$
g_w(x)=
\begin{cases}
x,&f(w,x)\mathbin\downarrow,\\
\text{undefined},&f(w,x)\mathbin\uparrow.
\end{cases}
$$
Operationally, its program simulates $f(w,x)$ and returns $x$ if that computation halts. By the <S-m-n theorem>, a total computable map $h$ produces an index $h(w)$ for $g_w$. Therefore
$$
\begin{aligned}
w\in P
&\Longleftrightarrow
(\forall x)\ g_w(x)\mathbin\downarrow\\
&\Longleftrightarrow W_{h(w)}=\mathbb W
\Longleftrightarrow h(w)\in\mathbf{Tot}.
\end{aligned}
$$
\b[Thus every <Pi-2 set> many-one reduces to $\mathbf{Tot}$. Combined with membership, this proves that the <totality problem> is $\Pi_2$-complete.]
Back to article page
