On orbits of prompt and low computably enumerable sets

Journal of Symbolic Logic 67 (2):649-678 (2002)
This paper concerns automorphisms of the computably enumerable sets. We prove two results relating semilow sets and prompt degrees via automorphisms, one of which is complementary to a recent result of Downey and Harrington. We also show that the property of effective simplicity is not invariant under automorphism, and that in fact every promptly simple set is automorphic to an effectively simple set. A major technique used in these proofs is a modification of the Harrington-Soare version of the method of Harrington-Soare and Cholak for constructing Δ 0 3 automorphisms; this modification takes advantage of a recent result of Soare on the extension of "restricted" automorphisms to full automorphisms
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1190150103
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 31,812
Through your library
References found in this work BETA
The Dense Simple Sets Are Orbit Complete with Respect to the Simple Sets.Peter Cholak - 1998 - Annals of Pure and Applied Logic 94 (1-3):37-44.

Add more references

Citations of this work BETA
Orbits of Computably Enumerable Sets: Low Sets Can Avoid an Upper Cone.Russell Miller - 2002 - Annals of Pure and Applied Logic 118 (1-2):61-85.

Add more citations

Similar books and articles
Added to PP index

Total downloads
8 ( #552,295 of 2,231,535 )

Recent downloads (6 months)
1 ( #445,507 of 2,231,535 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature