Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, we can enumerate $S$ by calculating $\{f(0), f(1) \ldots \}$.

What is known about this class of sets? Where does it stand in terms of computability? I suspect that it contains sets that are not context free, and that it does not contain all recursive sets.

Has this been studied? Does anyone have a reference for this?


In "Extensions of some theorems of Gödel and Church" it's shown by Barkley Rosser that these sets are exactly the recursive sets:

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.

Note that the crux here is repetitions. Since you constructed sets, and comparing them with other sets, any repetitions do not violate their equality.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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