Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

The $\Delta ^0_3$-automorphism method
and noninvariant classes of degrees


Authors: Leo Harrington and Robert I. Soare
Journal: J. Amer. Math. Soc. 9 (1996), 617-666
MSC (1991): Primary 03D25
MathSciNet review: 1311821
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A set $A$ 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 $\mathcal E $ denote the structure of the computably enumerable sets under inclusion, $\mathcal E = ( \{ W_e \}_{e\in \omega}, \subseteq )$. Most previously known automorphisms $\Phi $ of the structure $\mathcal E $ of sets were effective (computable) in the sense that $\Phi $ has an effective presentation. We introduce here a new method for generating noneffective automorphisms whose presentation is $\Delta ^0_3$, and we apply the method to answer a number of long open questions about the orbits of c.e. sets under automorphisms of $\mathcal E $. 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 $n\ge 0$ the well-known degree classes $\mathbf L_n $ (the low$_n$ c.e. degrees) and $\overline {\mathbf H}_n ={\mathbf R} - {\mathbf H} _n$ (the complement of the high$_n$ c.e. degrees) are noninvariant classes.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 03D25

Retrieve articles in all journals with MSC (1991): 03D25


Additional Information

Leo Harrington
Affiliation: Department of Mathematics University of California at Berkeley Berkeley, California 94720
Email: leo@math.berkeley.edu

Robert I. Soare
Affiliation: Department of Mathematics University of Chicago 5734 University Avenue Chicago, Illinois 60637-1538; World Wide Web address: http://www.Cs.uchicago.edu/$∼$soare
Email: soare@math.uchicago.edu

DOI: http://dx.doi.org/10.1090/S0894-0347-96-00181-6
PII: S 0894-0347(96)00181-6
Received by editor(s): December 13, 1993
Additional Notes: The first author was supported by National Science Foundation Grants DMS 89-10312 and DMS 92-14048, and the second author by National Science Foundation Grants DMS 91-06714 and DMS 95-00825
Article copyright: © Copyright 1996 American Mathematical Society