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$.


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.

| cite | improve this answer | |
  • $\begingroup$ Let X = even integers, we set $\rho(2n) in X$ different from $\rho(2m)$ for $m < n$. Then set $\rho(2n-1)$ to be the $n$th element of $N - \{\pi(2n) : n \in{\bf N} \}$. Doesn't effectivise well since one would need to calculate $\pi(2n)$ for all evens first. $\endgroup$ – This account was hacked Feb 16 '17 at 21:56
  • $\begingroup$ @jay_hathaway You're doing too much work. Here's a hint: let's say I want to make a permutation $\rho$ which is different from a permutation $\pi$. Well, either $\pi(1)=2$ or not; so I can make $\rho$ different from $\pi$ by setting $\rho(1)=2, \rho(2)=1$ if $\pi(1)\not=2$, and $\rho(1)=1, \rho(2)=2$ if $\pi(1)=2$. Note moreover that this "confines" my action to $1$ and $2$ - I've declared nothing about e.g. $\rho(17)$. Do you see how to handle many permutations at once this way? And how to effectivize it? $\endgroup$ – Noah Schweber Feb 16 '17 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.