Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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



On the degree spectrum of a $ \Pi^0_1$ 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 $ \mathcal{P} \subseteq 2^{\omega} $, define $ S(\mathcal{P}) $, the degree spectrum of $ \mathcal{P}$, to be the set of all Turing degrees $ \bf {a} $ such that there exists $ A\in \mathcal{P} $ of degree $ \bf {a} $. We prove a number of basic properties of the structure which is the degree spectra of $ \Pi^0_1$ classes ordered by inclusion and also study in detail some other phenomena relating to the study of $ \Pi^0_1$ classes from a degree theoretic point of view, which are brought to light as a result of this analysis.

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

  • [DC] D. Cenzer, $ \Pi^0_1$ 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 $ \Pi^0_1$ 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 $ \Pi^0_1$ 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 $ \Pi^0_1$ 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 $ \Pi^0_1$ 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 $ \Pi^0_2$ predicates, Pacific J. Math., 30, pp. 67-93, 1969. MR 0269508 (42:4403)
  • [JS1] C. Jockusch and R. Soare, $ \Pi^0_1$ 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 $ \Pi^0_1$ 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, $ \Pi^0_1$ 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, $ \Pi^0_1$ 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)

Similar Articles

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

Andrew E. M. Lewis
Affiliation: Department of Mathematics, University of Leeds, Leeds, England LS2 9JT

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.

American Mathematical Society