An effective enumeration of recursive sets in increasing order

Question

Definition: We call a set recursive if its characteristic function is recursive.

Claim: If the set $A\subset\mathbb N$ is recursive then $A=Range(f)$ for some recursive and increasing function.

Proof: If $A$ is infinite define $h$ by

$$h(0)=\mu z[\chi_A(z)=1]$$ $$h(x+1)=\mu z[\chi_A(z)=1\land z>h(x)]$$

Here $\mu,\chi_A$ are the minimization operator and $A$'s characteristic function respectively.

If $A$ is finite then $A=\{a_1,\dots a_n\}$ with $a_1<a_2\dots<a_n$. Now define $h$ by

$h(i)=\begin{cases} a_i & i<n \\ a_n & i\geq n\\ \end{cases}$

Clearly in each case the function $h$ satisfies the conditions of the theorem.

Questions:

1) Unless we can effectively decide on the ordinality of sets, the above procedure is ineffective. What is an effective procedure for enumerating recursive sets in increasing order?

2) If the set $A$ is infinite can we choose a strictly monotone enumeration function that is primitive recursive?

Answer 1

For (2), obviously not -- given an infinite decidable subset of $\mathbb N$, there is exactly one strictly monotone function that enumerates it, and that function does not have to be primitive recursive, as for example with $$ \{n\mid \exists k<n: n=\mathsf A(k,k)\} $$ where $\mathsf A$ is Ackermann's function, which by construction is not primitive recursive.

For (1), it sounds like you want a procedure that takes an (always halting) program and a produces different program that enumerates its accept set in non-decreasing order. Once you accept repetitions (which is necessary to deal with finite sets), this should be as easy as creating a program that computes

$$ f(n) = \max\bigl( (A \cap \{ 0,1,\ldots,n \})\cup\{\min A\} \bigr)$$

... as long as $A$ is not empty, of course.

Answer 2

Okay, so a couple of things.

Suppose that you know the index $e$ such that $\varphi_e$ is the indicator function for a nonempty recursive set $A$ (so we are promised that $\varphi_e$ is total recursive and not identically zero). Then:
- If you don't mind repeating elements, take $f(e,n) = n$ if $\varphi_e(n) = 1$ and $f(e, n) = f(e, n-1)$ otherwise, while $f(e, 0) = \mu x(\varphi_e(x) =1)$.
- If you don't like repeating elements in your enumeration of infinite recursive sets, you are out of luck. Determining whether $\varphi_e$ is eventually $0$ (i.e., $A$ is finite) is not a computable task, nor is determining whether it is identically zero. You could solve the halting problem if you could solve this.

This function of course doesn't converge for most $n$ when $\varphi_e$ is not total recursive (or when $\phi_e$ is never $1$). If you need $f(e,n)$ to be an increasing enumeration when $\varphi_e$ is total recursive and the indicator function for a nonempty recursive set, and also be a total recursive function, you are again out of luck. Once again this would solve the halting problem.