×

zbMATH — the first resource for mathematics

Turing incomparability in Scott sets. (English) Zbl 1123.03039
From the introduction: H. Friedman and A. McAllister posed the question whether for every nonrecursive set \(X\) of a Scott set \({\mathcal F}\) there is a \(Y\in {\mathcal F}\) such that \(X\) and \(Y\) are Turing incomparable (see Problem 3.2 and also Problem 3.3 in [D. Cenzer and C. G. Jockusch jun., Contemp. Math. 257, 33–59 (2000; Zbl 0962.03040)]). We present a positive solution to the question, using recent results in the area of algorithmic randomness and also results on \(\Pi^0_1\) classes.

MSC:
03D28 Other Turing degree structures
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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. · Zbl 0962.03039 · doi:10.1090/conm/257/04023 · doi.org
[2] 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. · Zbl 0962.03040 · doi:10.1090/conm/257/04026 · doi.org
[3] G. J. Chaitin, Algorithmic information theory, IBM J. Res. Develop. 21 (1977), no. 4, 350 – 359. · Zbl 0362.94035 · doi:10.1147/rd.214.0350 · doi.org
[4] R. Downey and D. R. Hirschfeldt. Algorithmic randomness and complexity. to appear. · Zbl 1221.68005
[5] Rod Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bull. Symbolic Logic 12 (2006), no. 3, 411 – 491. · Zbl 1113.03037
[6] 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. · Zbl 0952.03051 · doi:10.1016/S0168-0072(96)00029-2 · doi.org
[7] D. R. Hirschfeldt, A. Nies, and F. Stephan. Using random sets as oracles. to appear. · Zbl 1128.03036
[8] Carl G. Jockusch Jr. and Robert I. Soare, \Pi \(^{0}\)\(_{1}\) classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33 – 56. · Zbl 0262.02041
[9] Antonín Kučera, On the role of 0’ in recursion theory, Logic colloquium ’86 (Hull, 1986) Stud. Logic Found. Math., vol. 124, North-Holland, Amsterdam, 1988, pp. 133 – 141. · Zbl 0645.03041 · doi:10.1016/S0049-237X(09)70655-X · doi.org
[10] 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). · Zbl 0788.68068 · doi:10.1016/0168-0072(93)90209-V · doi.org
[11] Manuel Lerman, Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93 (1971), 365 – 389. · Zbl 0193.31004 · doi:10.2307/1970779 · doi.org
[12] Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. · Zbl 0542.03023
[13] 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. · Zbl 0866.68051
[14] André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274 – 305. · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006 · doi.org
[15] 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. · Zbl 0661.03029
[16] 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. · Zbl 0661.03029
[17] Gerald E. Sacks, On suborderings of degrees of recursive unsolvability, Z. Math. Logik Grundlagen Math. 7 (1961), 46 – 56. · Zbl 0118.25202
[18] Gerald E. Sacks, On the degrees less than 0\(^{\prime}\), Ann. of Math. (2) 77 (1963), 211 – 231. · Zbl 0118.25104 · doi:10.2307/1970214 · doi.org
[19] C.-P. Schnorr, A unified approach to the definition of random sequences, Math. Systems Theory 5 (1971), 246 – 258. · Zbl 0227.62005 · doi:10.1007/BF01694181 · doi.org
[20] 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.
[21] Richard A. Shore, On the ∀∃-sentences of \?-recursion theory, Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977) Stud. Logic Foundations Math., vol. 94, North-Holland, Amsterdam-New York, 1978, pp. 331 – 353.
[22] 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. · Zbl 0667.03030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.