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