Call a subset of $\mathbb{N}$ *primitive-recursively enumerable (p-r.e.)* if it is empty or an image of a primitive recursive function. I feel like a lot must be known about the poset of such sets ordered by inclusion, but I am unable to dig up references. Concretely, I would like to know whether there exists a p-r.e. set whose complement is not p-r.e.


The answer is affirmative if there is a complete set (in the sense of many-to-one reducibilities) that is enumerated by a primitive recursive function. My hunch is that such a set exists, but cannot come up with one.



Is there a "primitive-recursively enumerable" set whose complement is not such?
There is a stronger result: *Every r.e. set is primitive r.e. in your sense.*


Short proof: Kleene's Normal Form Theorem.


Longer proof: Let *S* be an r.e. set, assumed WLOG nonempty; fix *a* ∈ *S*, and fix an algorithm *e* where *S* is precisely the range of the function computed by *e*.


Consider the following algorithm: Given the input pair (*n*, *M*), run *e* on input *n* for *M* steps. If it gives an output by then, output whatever *e* outputs; otherwise output *a*.


The functions which set up the initial state of computation, advance a state by one step, and extract the output from a final state, are all p.r. Thus the above algorithm defines a p.r. function, and it is easy to check that its range is *S*.


Edit: Cutland's *Computability* is a decent resource for these questions.


