Turing incomparability in Scott sets

Kučera, Antonín; Slaman, Theodore

doi:10.1090/S0002-9939-07-08871-5

Turing incomparability in Scott sets
HTML articles powered by AMS MathViewer

by Antonín Kučera and Theodore A. Slaman

Proc. Amer. Math. Soc. 135 (2007), 3723-3731

DOI: https://doi.org/10.1090/S0002-9939-07-08871-5

Published electronically: June 22, 2007

PDF | Request permission

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

Klaus Ambos-Spies and Antonín Kučera, Randomness in computability theory, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 1–14. MR 1770730, DOI 10.1090/conm/257/04023
Douglas Cenzer and Carl G. Jockusch Jr., $\Pi _1^0$ classes—structure and applications, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 39–59. MR 1770733, DOI 10.1090/conm/257/04026
G. J. Chaitin, Algorithmic information theory, IBM J. Res. Develop. 21 (1977), no. 4, 350–359. MR 456932, DOI 10.1147/rd.214.0350
R. Downey and D. R. Hirschfeldt. Algorithmic randomness and complexity. to appear.
Rod Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bull. Symbolic Logic 12 (2006), no. 3, 411–491. MR 2248591
Marcia J. Groszek and Theodore A. Slaman, $\Pi ^0_1$ classes and minimal degrees, Ann. Pure Appl. Logic 87 (1997), no. 2, 117–144. Logic Colloquium ’95 Haifa. MR 1490050, DOI 10.1016/S0168-0072(96)00029-2
D. R. Hirschfeldt, A. Nies, and F. Stephan. Using random sets as oracles. to appear.
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
Antonín Kučera, On the role of ${\bf 0}’$ in recursion theory, Logic colloquium ’86 (Hull, 1986) Stud. Logic Found. Math., vol. 124, North-Holland, Amsterdam, 1988, pp. 133–141. MR 922107, DOI 10.1016/S0049-237X(09)70655-X
Antonín Kučera, On relative randomness, Ann. Pure Appl. Logic 63 (1993), no. 1, 61–67. 9th International Congress of Logic, Methodology and Philosophy of Science (Uppsala, 1991). MR 1238109, DOI 10.1016/0168-0072(93)90209-V
Manuel Lerman, Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93 (1971), 365–389. MR 307893, DOI 10.2307/1970779
Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 2nd ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR 1438307, DOI 10.1007/978-1-4757-2606-0
André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
Gerald E. Sacks, On suborderings of degrees of recursive unsolvability, Z. Math. Logik Grundlagen Math. 7 (1961), 46–56. MR 131973, DOI 10.1002/malq.19610070109
Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 146078, DOI 10.2307/1970214
C.-P. Schnorr, A unified approach to the definition of random sequences, Math. Systems Theory 5 (1971), 246–258. MR 354328, DOI 10.1007/BF01694181
Dana Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117–121. MR 0141595
Richard A. Shore, On the $\forall \exists$-sentences of $\alpha$-recursion theory, Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977) Studies in Logic and the Foundations of Mathematics, vol. 94, North-Holland, Amsterdam-New York, 1978, pp. 331–353. MR 516943
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7