MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 6 down vote accepted

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.

share|cite|improve this answer

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!

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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