# Is there a “primitive-recursively enumerable” set whose complement is not such?

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.

-
Why does it say "2 Answers" when there are three answers posted? I see answers by Chad Groft, Antonio Porreca and myself. – Joel David Hamkins Apr 12 '10 at 12:59
Is it because the answers were very nearly simultaneous? (As well as nearly identical, since we all hit upon the same argument!) – Joel David Hamkins Apr 12 '10 at 13:30
Thank you for the answers. I realized the same thing over dinner. Now how do I accept all of them? Or do I accept just the first one. – Andrej Bauer Apr 12 '10 at 21:07
I think it is fine to just accept the first one. And now I see that MO agrees that there are three answers... – Joel David Hamkins Apr 13 '10 at 13:45

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 aS, 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.

-

I claim that a set is primitive recursive enumerable if and only if it is computably enumerable. So the answer to your question is affirmative.

Clearly any p-r.e. set is c.e., since primitive recursive functions are computable. Conversely, suppose that A is computably enumerable. We want to show A is p-r.e. If A is empty, then we're done. So fix some element a0 in A. Since A is c.e., it is the domain of a computable function f, computed by program e. Consider now the function h(s,n) = n, if s codes the proof of a halting computation of program e on input n, and otherwise h(s,n) = a0. The function h is defined by Δ0 cases, and hence is primitive recursive. Also, the range of h is A, as desired.

So there are numerous sets A as you desire!

-

This is an interesting question. From B. Rosser, Extensions of some theorems of Gödel and Church:

Corollary I. If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function.

Hence any complete recursively enumerable set (such as K) should work.

-