A set is recursively enumerable iff it is the range of a total recursive function

Question

A set is called recursively enumerable if it is the domain of a partially recursive function.

How can I show that this definition are equivalent to "A set is recursively enumerable iff it is the range of a total recursive function"?

I could only show one direction: if a set is the range of a total recursive function $f$, then it is the domain of a partial recursive function, by defining a function $g$, on input $y$, look for an $x$ such that $f(x)=y$.

Answer 1

It seems that you are having difficulty somewhere with converting the informal short sketch into a fully detailed sketch.

So let's try to see in detail how a (non-empty) set being r.e. (recursively enumerable) implies that it is the range of some total recursive function.

Let $A\subseteq \mathbb{N}$ be a non-empty r.e. set. Then, by definition, there exists a partial recursive function $f_A:\mathbb{N} \rightarrow \mathbb{N}$ such that: $$f_A(x)=1 \quad if \, x\in A$$ $$f_A(x)=\,\uparrow \qquad if \, x\notin A$$

We want to construct a (total) recursive function $g:\mathbb{N} \rightarrow \mathbb{N}$ such that: $$range(g)=A$$ Let's divide into two cases:

(1) A has infinite number of elements

In that case define a function such as $step:\mathbb{N}^3\rightarrow\mathbb{N}$ such that $step(i,t,x)$ returns $1$ if a program corresponding to index $i$ halts(when given the input $x$) exactly at step $t$ -- and $0$ otherwise.

Note that since the function $f_A$ described above is partial recursive, there exists some program that computes it. The variable $x$ below is supposed to be given as input to the function $g$. Here is how we proceed with constructing the function $g(x)$:

$i:=index\;of\;some\;program\;that\;computes\;f_A \\ n:=0 \\ m:=0 \\ while(n\neq x+1) \,\,\{ \\ a:=first(m) \\ b:=second(m) \\ \qquad if(step(i,a,b)=1) \,\,\{ \\ \qquad \,\, n:=n+1\\ \qquad \,\,y:=b \\ \qquad \} \\ m:=m+1 \\ \} \\ return \;\; y $

For the functions $first:\mathbb{N} \rightarrow \mathbb{N}$ and $second:\mathbb{N} \rightarrow \mathbb{N}$, see for example https://en.wikipedia.org/wiki/Pairing_function. To define them rigorously consider any computable bijective function $pair:\mathbb{N}^2 \rightarrow \mathbb{N}$. Define: $$first(x)=\{\,a\in\mathbb{N} : \exists b\in \mathbb{N} \, (pair(a,b)=x) \}$$ $$second(x)=\{\,b\in\mathbb{N} : \exists a\in \mathbb{N} \, (pair(a,b)=x) \}$$ I think these definitions should be OK (but I am not fully confident). Anyway, note that the main properties of these functions are that for all $a,b \in \mathbb{N}$ we have: $$first(pair(a,b))=a$$ $$second(pair(a,b))=b$$

(2) A has finite number of elements

Suppose the number of elements in A are $N$. Then we can write A (without repetition) as: $$A=\{a_0,\,a_1,....,a_{N-1}\}$$

Now define:

$g(x)=a_{x} \qquad for \; 0\leq x \leq N-1 \\ g(x)=a_{N-1} \qquad for \; x \geq N$

P.S.

The above method in case(1) doesn't repeat the elements of A (in the range of g) when it is infinite.

The method that is described in comments below the question is a little different and removes the need of having a separate case for finite number of elements. Suppose $e\in A$. Here is a sketch for calculating $g(x)$ using that method:

$i:=index\;of\;some\;program\;that\;computes\;f_A \\ e:=some\;element\;that\;belongs\;to\;A \\ a:=first(x) \\ b:=second(x) \\ if(step(i,a,b)=1) \,\,\{ \\ y:=b \\ \} \\ if(step(i,a,b)=0) \,\,\{ \\ \\ y:=e \\ \} \\ return \;\; y $