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 degreesHTML articles powered by AMS MathViewer

by Leo Harrington and Robert I. Soare
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