{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T01:45:30Z","timestamp":1768009530826,"version":"3.49.0"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2568,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider embeddings of structures which preserve spectra: if <jats:italic>g<\/jats:italic> : \u2133 \u2192 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005624_inline1\"\/> with <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005624_inline1\"\/> computable, then \u2133 should have the same Turing degree spectrum (as a structure) that <jats:italic>g(\u2133)<\/jats:italic> has (as a relation on <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005624_inline1\"\/>). We show that the computable dense linear order \u2112 is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005624_inline2\"\/> Such structures are said to be <jats:italic>spectrally universal<\/jats:italic>. 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 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005624_inline2\"\/>. Finally, we consider the extent to which all spectra of unary relations on the structure \u2112 may be realized by such embeddings, offering partial results and building the first known example of a structure whose spectrum contains precisely those degrees c with <jats:italic>c\u2032 \u2265 \u03c4 0\u2033<\/jats:italic>.<\/jats:p>","DOI":"10.2178\/jsl\/1174668398","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T11:24:33Z","timestamp":1198063473000},"page":"324-348","source":"Crossref","is-referenced-by-count":12,"title":["Spectra of structures and relations"],"prefix":"10.1017","volume":"72","author":[{"given":"Valentina S.","family":"Harizanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell G.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200005624_ref017","first-page":"470\u2013486","volume":"66","author":"Miller","year":"2001","journal-title":"The -spectrum of a linear order"},{"key":"S0022481200005624_ref016","first-page":"1034\u20131042","volume":"51","author":"Knight","year":"1986","journal-title":"Degrees coded in jumps of orderings"},{"key":"S0022481200005624_ref012","volume-title":"A shorter model theory","author":"Hodges","year":"1997"},{"key":"S0022481200005624_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.02.001"},{"key":"S0022481200005624_ref006","first-page":"545\u2013552","article-title":"Orderings with \u03b1-th jump degree 0(\u03b1)","volume":"114","author":"Downey","year":"1992","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S0022481200005624_ref005","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1994-1203984-4"},{"key":"S0022481200005624_ref003","unstructured":"Csima B. F. , Harizanov V. S. , Miller R. G. , and Montalb\u00e1n A. , Computability of Fra\u00efss\u00e9 limits, to appear."},{"key":"S0022481200005624_ref002","first-page":"1213\u20131232","volume":"55","author":"Chisholm","year":"1990","journal-title":"The complexity of intrinsically r.e. subsets of existentially decidable models"},{"key":"S0022481200005624_ref001","volume-title":"Computable structures and the hyperarithmetical hierarchy","author":"Ash","year":"2000"},{"key":"S0022481200005624_ref019","first-page":"723\u2013731","volume":"46","author":"Richter","year":"1981","journal-title":"Degrees of structures"},{"key":"S0022481200005624_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90049-R"},{"key":"S0022481200005624_ref015","first-page":"193\u2013240","volume-title":"Models and computability: Invited papers from logic colloquium '97","volume":"259","author":"Khoussainov","year":"1999"},{"key":"S0022481200005624_ref004","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025971406116"},{"key":"S0022481200005624_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00059-6"},{"key":"S0022481200005624_ref010","first-page":"65\u201381","volume-title":"Contemporary mathematics","author":"Harizanov","year":"2000"},{"key":"S0022481200005624_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200005624_ref011","first-page":"71\u2013113","article-title":"Degree spectra and computable dimensions in algebraic structures","volume":"115","author":"Hirschfeldt","year":"2002","journal-title":"Annals of Pure and Applied Logic"},{"key":"S0022481200005624_ref009","first-page":"3\u2013114","volume-title":"Handbook of recursive mathematics, vol. 1","volume":"138","author":"Harizanov","year":"1998"},{"key":"S0022481200005624_ref018","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19860322514"},{"key":"S0022481200005624_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90038-N"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200005624","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T20:11:09Z","timestamp":1556741469000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200005624\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["S0022481200005624"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1174668398","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3]]}}}