A Note on Natural Creative Sets and Goedel Numberings

Abstract

Creative sets (or the complete recursively enumerable sets) play an important role in logic and mathematics and they are known to be recursively isomorphic. Therefore, on the one hand, all the creative sets can be viewed as equivalent, on the other hand, we intuitively perceive some creative sets as more "natural and simpler" than others. In this note, we try to capture this intuitive concept precisely by defining a creative set to be natural if all other recursively enumerable sets can be reduced to it by computationally simple reductions and show that these natural creative sets are all isomorphic under the same type of computationally simple mappings. The same ideas are also applied to define natural Goedel numberings.