On the degree spectrum of a Π⁰₁ class

Kent, Thomas; Lewis, Andrew

doi:10.1090/S0002-9947-10-05037-3

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