Is there a "primitive-recursively enumerable" set whose complement is not such? - MathOverflow

Is there a "primitive-recursively enumerable" set whose complement is not such?

2010-04-12T11:11:19Z

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.

Answer by Chad Groft for Is there a "primitive-recursively enumerable" set whose complement is not such?

2010-04-12T12:25:29Z

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.

Answer by Antonio E. Porreca for Is there a "primitive-recursively enumerable" set whose complement is not such?

2010-04-12T12:26:07Z

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.

Answer by Joel David Hamkins for Is there a "primitive-recursively enumerable" set whose complement is not such?

2010-04-12T12:26:07Z

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 a₀ 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) = a₀. The function h is defined by Δ₀ cases, and hence is primitive recursive. Also, the range of h is A, as desired.

So there are numerous sets A as you desire!