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 |
![]() ![]() ![]() ![]() |
Download options
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.
Automorphisms of the Lattice of Recursively Enumerable Sets. Part II: Low Sets.Robert I. Soare - 1982 - Annals of Mathematical Logic 22 (1):69.
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.
Similar books and articles
Definable Encodings in the Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2000 - Bulletin of Symbolic Logic 6 (2):185-196.
Codable Sets and Orbits of Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1998 - Journal of Symbolic Logic 63 (1):1-28.
Definable Incompleteness and Friedberg Splittings.Russell Miller - 2002 - Journal of Symbolic Logic 67 (2):679-696.
Isomorphisms of Splits of Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2003 - Journal of Symbolic Logic 68 (3):1044-1064.
Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
The Complexity of Orbits of Computably Enumerable Sets.Peter A. Cholak, Rodney Downey & Leo A. Harrington - 2008 - Bulletin of Symbolic Logic 14 (1):69 - 87.
On the Orbits of Hyperhypersimple Sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
Automorphisms of the Lattice of Recursively Enumerable Sets.Peter Cholak - 1995 - American Mathematical Society.
Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - Journal of Symbolic Logic 71 (4):1394 - 1410.
Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
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 )
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