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

  • $\begingroup$ How do you define "recursive", is it $\mu$-recursive, or some other schemata of construction, or is it by logical complexity of the definition? $\endgroup$ – Asaf Karagila Nov 2 '17 at 11:40
  • 3
    $\begingroup$ You mean nonempty set don't you? The empty set is r.e. but is not the range of a total recursive function. $\endgroup$ – bof Nov 2 '17 at 11:41
  • 1
    $\begingroup$ Informally: Suppose a nonempty set $A$ is the domain of a partial recursive function $g.$ Choose $a\in A.$ Start computing $g(x)$ for all $x,$ one step at a time. If step $n$ of the big computation is the last step in the computation of $g(x),$ define $f(n)=x;$ if step $n$ is not the last step in the computation of any value of $g,$ define $f(n)=a.$ Then $f$ is a total recursive function whose range is $A.$ $\endgroup$ – bof Nov 2 '17 at 11:51
  • 1
    $\begingroup$ Is your text actually defining recursively enumerable as being the domain of a partial recursive function? $\endgroup$ – DanielV Nov 2 '17 at 11:54
  • 1
    $\begingroup$ @DanielV yes indeed. $\endgroup$ – Sid Caroline Nov 2 '17 at 12:36

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$


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 $


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.