Recursively Enumerable Generic Sets
Maass, Wolfgang
J. Symbolic Logic, Tome 47 (1982) no. 1, p. 809-823 / Harvested from Project Euclid
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 $\mathscr{E}$ 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.
Publié le : 1982-12-14
Classification: 
@article{1183741140,
     author = {Maass, Wolfgang},
     title = {Recursively Enumerable Generic Sets},
     journal = {J. Symbolic Logic},
     volume = {47},
     number = {1},
     year = {1982},
     pages = { 809-823},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741140}
}
Maass, Wolfgang. Recursively Enumerable Generic Sets. J. Symbolic Logic, Tome 47 (1982) no. 1, pp.  809-823. http://gdmltest.u-ga.fr/item/1183741140/