On the degree spectrum of a class

Authors:
Thomas Kent and Andrew E. M. Lewis

Journal:
Trans. Amer. Math. Soc. **362** (2010), 5283-5319

MSC (2010):
Primary 03D28

Published electronically:
May 4, 2010

MathSciNet review:
2657680

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For any , define , the *degree spectrum* of , to be the set of all Turing degrees such that there exists of degree . We prove a number of basic properties of the structure which is the degree spectra of classes ordered by inclusion and also study in detail some other phenomena relating to the study of classes from a degree theoretic point of view, which are brought to light as a result of this analysis.

**[DC]**D. Cenzer, classes, in the*Handbook of Computability Theory*, Studies in logic and the foundations of mathematics, vol 140, Elsevier, 1999.**[CS]**Douglas Cenzer and Rick L. Smith,*On the ranked points of a Π⁰₁ set*, J. Symbolic Logic**54**(1989), no. 3, 975–991. MR**1011184**, 10.2307/2274757**[CCS]**Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, and Stanley S. Wainer,*Members of countable Π⁰₁ classes*, Ann. Pure Appl. Logic**31**(1986), no. 2-3, 145–163. Special issue: second Southeast Asian logic conference (Bangkok, 1984). MR**854290**, 10.1016/0168-0072(86)90067-9**[CC]**Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann,*Automorphisms of the lattice of Π⁰₁ classes: perfect thin classes and anc degrees*, Trans. Amer. Math. Soc.**353**(2001), no. 12, 4899–4924. MR**1852086**, 10.1090/S0002-9947-01-02821-5**[SC]**Joshua A. Cole and Stephen G. Simpson,*Mass problems and hyperarithmeticity*, J. Math. Log.**7**(2007), no. 2, 125–143. MR**2423947**, 10.1142/S0219061307000652**[BC]**S. Barry Cooper,*Computability theory*, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR**2017461****[OD]**Osvald Demuth,*Remarks on the structure of tt-degrees based on constructive measure theory*, Comment. Math. Univ. Carolin.**29**(1988), no. 2, 233–247. MR**957390****[RD]**Rod Downey,*On Π⁰₁ classes and their ranked points*, Notre Dame J. Formal Logic**32**(1991), no. 4, 499–512 (1992). MR**1146607**, 10.1305/ndjfl/1093635924**[DH]**R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, monograph in preparation.**[JM]**C. G. Jockusch Jr. and T. G. McLaughlin,*Countable retracing functions and Π₂⁰ predicates*, Pacific J. Math.**30**(1969), 67–93. MR**0269508****[JS1]**Carl G. Jockusch Jr. and Robert I. Soare,*Π⁰₁ classes and degrees of theories*, Trans. Amer. Math. Soc.**173**(1972), 33–56. MR**0316227**, 10.1090/S0002-9947-1972-0316227-0**[JS2]**Carl G. Jockusch Jr. and Robert I. Soare,*Degrees of members of Π⁰₁ classes*, Pacific J. Math.**40**(1972), 605–616. MR**0309722****[SK]**S. C. Kleene,*Recursive predicates and quantifiers*, Trans. Amer. Math. Soc.**53**(1943), 41–73. MR**0007371**, 10.1090/S0002-9947-1943-0007371-8**[KP]**Marian Boykan Pour-El and Saul Kripke,*Deduction-preserving “recursive isomorphisms” between theories*, Bull. Amer. Math. Soc.**73**(1967), 145–148. MR**0215713**, 10.1090/S0002-9904-1967-11689-6**[AK]**Antonín Kučera,*Measure, Π⁰₁-classes and complete extensions of 𝑃𝐴*, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR**820784**, 10.1007/BFb0076224**[AL]**Andrew E. M. Lewis,*Π₁⁰ classes, strong minimal covers and hyperimmune-free degrees*, Bull. Lond. Math. Soc.**39**(2007), no. 6, 892–910. MR**2392813**, 10.1112/blms/bdm083**[MP]**D. A. Martin and M. B. Pour-El,*Axiomatizable theories with few axiomatizable extensions*, J. Symbolic Logic**35**(1970), 205–209. MR**0280374****[AN]**A. Nies, Computability and Randomness, monograph in preparation.**[HP]**M.G. Peretyakin, Finitely Axiomatizable Theories, Scientific Books, ISBN 0-306-11062-8.**[FS]**Frank Stephan,*Martin-Löf random and PA-complete sets*, Logic Colloquium ’02, Lect. Notes Log., vol. 27, Assoc. Symbol. Logic, La Jolla, CA, 2006, pp. 342–348. MR**2258714****[SS]**Stephen G. Simpson,*An extension of the recursively enumerable Turing degrees*, J. Lond. Math. Soc. (2)**75**(2007), no. 2, 287–297. MR**2340228**, 10.1112/jlms/jdl015**[SS2]**Stephen G. Simpson,*Mass problems and randomness*, Bull. Symbolic Logic**11**(2005), no. 1, 1–27. MR**2125147**, 10.2178/bsl/1107959497

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2010):
03D28

Retrieve articles in all journals with MSC (2010): 03D28

Additional Information

**Thomas Kent**

Affiliation:
Department of Mathematics, Marywood University, Scranton, Pennsylvania 18509

Email:
tfkent@marywood.edu

**Andrew E. M. Lewis**

Affiliation:
Department of Mathematics, University of Leeds, Leeds, England LS2 9JT

Email:
aemlewis@aemlewis.co.uk

DOI:
https://doi.org/10.1090/S0002-9947-10-05037-3

Keywords:
$\Pi ^0_1$ classes

Received by editor(s):
June 13, 2008

Published electronically:
May 4, 2010

Additional Notes:
The first author was supported by Marie-Curie Fellowship MIFI-CT-2006-021702.

The second author was supported by a Royal Society University Research Fellowship.

Article copyright:
© Copyright 2010
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.