Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

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 nonlow computably enumerable degrees are not invariant in $\mathcal {E}$
HTML articles powered by AMS MathViewer

by Rachel Epstein PDF
Trans. Amer. Math. Soc. 365 (2013), 1305-1345 Request permission


We study the structure of the computably enumerable (c.e.) sets, which form a lattice $\mathcal {E}$ under set inclusion. The upward closed jump classes $\overline {\mathbf {L}}_n$ and $\mathbf {H}_n$ have all been shown to be definable by a lattice-theoretic formula, except for $\overline {\mathbf {L}}_{1}$, the nonlow degrees. We say a class of c.e. degrees is invariant if it is the set of degrees of a class of c.e. sets that is invariant under automorphisms of $\mathcal E$. All definable classes of degrees are invariant. We show that $\overline {\mathbf {L}}_{1}$ is not invariant, thus proving a 1996 conjecture of Harrington and Soare that the nonlow degrees are not definable, and completing the problem of determining the definability of each jump class. We prove this by constructing a nonlow c.e. set $D$ such that for all c.e. $A\leq _\textrm {T} D$, there is a low set $B$ such that $A$ can be taken by an automorphism of $\mathcal {E}$ to $B$.
Similar Articles
  • Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D25
  • Retrieve articles in all journals with MSC (2010): 03D25
Additional Information
  • Rachel Epstein
  • Affiliation: Department of Mathematics, Faculty of Arts and Sciences, Harvard University, 1 Oxford Street, Cambridge, Massachusetts 02138
  • Email:
  • Received by editor(s): January 28, 2011
  • Received by editor(s) in revised form: April 8, 2011
  • Published electronically: July 18, 2012
  • Additional Notes: The author would like to thank Bob Soare for many helpful comments and conversations.
  • © Copyright 2012 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 365 (2013), 1305-1345
  • MSC (2010): Primary 03D25
  • DOI:
  • MathSciNet review: 3003266