# Equivalence of two definitions of recursively enumerable sets

Let's define a recursively enumerable set as the domain of some program $$p$$, i.e., $$\{x:\phi_p(x)\downarrow\}$$.

There is another definition of a recursively enumerable set: it is either the empty set or the range of a computable function $$f: \mathbb N\to \mathbb N$$.

I'm trying to understand their equivalence.

One direction: suppose the second definition holds. Then define the program $$p$$ by the following conditions. The program $$p$$ takes an input $$x$$ and checks if $$x\in f(\mathbb N)$$: since $$f$$ is computable (say via $$e$$), the program $$p$$ can use $$e$$ to see, for each $$n=0,1,\dots$$, whether $$f(n)=x$$. If $$x\in f(\mathbb N)$$, then such $$n$$ will be found, and in this case we force $$p$$ to halt. Otherwise the program will work forever. For this program $$p$$, the domain of $$\phi_p$$ is $$f(\mathbb N)$$, q.e.d. Is this proof correct?

The other direction: This seems to be more difficult. I found this answer (which is supposedly what I need), from which the proof appears to be relatively easy, but I don't understand that proof. For example, I don't understand what $$\Phi_{e,s}$$ is.

• Regarding $\Phi_{e,s}$ in the linked answer, it probably means that you're now indexing your partial recursive functions by pairs of numbers instead of single numbers. This is not a problem, since there are computable bijections between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$. Also, the proof you offered above seems to be the direction which does not involve $\Phi_{e,s}$ in the linked answer. Commented Dec 1, 2019 at 1:05
• @Reveillark If we read $\Phi_{e,s}(n)$ as $\phi_{\pi(e,s)}(n)$ where $\pi$ is the Cantor pairing function, then it's not clear to me why $A$ is the range of $f$ from that answer. Commented Dec 1, 2019 at 1:17
• @Reveillark Actually, $\Phi_{e, s}$ is typically used to refer to the function computed by $\Phi_e$ where any computation that takes more than $s$ steps is considered to diverge. I.e. $\Phi_{e, s}$ means "run the program coded by $e$ for $s$ steps" Commented Dec 15, 2019 at 17:50

Here is another proof of the remaining direction: assume that $$A=\operatorname{dom}\phi_e$$ for some $$e$$. If $$A$$ is finite, then it is obviously an image of some computable function.
Now assume that $$A$$ is infinite. We will construct an infinite list $$\langle c_n\mid n<\omega\rangle$$: start from an empty list. We will add natural numbers into the list by considering the following procedure: for each $$n$$, check $$\phi_e(n)\downarrow$$. By dovetailing, we can evaluate $$\phi_e(n)$$ simultaneously for multiple $$n$$. If we finish computing $$\phi_e(n)$$ for given $$n$$, put $$n$$ into the list.
Since $$A$$ is infinite, out list is infinite. Let $$f$$ be the canonical enumeration of the list (i.e. $$f(n)=c_n$$.) By our construction of the list, $$f$$ is computable. Moreover, the image of $$f$$ is exactly $$A$$: if $$n\notin A$$, then $$n$$ will not be appear in our list.
• I'm not sure I understand why we can perform infinitely many checks $\phi_e(n)\downarrow$. It will take forever to know for which $n$ $\phi_e(n)\downarrow$, won't it? Commented Dec 3, 2019 at 0:27
• Another way to say this is to define $f(n)$ inductively as follows: if there is some $m < n$ such that $\phi_e(m)$ halts in at most $n$ steps and $m$ is not already in the range of $f$ then set $f(n)$ to be the least such $m$. Otherwise let $f(n)$ diverge. This also works fine when $A$ is finite. Commented Dec 15, 2019 at 17:55