Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

Turing incomparability in Scott sets

Author(s): Antonín Kucera; Theodore A. Slaman
Journal: Proc. Amer. Math. Soc. 135 (2007), 3723-3731.
MSC (2000): Primary 03D28
Posted: June 22, 2007
MathSciNet review: 2336589
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

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

References:

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
Email: kucera@ksi.mff.cuni.cz

Theodore A. Slaman
Affiliation: Department of Mathematics, The University of California, Berkeley, Berkeley, California 94720-3840
Email: slaman@math.berkeley.edu

DOI: 10.1090/S0002-9939-07-08871-5
PII: S 0002-9939(07)08871-5
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
Posted: 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
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|