Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.83.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The $\Delta _3^0$-automorphism method and noninvariant classes of degrees
HTML articles powered by AMS MathViewer

by Leo Harrington and Robert I. Soare PDF
J. Amer. Math. Soc. 9 (1996), 617-666 Request permission

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>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
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
  • 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
  • © Copyright 1996 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 9 (1996), 617-666
  • MSC (1991): Primary 03D25
  • DOI: https://doi.org/10.1090/S0894-0347-96-00181-6
  • MathSciNet review: 1311821