On the degree spectrum of a $\Pi ^0_1$ class
HTML articles powered by AMS MathViewer
- by Thomas Kent and Andrew E. M. Lewis PDF
- Trans. Amer. Math. Soc. 362 (2010), 5283-5319 Request permission
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
- D. Cenzer, $\Pi ^0_1$ classes, in the Handbook of Computability Theory, Studies in logic and the foundations of mathematics, vol 140, Elsevier, 1999.
- Douglas Cenzer and Rick L. Smith, On the ranked points of a $\Pi ^0_1$ set, J. Symbolic Logic 54 (1989), no. 3, 975–991. MR 1011184, DOI 10.2307/2274757
- Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, and Stanley S. Wainer, Members of countable $\Pi ^0_1$ classes, Ann. Pure Appl. Logic 31 (1986), no. 2-3, 145–163. Special issue: second Southeast Asian logic conference (Bangkok, 1984). MR 854290, DOI 10.1016/0168-0072(86)90067-9
- Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann, Automorphisms of the lattice of $\Pi ^0_1$ classes: perfect thin classes and anc degrees, Trans. Amer. Math. Soc. 353 (2001), no. 12, 4899–4924. MR 1852086, DOI 10.1090/S0002-9947-01-02821-5
- Joshua A. Cole and Stephen G. Simpson, Mass problems and hyperarithmeticity, J. Math. Log. 7 (2007), no. 2, 125–143. MR 2423947, DOI 10.1142/S0219061307000652
- S. Barry Cooper, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2017461
- 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
- Rod Downey, On $\Pi ^0_1$ classes and their ranked points, Notre Dame J. Formal Logic 32 (1991), no. 4, 499–512 (1992). MR 1146607, DOI 10.1305/ndjfl/1093635924
- R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, monograph in preparation.
- C. G. Jockusch Jr. and T. G. McLaughlin, Countable retracing functions and $\Pi _{2}{}^{0}$ predicates, Pacific J. Math. 30 (1969), 67–93. MR 269508
- Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- Carl G. Jockusch Jr. and Robert I. Soare, Degrees of members of $\Pi ^{0}_{1}$ classes, Pacific J. Math. 40 (1972), 605–616. MR 309722
- S. C. Kleene, Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53 (1943), 41–73. MR 7371, DOI 10.1090/S0002-9947-1943-0007371-8
- Marian Boykan Pour-El and Saul Kripke, Deduction-preserving “recursive isomorphisms” between theories, Bull. Amer. Math. Soc. 73 (1967), 145–148. MR 215713, DOI 10.1090/S0002-9904-1967-11689-6
- Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
- Andrew E. M. Lewis, $\Pi _1^0$ classes, strong minimal covers and hyperimmune-free degrees, Bull. Lond. Math. Soc. 39 (2007), no. 6, 892–910. MR 2392813, DOI 10.1112/blms/bdm083
- D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205–209. MR 280374, DOI 10.2307/2270510
- A. Nies, Computability and Randomness, monograph in preparation.
- M.G. Peretyakin, Finitely Axiomatizable Theories, Scientific Books, ISBN 0-306-11062-8.
- 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
- Stephen G. Simpson, An extension of the recursively enumerable Turing degrees, J. Lond. Math. Soc. (2) 75 (2007), no. 2, 287–297. MR 2340228, DOI 10.1112/jlms/jdl015
- Stephen G. Simpson, Mass problems and randomness, Bull. Symbolic Logic 11 (2005), no. 1, 1–27. MR 2125147, DOI 10.2178/bsl/1107959497
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
- MR Author ID: 748032
- Email: aemlewis@aemlewis.co.uk
- 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. - © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 362 (2010), 5283-5319
- MSC (2010): Primary 03D28
- DOI: https://doi.org/10.1090/S0002-9947-10-05037-3
- MathSciNet review: 2657680