{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T02:33:22Z","timestamp":1768012402325,"version":"3.49.0"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":4302,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2002,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give some new examples of possible degree spectra of invariant relations on \u0394<jats:sub arrange=\"stack\">2<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>-categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a \u0394<jats:sub arrange=\"stack\">2<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>-categorical computable structure is either intrinsically computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses [23] to establish the same result for computable relations on computable linear orderings.<\/jats:p><jats:p>We also place our results in the context of the study of what types of degree-theoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of \u0394<jats:sub arrange=\"stack\">2<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>-categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode [3] to extend results of Harizanov [14].<\/jats:p>","DOI":"10.2178\/jsl\/1190150105","type":"journal-article","created":{"date-parts":[[2007,12,13]],"date-time":"2007-12-13T19:13:31Z","timestamp":1197573211000},"page":"697-720","source":"Crossref","is-referenced-by-count":7,"title":["Degree spectra of relations on computable structures in the presence of \u0394<sub>2<\/sub><sup>0<\/sup>isomorphisms"],"prefix":"10.1017","volume":"67","author":[{"given":"Denis R.","family":"Hirschfeldt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200009695_ref022","volume-title":"Elementary induction on abstract structures","volume":"77","author":"Moschovakis","year":"1974"},{"key":"S0022481200009695_ref023","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19860322514"},{"key":"S0022481200009695_ref018","unstructured":"Hirschfeldt D. R. and White W. M. , Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures, to appear."},{"key":"S0022481200009695_ref005","doi-asserted-by":"crossref","unstructured":"Downey R. G. , Computahility theory and linear orderings, in [9], pp. 823\u2013976.","DOI":"10.1016\/S0049-237X(98)80047-5"},{"key":"S0022481200009695_ref016","author":"Hirschfeldt","journal-title":"Degree spectra of intrinsically c. e. relations"},{"key":"S0022481200009695_ref013","unstructured":"Harizanov V. S. , Degree spectrum of a recursive relation on a recursive structure, Ph. d. thesis , University of Wisconsin, Madison, Wisconsin, 1987."},{"key":"S0022481200009695_ref021","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565670.009"},{"key":"S0022481200009695_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200009695_ref008","doi-asserted-by":"crossref","unstructured":"Ershov Y. L. and Goncharov S. S. , Elementary theories and their constructive models, in [9], pp. 115\u2013166.","DOI":"10.1016\/S0049-237X(98)80003-7"},{"key":"S0022481200009695_ref003","first-page":"26","volume-title":"Aspects of effective algebra (Clayton, 1979)","author":"Ash","year":"1981"},{"key":"S0022481200009695_ref019","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"S0022481200009695_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90097-6"},{"key":"S0022481200009695_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00059-6"},{"key":"S0022481200009695_ref024","first-page":"572","volume":"46","author":"Remmel","year":"1981","journal-title":"Recursive isomorphism types of recursive Boolean algebras"},{"key":"S0022481200009695_ref006","unstructured":"Downey R. G. , Goncharov S. S. , and Hirschfeldt D. R. , Degree spectra of relations on Boolean algebras, to appear."},{"key":"S0022481200009695_ref026","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19960420139"},{"key":"S0022481200009695_ref009","volume-title":"Handbook of recursive mathematics","volume":"138","author":"Ershov","year":"1998"},{"key":"S0022481200009695_ref001","doi-asserted-by":"crossref","unstructured":"Ash C. J. , Isomorphic recursive structures, in [9], pp. 167\u2013182.","DOI":"10.1016\/S0049-237X(98)80004-9"},{"key":"S0022481200009695_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(96)00011-5"},{"key":"S0022481200009695_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90005-7"},{"key":"S0022481200009695_ref007","first-page":"32","volume":"859","author":"Epstein","year":"1981"},{"key":"S0022481200009695_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00056-0"},{"key":"S0022481200009695_ref010","doi-asserted-by":"crossref","unstructured":"Goncharov S. S. , Autostable models and algorithmic dimensions, in [9], pp. 261\u2013288.","DOI":"10.1016\/S0049-237X(98)80007-4"},{"key":"S0022481200009695_ref011","first-page":"4","volume-title":"Mathematical logic and the theory of algorithms","volume":"2","author":"Goncharov","year":"1982"},{"key":"S0022481200009695_ref012","doi-asserted-by":"crossref","unstructured":"Harizanov V. S. , Pure computable model theory, in [9], pp. 3\u2013114.","DOI":"10.1016\/S0049-237X(98)80002-5"},{"key":"S0022481200009695_ref017","volume-title":"Annals of Pure and Applied Logic","author":"Hirschfeldt"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200009695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T17:51:40Z","timestamp":1737654700000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200009695\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,6]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,6]]}},"alternative-id":["S0022481200009695"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1190150105","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,6]]}}}