Recursively enumerable generic sets

Journal of Symbolic Logic 47 (4):809-823 (1982)
  Copy   BIBTEX


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 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



    Upload a copy of this work     Papers currently archived: 74,213

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

202 (#60,992)

6 months
1 (#414,449)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Splitting Theorems in Recursion Theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Some Orbits for E.Peter Cholak, Rod Downey & Eberhard Herrmann - 2001 - Annals of Pure and Applied Logic 107 (1-3):193-226.
Definable Properties of the Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):97-125.

View all 13 citations / Add more citations

References found in this work

Set Theory.Keith J. Devlin - 1981 - Journal of Symbolic Logic 46 (4):876-877.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

Add more references