zbMATH — the first resource for mathematics

Spectra of structures and relations. (English) Zbl 1116.03029
Summary: We consider embeddings of structures which preserve spectra: if \(g:{\mathcal M}\to{\mathcal S}\) with \({\mathcal S}\) computable, then \({\mathcal M}\) should have the same Turing degree spectrum (as a structure) that \(g({\mathcal M})\) has (as a relation on \({\mathcal S})\). We show that the computable dense linear order \({\mathcal L}\) is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph \({\mathcal G}\). Such structures are said to be spectrally universal. We use our results to answer a question of Goncharov, and also to characterize the possible spectra of structures as precisely the spectra of unary relations on \({\mathcal G}\). Finally, we consider the extent to which all spectra of unary relations on the structure \({\mathcal L}\) may be realized by such embeddings, offering partial results and building the first known example of a structure whose spectrum contains precisely those degrees \({\mathbf c}\) with \({\mathbf c}'\geq_T{\mathbf 0}''\).

03C57 Computable structure theory, computable model theory
03D28 Other Turing degree structures
Full Text: DOI
[1] Recursively enumerable sets and degrees (1987)
[2] Contemporary mathematics pp 65–81– (2000)
[3] Annals of Pure Applied Logic 54 pp 255–263– (1991)
[4] Annals of Pure and Applied Logic 136 pp 219–246– (2005)
[5] Proceedings of the American Mathematical Society 114 pp 545–552– (1992)
[6] Proceedings of the American Mathematical Society 122 pp 871–880– (1994) · Zbl 0805.90016
[7] Algebra and Logic 42 pp 105–111– (2003)
[8] The complexity of intrinsically r.e. subsets of existentially decidable models 55 pp 1213–1232– (1990)
[9] Computable structures and the hyperarithmetical hierarchy (2000) · Zbl 0960.03001
[10] Degrees of structures 46 pp 723–731– (1981)
[11] Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 32 pp 467–472– (1986)
[12] The -spectrum of a linear order 66 pp 470–486– (2001)
[13] Degrees coded in jumps of orderings 51 pp 1034–1042– (1986)
[14] Models and computability: Invited papers from logic colloquium ’97 259 pp 193–240– (1999)
[15] Annals of Pure and Applied Logic 93 pp 153–193– (1998)
[16] Annals of Pure and Applied Logic 52 pp 39–64– (1991)
[17] A shorter model theory (1997) · Zbl 0873.03036
[18] Annals of Pure and Applied Logic 115 pp 71–113– (2002)
[19] Handbook of recursive mathematics, vol. 1 138 pp 3–114– (1998) · Zbl 0930.03037
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.