Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-24T05:41:01.475Z Has data issue: false hasContentIssue false
  • English
  • Français

THE COMPLEMENTS OF LOWER CONES OF DEGREES AND THE DEGREE SPECTRA OF STRUCTURES

Published online by Cambridge University Press:  15 August 2016

URI ANDREWS ,
MINGZHONG CAI ,
ISKANDER SH. KALIMULLIN ,
STEFFEN LEMPP ,
JOSEPH S. MILLER  and
ANTONIO MONTALBÁN
URI ANDREWS
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN 480 LINCOLN DR. MADISON, WI 53706, USAE-mail: [email protected]: www.math.wisc.edu/∼andrews
MINGZHONG CAI
Affiliation:
DEPARTMENT OF MATHEMATICS DARTMOUTH COLLEGE HANOVER, NH 03755, USAE-mail: [email protected]: math.dartmouth.edu/∼cai
ISKANDER SH. KALIMULLIN
Affiliation:
INSTITUTE OF MATHEMATICS AND MECHANICS KAZAN FEDERAL UNIVERSITY KREMLEVSKAYA ST. 18 420008 KAZAN, RUSSIAE-mail: [email protected]: kpfu.ru/main?p_id=10721
STEFFEN LEMPP
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN 480 LINCOLN DR. MADISON, WI 53706, USAE-mail: [email protected]: www.math.wisc.edu/∼lempp
JOSEPH S. MILLER
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN 480 LINCOLN DR. MADISON, WI 53706, USAE-mail: [email protected]: www.math.wisc.edu/∼jmiller
ANTONIO MONTALBÁN
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA-BERKELEY EVANS HALL #3840 BERKELEY, CA 94720, USAE-mail: [email protected]: www.math.berkeley.edu/∼antonio
Get access Rights & Permissions [Opens in a new window]

Abstract

We study Turing degrees a for which there is a countable structure ${\cal A}$ whose degree spectrum is the collection {x : x ≰ a}. In particular, for degrees a from the interval [0′, 0″], such a structure exists if a′ = 0″, and there are no such structures if a″ > 0‴.

Keywords

algebraic structuresturing degreesdegree spectracomputably enumerable (c.e.) setsfamilies of c.e. sets
Type
Articles
Information
The Journal of Symbolic Logic , Volume 81 , Issue 3 , September 2016 , pp. 997 - 1006
Copyright
Copyright © The Association for Symbolic Logic 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Cai, M. and Shore, R., Domination, forcing, array nonrecursiveness and relative recursive enumerability, this Journal, vol. 77 (2012), pp. 33–48.Google Scholar
Hirschfeldt, D. R., Khoussainov, B., Shore, R. A., and Slinko, A. M., Degree spectra and computable dimensions in algebraic structures . Annals of Pure and Applied Logic, vol. 115 (2002), no. 1–3, pp. 71–113.Google Scholar
Kalimullin, I. S., Spectra of degrees of some structures . Algebra Logika, vol. 46 (2007), no. 6, pp. 729–744.CrossRefGoogle Scholar
Kalimullin, I. S., Almost computably enumerable families of sets . Sbornik: Mathematics, vol. 199 (2008), no. 10, pp. 1451–1458.Google Scholar
Kalimullin, I. S., Restrictions on the degree spectra of algebraic structures . Siberian Mathematical Journal, vol. 49 (2008), no. 6, pp. 1034–1043.CrossRefGoogle Scholar
Kalimullin, I., Khoussainov, B., and Melnikov, A., Limitwise monotonic sequences and degree spectra of structures . Proceedings of the American Mathematical Society, vol. 141 (2013), pp. 3275–3289.Google Scholar
Knight, J. F., Degrees coded in jumps of orderings, this Journal, vol. 51 (1986), no. 4, pp. 1034–1042.Google Scholar
Rogers, H. Jr., Theory of Recursive Functions and Effective Computability, McGraw Hill, New York, 1968.Google Scholar
de Leeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N., Computability by probabilistic machines , Automata Studies: Annals of Mathematics Studies, pp. 183–212, no. 34, Princeton University Press, Princeton, N J, 1956.Google Scholar
Miller, R., The ${\rm{\Delta }}_2^0$ -spectrum of a linear order, this Journal, vol. 66 (2001), no. 2, pp. 470–486.Google Scholar
Robinson, R. W., Interpolation and embedding in the recursively enumerable degrees . Annals of Mathematics, vol. 93 (1971), pp. 285–314.Google Scholar
Slaman, T. A., Relative to any nonrecursive set . Proceedings of the American Mathematical Society, vol. 126 (1998), no. 7, pp. 2117–2122.CrossRefGoogle Scholar
Wehner, S., Enumerations, countable structures and Turing degrees . Proceedings of the American Mathematical Society, vol. 126 (1998), no. 7, pp. 2131–2139.Google Scholar