The Slaman-Wehner theorem in higher recursion theory
HTML articles powered by AMS MathViewer
- by Noam Greenberg, Antonio Montalbán and Theodore A. Slaman PDF
- Proc. Amer. Math. Soc. 139 (2011), 1865-1869 Request permission
Abstract:
Slaman and Wehner have independently shown that there is a countable structure whose degree spectrum consists of the nonzero Turing degrees. We show that the analogue fails in the degrees of constructibility. While we do not settle the problem for the hyperdegrees, we show that every almost computable structure, in the sense of Kalimullin, has a copy computable from Kleene’s $\mathcal {O}$.References
- Barbara F. Csima and Iskander S. Kalimullin, Degree spectra and immunity properties, MLQ Math. Log. Q. 56 (2010), no. 1, 67–77. MR 2598838, DOI 10.1002/malq.200910001
- Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller, and Reed Solomon, Enumerations in computable structure theory, Ann. Pure Appl. Logic 136 (2005), no. 3, 219–246. MR 2169684, DOI 10.1016/j.apal.2005.02.001
- Valentina S. Harizanov, Pure computable model theory, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114. MR 1673621, DOI 10.1016/S0049-237X(98)80002-5
- Iskander Sh. Kalimullin. Some notes on degree spectra of structures. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, Computation and Logic in the Real World, volume 4497 of Lecture Notes in Computer Science, pages 389–397. Computability in Europe, Springer, 2007.
- André O. Nies. Randomness and computability: five questions. To appear in Studying randomness through computation, H. Zenil (ed.), World Scientific.
- Julia F. Knight, Degrees coded in jumps of orderings, J. Symbolic Logic 51 (1986), no. 4, 1034–1042. MR 865929, DOI 10.2307/2273915
- Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723–731. MR 641486, DOI 10.2307/2273222
- Theodore A. Slaman, Relative to any nonrecursive set, Proc. Amer. Math. Soc. 126 (1998), no. 7, 2117–2122. MR 1443408, DOI 10.1090/S0002-9939-98-04307-X
- Stephan Wehner, Enumerations, countable structures and Turing degrees, Proc. Amer. Math. Soc. 126 (1998), no. 7, 2131–2139. MR 1443415, DOI 10.1090/S0002-9939-98-04314-7
Additional Information
- Noam Greenberg
- Affiliation: School of Mathematics, Statistics and Operations Research, Victoria University, Wellington, New Zealand
- MR Author ID: 757288
- ORCID: 0000-0003-2917-3848
- Email: greenberg@msor.vuw.ac.nz
- Antonio Montalbán
- Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, Illinois 60637
- Email: antonio@math.uchicago.edu
- Theodore A. Slaman
- Affiliation: Department of Mathematics, University of California Berkeley, Berkeley, California 94720-3840
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
- Received by editor(s): May 12, 2010
- Published electronically: November 23, 2010
- Additional Notes: The first author’s research was partially supported by the Marsden fund of New Zealand.
The second author’s research was partially supported by NSF grant DMS-0901169
The third author’s research was partially supported by NSF award DMS-1001551 and by the John Templeton Foundation. - Communicated by: Julia Knight
- © Copyright 2010 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 139 (2011), 1865-1869
- MSC (2010): Primary 03C57, 03D60; Secondary 03D45
- DOI: https://doi.org/10.1090/S0002-9939-2010-10693-7
- MathSciNet review: 2763773