Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Turing incomparability in Scott sets

Authors: Antonín Kucera and Theodore A. Slaman
Journal: Proc. Amer. Math. Soc. 135 (2007), 3723-3731
MSC (2000): Primary 03D28
Published electronically: June 22, 2007
MathSciNet review: 2336589
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For every Scott set $ \mathcal F$ and every nonrecursive set $ X$ in $ \mathcal F$, there is a $ Y \in \mathcal F$ such that $ X$ and $ Y$ are Turing incomparable.

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

  • 1. Klaus Ambos-Spies and Antonín Kucera.
    Randomness in computability theory.
    In Computability theory and its applications (Boulder, CO, 1999), volume 257 of Contemp. Math., pages 1-14. Amer. Math. Soc., Providence, RI, 2000. MR 1770730 (2001d:03112)
  • 2. Douglas Cenzer and Carl G. Jockusch, Jr.
    $ \Pi\sb 1\sp 0$ classes--structure and applications.
    In Computability theory and its applications (Boulder, CO, 1999), volume 257 of Contemp. Math., pages 39-59. Amer. Math. Soc., Providence, RI, 2000. MR 1770733 (2001h:03074)
  • 3. G. J. Chaitin.
    Algorithmic information theory.
    IBM J. Res. Develop., 21:350-359, 496, 1977. MR 0456932 (56:15151)
  • 4. R. Downey and D. R. Hirschfeldt.
    Algorithmic randomness and complexity. to appear.
  • 5. R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn.
    Calibrating randomness.
    Bull. Symbolic Logic 12:411-491 (2006). MR 2248591
  • 6. Marcia J. Groszek and Theodore A. Slaman.
    $ {\Pi}\sp 0\sb 1$ classes and minimal degrees.
    Ann. Pure Appl. Logic, 87(2):117-144, 1997.
    Logic Colloquium '95 Haifa. MR 1490050 (99f:03058)
  • 7. D. R. Hirschfeldt, A. Nies, and F. Stephan.
    Using random sets as oracles.
    to appear.
  • 8. Carl G. Jockusch, Jr. and Robert I. Soare.
    $ \Pi_1^0$ classes and degrees of theories.
    Trans. Amer. Math. Soc., 173:33-56, 1972. MR 0316227 (47:4775)
  • 9. Antonín Kucera.
    On the role of $ {\bf0}'$ in recursion theory.
    In Logic colloquium '86 (Hull, 1986), volume 124 of Stud. Logic Found. Math., pages 133-141. North-Holland, Amsterdam, 1988. MR 922107 (89b:03070)
  • 10. Antonín Kucera.
    On relative randomness.
    Ann. Pure Appl. Logic, 63(1):61-67, 1993.
    9th International Congress of Logic, Methodology and Philosophy of Science (Uppsala, 1991). MR 1238109 (95c:03103)
  • 11. M. Lerman.
    Initial segments of the degrees of unsolvability.
    Ann. of Math., 93:311-389, 1971. MR 0307893 (46:7008)
  • 12. M. Lerman.
    Degrees of Unsolvability.
    Perspectives in Mathematical Logic. Springer-Verlag, Heidelberg, 1983.
    307 pages. MR 708718 (85h:03044)
  • 13. Ming Li and Paul Vitányi.
    An introduction to Kolmogorov complexity and its applications.
    Graduate Texts in Computer Science. Springer-Verlag, New York, second edition, 1997. MR 1438307 (97k:68086)
  • 14. André Nies.
    Lowness properties and randomness.
    Adv. Math., 197(1):274-305, 2005. MR 2166184 (2006j:68052)
  • 15. Piergiorgio Odifreddi.
    Classical recursion theory, volume 125 of Studies in Logic and the Foundations of Mathematics.
    North-Holland Publishing Co., Amsterdam, 1989.
    The theory of functions and sets of natural numbers, With a foreword by G. E. Sacks. MR 982269 (90d:03072)
  • 16. Piergiorgio Odifreddi.
    Classical recursion theory. Vol. II, volume 143 of Studies in Logic and the Foundations of Mathematics.
    North-Holland Publishing Co., Amsterdam, 1999. MR 982269 (90d:03072)
  • 17. Gerald E. Sacks.
    On suborderings of degrees of recursive unsolvability.
    Z. Math. Logik Grundlag. Math., 17:46-56, 1961. MR 0131973 (24:A1820)
  • 18. Gerald E. Sacks.
    On the degrees less than 0$ '$.
    Ann. of Math., 77:211-231, 1963. MR 0146078 (26:3604)
  • 19. C.-P. Schnorr.
    A unified approach to the definition of random sequences.
    Math. Systems Theory, 5:246-258, 1971. MR 0354328 (50:6808)
  • 20. Dana Scott.
    Algebras of sets binumerable in complete extensions of arithmetic.
    In Recursive Function Theory, volume 5 of Proceedings of Symposia in Pure Mathematics, pages 117-121, American Mathematical Society, Providence, R.I., 1962. MR 0141595 (25:4993)
  • 21. Richard A. Shore.
    On the $ \forall\exists$-sentences of $ \alpha$-recursion theory.
    In R. O. Gandy, J. Fenstad and G. E. Sacks, editors, Generalized Recursion Theory II, volume 94 of Stud. Logic Foundations Math., pages 331-354, Amsterdam, 1978. North-Holland Publishing Co. MR 516943 (80e:03055)
  • 22. Robert I. Soare.
    Recursively Enumerable Sets and Degrees.
    Perspectives in Mathematical Logic, Omega Series. Springer-Verlag, Heidelberg, 1987. MR 882921 (88m:03003)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D28

Retrieve articles in all journals with MSC (2000): 03D28

Additional Information

Antonín Kucera
Affiliation: Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic

Theodore A. Slaman
Affiliation: Department of Mathematics, The University of California, Berkeley, Berkeley, California 94720-3840

Keywords: Scott set, Turing degree, $K$-trivial, low for random
Received by editor(s): February 20, 2006
Received by editor(s) in revised form: August 14, 2006
Published electronically: June 22, 2007
Additional Notes: The first author was partially supported by the Research Project of the Ministry of Education of the Czech Republic MSM0021620838
The second author was partially supported by NSF grant DMS-0501167.
Communicated by: Julia Knight
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society