Proof that INF (the set of indices of Turing Machines that halt on infinitely many inputs) is not computably enumerable, I.e. $\not \in \Sigma_1^0$

Question

I got curious about this today when looking for sets to proove aren't $\Sigma_1$ as exam prep.

Unlike with its complement, FIN, a run of the mill contradiction was not easy to come by (perhaps I'm being stupid), and the infinite domains of the functions don't necessarily intersect, so I see no way to diagonalise out. My next line of attack was to show:

$$a \in \text{INF} \iff \forall m \exists n,s: (n > m) \land \varphi_a^s(n) \downarrow$$

So INF is $\Pi_2$. If it's $\Pi_2$ complete, then INF $=_T 0''$, which contradicts that any $\Sigma_1$ set turing reduces to $0'$. But I've not had any luck prooving this completeness, nor the equivalent condition that FIN is $\Sigma_2$ complete.

Answer 1

Yes, INF is $\Pi^0_2$ complete. You can prove this by a small variation the same reduction from the reduction here.

You can also prove the weaker result that INF is not $\Sigma^0_1$ by diagonalization. Here is the construction, and then a verification.

---

Construction

Suppose $W$ is an arbitrary r.e. set. Let $e$ be a program that does the following. On input $k$, $e$ first simulates the enumeration of $W$ for $k$ timesteps. If $e$ finds that its own index $e$ is not enumerated into $W$ within $k$ timesteps, then $e(k)$ halts. Otherwise, if $e$ is enumerated into $W$ in $k$ timesteps, then $e(k)$ does not halt. The circularity here (that $e$ knows its own index) is easy to resolve with the recursion theorem.

---

Verification

First suppose $e \in W$. Then there is some $k$ for which $e$ is enumerated into $W$ in $k$ timesteps. Then $e(n) \uparrow$ for all $n \geq k$, so $e \not \in \text{INF}$.

Conversely, suppose $e \not \in W$. Then $e(k)\downarrow$ for all $k$, so $e \in \text{INF}$.

Overall, $e \in W \leftrightarrow e \not \in \text{INF}$.

Here $W$ was an arbitrary r.e. set, so in particular INF cannot be an r.e. set, because we would obtain a contradiction if $W$ could be the set INF.

Answer 2

The diagonalisation method, which I figured out after Carl Mummert noted that it is possible:

Assume INF is $\Sigma_1$. Then we can enumerate its elements computably; for come computable $f$, we have INF $= \{ f(0), f(1), ...\}$.

Now construct a partial recursive function $g$ as follows:

First do one step of the computation for $\varphi_{f(0)} (0)$, then two steps of $\varphi_{f(0)} (0)$ and $\varphi_{f(0)} (1)$, then three of $\varphi_{f(0)} (0)$, $\varphi_{f(0)} (1)$ and $\varphi_{f(0)} (2)$ etc. Since the domain of $\varphi_{f(0)}$ is non-empty, this process will eventually halt for some argument $n_0$. Now we define that $g(n_0) = \varphi_{f(0)} (n_0)+1$.

Repeat this process for $\varphi_{f(1)}$, and let the first argument (excluding $n_0$) which $\varphi_{f(1)}$ halts on be $n_1$. Then we define $g(n_1) = \varphi_{f(1)} (n_1)+1$.

Each time, we repeat this process, defining $g$ at a new (unique) $n_k$. We can always afford to ignore previous $n_i$ because the domain of every function under consideration is infinite, so they must still halt yet somewhere else.

To compute the function at a value, simply go through the construction until an $n_i$ is found which is the input. If no such $n_i$ is ever found, this process naturally diverges.

$g$ is defined on the infinite set $\{ n_0, n_1, n_2, ... \}$, hence $\exists e$ with $g(n) = \varphi_{f(e)} (n)$.

But $\varphi_{f(e)} (n_e) = g(n_e) = \varphi_{f(e)} (n_e)+1$

By the construction, $\varphi_{f(e)}(n_e) \downarrow$ and $g(n_e) \downarrow$, so the above implies $0=1$.

This is a contradiction, so INF is not $\Sigma_1$.