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

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 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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2273100
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 52,973
Through your library

References found in this work BETA

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

Citations of this work BETA

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 11 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
201 ( #42,863 of 2,344,080 )

Recent downloads (6 months)
1 ( #514,058 of 2,344,080 )

How can I increase my downloads?

Downloads

My notes