How to prove that the set INF is not recursively enumerable

Question

I've been given the set $INF=\{e\in\mathbb{N}:dom(\varphi_e)$ is infinite$\}$, where $\varphi_e$ denotes the $e$-th computable function.

I'm trying to prove that it is not recursively enumerable. I tried to follow the same strategy as with the complementary set, $FIN$, for which I assumed it was r.e. and then defined the function

$$ f(e,x)=\begin{cases} x & e\in FIN\\ \uparrow & otherwise \end{cases} $$

Which is computable because its graph is r.e. by assumption, carrying me to a contradiction by examining the possible cases. But in this case, if I define

$$ g(e,x)=\begin{cases} x & e\in INF\\ \uparrow & otherwise \end{cases} $$

Then there is no contradiction with the fact of $g$ being computable. What strategy should I follow then?

Answer 1

This can be done with a "regular" (i.e. usual) diagonalization, using what I would call a "watch and wait" method.

Choose any $e$ and look at $W_e$. Make a program $j$ that simulates the enumeration of $W_e$, and so that $\phi_j(n)$ halts if and only if $j$ does not enter $W_e$ within the first $n$ steps of the simulation. This uses the recursion theorem to allow $j$ to know its own index.

Then we can show that $j \in W_e$ if and only if the domain of $\phi_j$ is finite. So $W_e$ does not enumerate INF. Now $e$ was arbitrary, so INF is not r.e.

There is a more principled way to solve this problem. We should always begin this type of problem with a Tarski-Kuratowski computation to guess the complexity of the set within the arithmetical hierarchy. One definition of INF is: $$ \text{INF} = \{e : (\forall n)(\exists m)(\exists t)[ n > m \land \phi_{e,t}(n)\downarrow]\} $$ So we would guess that INF is a $\Pi^0_2$ set. Thus, a better way to show INF is not r.e. (that is, not $\Sigma^0_1$) would be to show that INF is $\Pi^0_2$ complete. It is not hard to do this - to show that every $\Pi^0_2$ set is many-one reducible to INF. Then we know that INF cannot be r.e. because of Post's theorem, but we actually have a sharp computation of the location of INF in the arithmetical hierarchy.

Similarly, FIN can be defined as $$ \text{FIN} = \{ e : (\exists m)(\forall n)(\forall t)[n > m \to \phi_{e,t}(n)\uparrow]\}.$$ So we would guess that FIN is $\Sigma^0_2$, and try to prove that every $\Sigma^0_2$ set is many-one reducible to FIN. This gives more information than just "FIN is not r.e." but it also gives a suggestion for where to start the proof.