Classifying index sets

$\mathrm{Fin}$ is $\Sigma^0_2$ by Example 1.2. Let $A$ be $\Sigma^0_2$: $x \in A \iff \exists y\ \forall z\ R(x, y, z)$ with $R$ computable. Consider the sets

The relation $n \in V_x$ is c.e., by closure under bounded quantification, so there is a computable $f$ with $W_{f(x)} = V_x$ for every $x$. If $x \notin A$, every $y$ has a $z$ with $\neg R(x, y, z)$, so $V_x = \nat$ is infinite. If $x \in A$, let $y_0$ be such that $\forall z\ R(x, y_0, z)$; then no $n > y_0$ belongs to $V_x$, so $V_x$ is finite. Hence $x \in A \iff f(x) \in \mathrm{Fin}$. The statement on $\mathrm{Inf}$ follows by complementation.

$\mathrm{Tot}$ is $\Pi^0_2$ by Example 1.2. Let $A$ be $\Pi^0_2$: $x \in A \iff \forall y\ \exists z\ R(x, y, z)$ with $R$ computable. Let $f$ be computable with $\Phi_{f(x)}(y) \simeq \mu z\ R(x, y, z)$. Then $\Phi_{f(x)}$ is total if and only if every $y$ has a witness $z$, that is, if and only if $x \in A$.

$\mathrm{Cof}$ is $\Sigma^0_3$ by Example 1.2. Let $A$ be $\Sigma^0_3$: $x \in A \iff \exists n\ P(x, n)$ with $P$ a $\Pi^0_2$ relation. By Theorem 3.1, $\mathrm{Inf}$ is $\Pi^0_2$-complete, so there is a computable $g$ with $P(x, n) \iff W_{g(x, n)}$ is infinite. We build, uniformly in $x$, a c.e. set $V_x$ which is cofinite if and only if some $W_{g(x, n)}$ is infinite.

Construction. We enumerate $V_x$ by stages, starting with $V_x[0] = \emptyset$. At stage $s + 1$, let $n$ be the least $n \leq s$ such that $W_{g(x, n)}[s + 1] \neq W_{g(x, n)}[s]$, if there is one; we say that $n$ acts at stage $s + 1$. In that case, list the elements of $\{0, \dots, s - 1\} \setminus V_x[s]$ in increasing order, and enumerate into $V_x$ all of them except the first $n$. If no $n \leq s$ acts, do nothing. The construction is computable uniformly in $x$, so there is a computable $h$ with $W_{h(x)} = V_x$.

The numbers not in $V_x$ at stage $s$, in increasing order, are called the markers at stage $s$. A stage at which $n$ acts keeps the first $n$ markers below $s$ and removes the others.

If some $W_{g(x, n)}$ is infinite, $V_x$ is cofinite. Fix such an $n$. Then $W_{g(x, n)}$ receives new elements at infinitely many stages, and at each of them some $n' \leq n$ acts. Suppose $m_0 < m_1 < \dots < m_n$ are $n + 1$ numbers outside $V_x$. Take a stage $s + 1$ with $s > m_n$ at which some $n' \leq n$ acts. The numbers $m_0, \dots, m_n$ are all below $s$ and outside $V_x[s]$, and $m_n$ is not among the first $n$ markers below $s$, since $m_0, \dots, m_{n-1}$ precede it. So $m_n$ is enumerated into $V_x$, a contradiction. Hence the complement of $V_x$ has at most $n$ elements.

If every $W_{g(x, n)}$ is finite, $V_x$ is coinfinite. We show that for every $k$, the $k$-th marker (counting from $0$) eventually reaches a final value. Only actions of some $n \leq k$ remove the $k$-th marker or a smaller one, since an action of $n$ keeps the first $n$ markers. Each $n \leq k$ acts only finitely often, since $W_{g(x, n)}$ is finite. After the last action of the numbers $n \leq k$, the first $k + 1$ markers are never removed: they are final. So the complement of $V_x$ contains the final values of all markers, and is infinite.

Hence $x \in A \iff h(x) \in \mathrm{Cof}$.