Journal of Symbolic Logic 67 (2):649-678 (2002)

Abstract
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
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: 56,949
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

Analytics

Added to PP index
2009-01-28

Total views
30 ( #344,916 of 2,409,937 )

Recent downloads (6 months)
4 ( #189,545 of 2,409,937 )

How can I increase my downloads?

Downloads

My notes