8
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ Why does it say "2 Answers" when there are three answers posted? I see answers by Chad Groft, Antonio Porreca and myself. $\endgroup$ Apr 12, 2010 at 12:59
  • $\begingroup$ Is it because the answers were very nearly simultaneous? (As well as nearly identical, since we all hit upon the same argument!) $\endgroup$ Apr 12, 2010 at 13:30
  • $\begingroup$ 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. $\endgroup$ Apr 12, 2010 at 21:07
  • $\begingroup$ I think it is fine to just accept the first one. And now I see that MO agrees that there are three answers... $\endgroup$ Apr 13, 2010 at 13:45

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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!

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.