|ISSN 1088-6834(online) ISSN 0894-0347(print)|
The -automorphism method
Abstract: A set of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let denote the structure of the computably enumerable sets under inclusion, . Most previously known automorphisms of the structure of sets were effective (computable) in the sense that has an effective presentation. We introduce here a new method for generating noneffective automorphisms whose presentation is , and we apply the method to answer a number of long open questions about the orbits of c.e. sets under automorphisms of . For example, we show that the orbit of every noncomputable ( i.e., nonrecursive) c.e. set contains a set of high degree, and hence that for all the well-known degree classes (the low c.e. degrees) and (the complement of the high c.e. degrees) are noninvariant classes.
Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 03D25
Retrieve articles in all journals with MSC (1991): 03D25