Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)

     

On the degree spectrum of a $ \Pi^0_1$ class

Author(s): Thomas Kent; Andrew E. M. Lewis
Journal: Trans. Amer. Math. Soc. 362 (2010), 5283-5319.
MSC (2010): Primary 03D28
Posted: May 4, 2010
MathSciNet review: 2657680
Retrieve article in: PDF

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:

[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
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: 10.1090/S0002-9947-10-05037-3
PII: S 0002-9947(10)05037-3
Keywords: $\Pi ^0_1$ classes
Received by editor(s): June 13, 2008
Posted: 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.
Copyright of article: Copyright 2010, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia