A subset of $ \mathbb{N}$ is recursively enumerable iff it is the range of some recursive function from $\mathbb{N }$ to $\mathbb{N}$.

Question

I know how to prove the converse of the statement, but given a recursively enumerable set, I don't know how to find such a recursive function. Also, how to prove that the function can be chosen as injective if the set is infinte?

Answer 1

First of all, if you want the function to be total then we need the set in question to be nonempty. :P

Modulo that, the point is that the elements of an r.e. set can be listed in two natural ways:

• by the usual ordering on $\mathbb{N}$, or

• by when the relevant computation converges.

To elaborate on this second point: suppose $W_e=dom(\Phi_e)$ is an r.e. set, and $x, y\in W_e$. Say $x$ enters $W_e$ before $y$ if

• EITHER there is some $n$ such that $\Phi_e(x)[n]\downarrow$ but $\Phi_e(y)[n]\uparrow$,

• OR both $\Phi_e(x)$ and $\Phi_e(y)$ take the same number of steps to halt, and $x<y$. Basically, this case is just disambiguation.

Finally, let's adopt the convention that before $\Phi_e(x)$ halts, the machine $\Phi_e$ has to actually read all the input "$x$" - that is, $\Phi_e(x)$ takes at least length-of-$x$-many steps to halt, and consequently only finitely many numbers enter $W_e$ at a given stage.

Call this the time order on $W_e$ (not common terminology), and denote it "$<_{time}$".

Then the point is that $W_e$ can be listed effectively in the time order: if $n_0<_{time}n_1<_{time}n_2<_{time}\dots$ are the elements of $W_e$ in the time order, then the sequence $$n_0, n_1, n_2, \dots$$ is a computable sequence (and is infinite iff $W_e$ is).

• Do you see why?

• Do you see how to use this to express $W_e$ as the range of a total computable function?

Keep in mind that the usual order on $W_e$ does not work here - e.g. the Halting Problem $K$ is an r.e. set, yet the sequence of elements of $K$ in increasing order is of course not recursive (if it were, then $K$ would be recursive).