How to Order

For AMS eBook frontlist subscriptions or backfile collection purchases:

   1a. To purchase any ebook backfile or to subscibe to the current year of Contemporary Mathematics, please download this required license agreement,

   1b. To subscribe to the current year of Memoirs of the AMS, please download this required license agreement.

   2. Complete and sign the license agreement.

   3. Email, fax, or send via postal mail to:

Customer Services
American Mathematical Society
201 Charles Street Providence, RI 02904-2213  USA
Phone: 1-800-321-4AMS (4267)
Fax: 1-401-455-4046

Visit the AMS Bookstore for individual volume purchases.

Browse the current eBook Collections price list

Powered by MathJax
  Remote Access

Degree Spectra of Relations on a Cone

About this Title

Matthew Harrison-Trainor

Publication: Memoirs of the American Mathematical Society
Publication Year: 2018; Volume 253, Number 1208
ISBNs: 978-1-4704-2839-6 (print); 978-1-4704-4411-2 (online)
Published electronically: March 29, 2018
Keywords:computable structure, degree spectrum of a relation, cone of Turing degrees

View full volume PDF

View other years and numbers:

Table of Contents


  • Chapter 1. Introduction
  • Chapter 2. Preliminaries
  • Chapter 3. Degree Spectra between the C.E. Degrees and the D.C.E. Degrees
  • Chapter 4. Degree Spectra of Relations on the Naturals
  • Chapter 5. A “Fullness” Theorem for 2-\cea Degrees
  • Chapter 6. Further Questions
  • Appendix A. Relativizing Harizanov’s Theorem on C.E. Degrees


Let be a mathematical structure with an additional relation . We are interested in the degree spectrum of , either among computable copies of when is a âĂIJnaturalâĂİ structure, or (to make this rigorous) among copies of computable in a large degree d. We introduce the partial order of degree spectra on a cone and begin the study of these objects. Using a result of HarizanovâĂŤthat, assuming an effectiveness condition on and , if is not intrinsically computable, then its degree spectrum contains all c.e. degreesâĂŤwe see that there is a minimal non-trivial degree spectrum on a cone, consisting of the c.e. degrees. We show that this does not generalize to d.c.e. degrees by giving an example of two incomparable degree spectra on a cone. We also give a partial answer to a question of Ash and Knight: they asked whether (subject to some effectiveness conditions) a relation which is not intrinsically must have a degree spectrum which contains all of the -CEA degrees. We give a positive answer to this question for by showing that any degree spectrum on a cone which strictly contains the degrees must contain all of the 2-CEA degrees. We also investigate the particular case of degree spectra on the structure . This work represents the beginning of an investigation of the degree spectra of âĂIJnaturalâĂİ structures, and we leave many open questions to be answered.

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