Abstract
A jump inversion theorem for the degree spectra is presented. For a structure which degree spectrum is a subset of the jump spectrum of a structure
, a structure
is constructed as a Marker’s extension of
such that the jump spectrum of
is exactly the degree spectrum of
and the degree spectrum of
is a subset of the degree spectrum of
.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ash, C.J., Jockush, C., Knight, J.F.: Jumps of orderings. Trans. Amer. Math. Soc. 319, 573–599 (1990)
Coles, R., Downey, R., Slaman, T.: Every set has a least jump enumeration. Bulletin London Math. Soc 62, 641–649 (2000)
Cooper, S.B.: Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ 2 sets are dense. J. Symbolic Logic 49, 503–513 (1984)
Downey, R.G., Knight, J.F.: Orderings with αth jump degree 0(α). Proc. Amer. Math. Soc. 114, 545–552 (1992)
Gavryushkin, A.N.: On complexity of Ehrenfeucht Theories with computable model. In: Beckmann, A., Berger, U., Löwe, B., Tucker, J. (eds.) Logical Approaches to Computational barriers CiE2006, University of Wales Swansea, Report Series, No. CSR 7-2006, pp. 105–108 (2006)
Goncharov, S., Khoussainov, B.: Complexity of categorical theories with computable models. Algbra and Logic 43(6), 365–373 (2004)
Knight, J.F.: Degrees coded in jumps of orderings. J. Symbolic Logic 51, 1034–1042 (1986)
Marker, D.: Non Σ n -axiomatizable almost strongly minimal theories. J. Symbolic Logic 54(3), 921–927 (1989)
Richter, L.J.: Degrees of structures. J. Symbolic Logic 46, 723–731 (1981)
Soskov, I.N.: A jump inversion theorem for the enumeration jump. Arch. Math. Logic 39, 417–437 (2000)
Soskov, I.N.: Degree spectra and co-spectra of structures. Ann. Univ. Sofia 96, 45–68 (2004)
Soskov, I.N.: The Jump Spectra are Spectra (in preparation)
Soskova, A.A.: Minimal pairs and quasi-minimal degrees for the joint spectra of structures. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol. 3526, pp. 451–460. Springer, Heidelberg (2005)
Soskova, A.A.: Relativized degree spectra. In: Beckmann, A., Berger, U., Löwe, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol. 3988, pp. 546–555. Springer, Heidelberg (2006)
Soskova, A.A., Soskov, I.N.: Co-spectra of joint spectra of structures. Ann. Univ. Sofia 96, 35–44 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Soskova, A.A. (2007). A Jump Inversion Theorem for the Degree Spectra. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds) Computation and Logic in the Real World. CiE 2007. Lecture Notes in Computer Science, vol 4497. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73001-9_76
Download citation
DOI: https://doi.org/10.1007/978-3-540-73001-9_76
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73000-2
Online ISBN: 978-3-540-73001-9
eBook Packages: Computer ScienceComputer Science (R0)