Showing a set is not recursively enumerable Let $\Pi$ be the group of recursive permutations (i.e. bijections ${\bf N} \to {\bf N}$ that are computable.  Let $\phi_e : e \in {\bf N}$ be an enumeration of the recursive partial functions.
I think the set $\{e \in {\bf N} : \phi_e \in \Pi \}$ is not recursively enumerable.  It is easy to see that it is not recursive by reducing it to the halting problem (on input n simulating running $\phi_n(n)$ then return $n$ when it halts).
Furthermore, I wish to show that there is no recursively enumerable subset such that $\{ \phi_e \mid e \in P' \}$ is equal to $\Pi$.
 A: For the first part, suppose $f$ enumerates $\Pi$. By the Recursion theorem, we can build a partial recursive function $\varphi_e$ whose code "refers to" $f$'s behavior on input $e$. Now, the only constraint on $f$ is that $f(k)$ halts iff $\varphi_k$ is a permutation; so, our $\varphi_e$ should "look like" a permutation until (if ever) it sees $f(e)$ halt, and then "stop being a permutation."
HINT: the simplest permutation is the identity . . .
For a further exercise, modify this idea to show that $\Pi$ is, in fact, not even $\Sigma^0_2$! It is, in fact, $\Pi^0_2$ complete.

For the second part, first think about the classical proof that there are uncountably many permutations of $\mathbb{N}$: given a family $\pi_i$ of permutations, do you see how to diagonalize against them to produce a new permutation $\rho$? Now, that argument effectivizes in a natural way . . .
Note that this provides another argument that $\Pi$ is not recursively enumerable. But, the argument in the first part is of a kind that it is very good to know.
