I am working on an interesting theorem of Uspenskii which says that the class of infinite computably enumerable sets is not computably enumerable.
By contradiction we suppose that there exists a total recursive function $g$ which enumerates the infinite computably enumerable sets. In particular for all $x \in \mathbb{N}$, $W_{g(x)}$ is infinite and for every infinite computably enumerable set $A$ there exists $x \in \mathbb{N}$ such that $A =W_{g(x)}$.
Using the function $g$, we try to build by induction a primitive recursive function $f$ such that : for all $x \in \mathbb{N}$, $f(x+1) > f(x)+1$ and $f(x) + 1 \in W_{g(x)}$.
We notice that $x \in (W_{g(s)} = \text{dom} (\varphi_{g(s)}) \ ) \Leftrightarrow \varphi_{g(s)}(x) \downarrow \ \Leftrightarrow \exists t \ T^1[s,x,t]$ where $T^1$ is the recursive primitive Kleene's predicate.
For $x=0$, let us write $s= f(0)+1 \in W_{g(0)}$ and introduce $z \in \mathbb{N}$ which is a code for the pair $\langle s,t \rangle$.
Hence $f(0) = \pi_2^1(\mu z .T^1[\pi_2^1(z),0,\pi_2^2(z)] \ \wedge \ \pi_2^1(z)\ge 1)-1$.
For the induction step we write $s = f(x+1) + 1 \in W_{g(x+1)}$ and we take the same $z$ as previously.
Hence $f(x+1) = \pi_2^1(\mu z .T^1[\pi_2^1(z),x+1,\pi_2^2(z)] \ \wedge \ \pi_2^1(z)\ge 1 \ \wedge \ (\pi_2^1(z)-1 > f(x)+1)\ )-1$.
The function $f$ is then primitive recursive. Moreover, we can notice that $f$ is total, strictly increasing and its range is infinite. Hence $\text{range}(f)$ is computably enumerable.
Then there exists $x_0\in \mathbb{N}$ such that : $\text{range}(f)= W_{g(x_0)}$. However, by definition of $f$, we know that $f(x_0)+1 \in W_{g(x_0)}$ and also, there exists $y_0\in \mathbb{N}$ such that : $f(y_0)=f(x_0)+1$. Finally we notice that if $y_0>x_0$, then $f(y_0) \ge f(x_0+1)>f(x_0) + 1 = f(y_0)$ and if $x_0 > y_0$, then $f(x_0) \ge f(y_0+1)> f(y_0)+1=f(x_0) +2$ which is impossible.
But I am not sure how this argument concludes the proof ? I guess I miss a thing...
Apparently, I also have to consider the following $\Sigma_1^0$- set, $B := \{(s,x)\in \mathbb{N}^2\ ; x\in W_{g(s)}\}$ (indeed, $(s,x) \in B \Leftrightarrow \exists t \ \varphi_{g(s)}(x)[t] \ \text{"halts"}$, gives the computably enumerable character).
Thanks in advance !
I dislike these recursion theory proofs that are an impenetrable mass of symbols, obscuring the computation that underlies them.
Here's what's really happening: We have a recursive function $g\colon\mathbb N\to\mathbb N$ such that $W_{g(x)}$ is infinite for all $x\in\mathbb N.$ We want to find some infinite r.e. set $R$ that is not equal to any of the $W_{g(x)}\text{'s.}$ (The $R$ we'll find will actually turn out to be recursive, not just r.e.)
We'd like to carry out the construction in steps, where at step $n$ we make sure that the set $R$ we're constructing doesn't equal $W_{g(n)}.$ There are two natural ways of trying to do this:
Strategy (A): Take some number that's not in $W_{g(n)}$ and put it into $R;$
or
Strategy (B): Take some number that is in $W_{g(n)}$ and ensure that it's never put into $R.$
Since we have no computable way to determine a number which isn't in $W_{g(n)},$ Strategy (A) doesn't seem feasible. So we'll go with Strategy (B).
Carry out the following computation:
Stage 0: Enumerate $W_{g(0)}$ until you hit some number $a_0.$ (The set being enumerated is infinite, so this has to halt.)
Stage 1: Enumerate $W_{g(1)}$ until you hit some number $a_1 \ge a_0+2.$ (Again, the set being enumerated is infinite, so this has to halt.)
Stage 2: Enumerate $W_{g(2)}$ until you hit some number $a_2 \ge a_1+2.$ (As before, the set being enumerated is infinite, so this has to halt.)
In general:
Stage $\mathbf{\boldsymbol{\normalsize{n}}\gt 0}$: Enumerate $W_{g(n)}$ until you hit some number $a_n \ge a_{n-1}+2.$ (The set being enumerated is infinite, so this has to halt.)
[By the way, note that the enumerations of the various $W_{g(n)}$ that we are using are generally not in increasing order, so we have no guarantee that each $a_n$ is the least number in $W_{g(n)}$ with the indicated property; it's merely the first number in the enumeration order with that property.]
Each $a_n$ is in the corresponding $W_{g(n)}$ by construction, and we'll make sure that none of the $a_n\text{'s}$ are in $R.$
The enumeration $a_0 < a_1 < a_2 < \dots < a_n < \dots$ is computable, infinite, and in strictly increasing order, so it must enumerate a recursive set. It follows that its complement is also recursive, and that's what we'll take as $R;$ that guarantees that none of the $a_n$ are in it:
$$R=\{x \mid (\forall n)(x\ne a_n)\}.$$
So:
(1) $R$ is a recursive set (since it's the complement of a recursive set).
(2) $R$ is infinite, since for every $n\in\mathbb N,$ $a_n+1\in R.$ (This is because we made sure that each $a_k$ is at least $2$ greater than its predecessor, so $a_n+1$ can't be any of the $a_k\text{'s.)}$
(3) For each $n,$ we have $R\ne W_{g(n)}$; that's because $a_n$ is in $W_{g(n)}$ but $a_n\notin R.$