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

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

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]**D. Cenzer and R. Smith, The ranked points of a set,*Journal of Symbolic Logic*, 54, pp. 975-991, 1989. MR**1011184 (90j:03090)****[CCS]**D. Cenzer, P. Clote, R. Smith, R. Soare and S. Wainer, Members of countable classes,*Annals of Pure and Applied Logic*, 31, pp. 145-163, 1986. MR**854290 (88e:03064)****[CC]**P. Cholak, R. Coles, R. Downey and E. Herrmann, Automorphisms of the lattice of classes; perfect thin classes and ANC degrees,*Transactions of the American Mathematical Society*, 353 (12), pp. 4899-4924, 2001. MR**1852086 (2002f:03080)****[SC]**J. Cole and S. Simpson, Mass problems and hyperarithmeticity,*Journal of Mathematical Logic*, 7, issue 2, pp. 125-143, 2007. MR**2423947 (2009d:03099)****[BC]**S.B. Cooper,*Computability Theory*, Chapman & Hall, CRC Press, Boca Raton, FL, New York, London (2004). MR**2017461 (2005h:03001)****[OD]**O. Demuth, Remarks on the structure of tt-degrees based on constructive measure theory,*Comment. Math. Carolinae*, 29, pp. 233-247, 1988. MR**957390 (89k:03049)****[RD]**R. Downey, On classes and their ranked points,*Notre Dame Journal of Formal Logic*, 32, pp. 499-512, 1991. MR**1146607 (93a:03046)****[DH]**R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, monograph in preparation.**[JM]**C. Jockusch and T. McLaughlin, Countable retracing functions and predicates,*Pacific J. Math.*, 30, pp. 67-93, 1969. MR**0269508 (42:4403)****[JS1]**C. Jockusch and R. Soare, classes and degrees of theories,*Transactions of the American Mathematical Society*, 173, pp. 33-56, 1972. MR**0316227 (47:4775)****[JS2]**C. Jockusch and R. Soare, Degrees of members of classes,*Pacific Journal of Mathematics*, 40, pp. 605-616, 1972. MR**0309722 (46:8827)****[SK]**S. Kleene, Recursive predicates and quantifiers,*Transactions of the American Mathematical Society*, 53, pp. 41-73, 1943. MR**0007371 (4:126b)****[KP]**S. Kripke and M.B Pour-El, Deduction-preserving ``recursive isomorphisms'' between theories,*Bulletin of the American Mathematical Society*, 73, pp. 145-148, 1967. MR**0215713 (35:6548)****[AK]**A. Kucera, Measure, classes and complete extensions of PA, in*Recursion Theory Week (Proceedings Oberwolfach 1984)*, Lecture Notes in Mathematics, vol 1141, pp. 245-259, 1985. MR**820784 (87e:03102)****[AL]**A.E.M. Lewis, classes, strong minimal covers and hyperimmune-free degrees,*Bull. Lond. Math. Soc.*, 39, pp. 892-910, 2007. MR**2392813 (2009b:03113)****[MP]**D. Martin and M.B. Pour-El, Axiomatixable theories with few axiomatizable extensions,*Journal of Symbolic Logic*, 35 (2), pp. 205-209, 1970. MR**0280374 (43:6094)****[AN]**A. Nies, Computability and Randomness, monograph in preparation.**[HP]**M.G. Peretyakin, Finitely Axiomatizable Theories, Scientific Books, ISBN 0-306-11062-8.**[FS]**F. Stephan, Martin-Löf random and PA-complete sets. (TR 58)*ASL Lecture Notes in Logic*, 27, pp. 342-348, 2006. MR**2258714 (2007h:03088)****[SS]**S. Simpson, An extension of the recursively enumerable Turing degrees,*Journal of the London Mathematical Society*, 75, pp. 287-297, 2007. MR**2340228 (2008d:03041)****[SS2]**S. Simpson, Mass problems and randomness,*Bulletin of Symbolic Logic*, 11, pp. 1-27, 2005. MR**2125147 (2005k:03097)**

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.