How to prove that the set INF is not recursively enumerable 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?
 A: 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. 
