Abstract: Abstract We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0′. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice ℰ of recursively enumerable sets with inclusion. We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions.
Publication Year: 1982
Publication Date: 1982-12-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 53
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot