{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:32Z","timestamp":1777516772556,"version":"3.51.4"},"reference-count":11,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2018,2,15]],"date-time":"2018-02-15T00:00:00Z","timestamp":1518652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2018,10,24]]},"abstract":"<jats:p>Downey, Khoussainov, Miller, and Yu examined degree spectra of unary relations on the structure [Formula: see text]. We extend their results in several directions. First, we show that the degree spectrum of any unary relation on [Formula: see text] contains only the computable degree or consists of exactly the [Formula: see text] degrees. We then show, using results from combinatorics, that the degree spectrum of an n-ary relation on [Formula: see text] either contains only the computable degree or contains all c.e. degrees. Finally, we examine unary relations on general computable ordinals and show that the degree spectrum always contains a maximum degree and that degree is always a (possibly infinite) iterate of the jump.<\/jats:p>","DOI":"10.3233\/com-180086","type":"journal-article","created":{"date-parts":[[2018,2,16]],"date-time":"2018-02-16T11:03:38Z","timestamp":1518779018000},"page":"349-365","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":2,"title":["Degrees of relations on ordinals"],"prefix":"10.1177","volume":"7","author":[{"given":"Matthew","family":"Wright","sequence":"first","affiliation":[{"name":"Dropbox, Inc., United States."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2018,2,15]]},"reference":[{"key":"ref001","unstructured":"C.J.\u00a0Ash and J.\u00a0Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol.\u00a0144, North-Holland Publishing Co., Amsterdam, 2000, p.\u00a0346. ISBN 0-444-50072-3."},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-008-0110-6"},{"key":"ref003","unstructured":"R.\u00a0Downey, B.\u00a0Khoussainov, J.S.\u00a0Miller and L.\u00a0Yu, Degree spectra of unary relations on \u27e8\u03c9,\u2a7d\u27e9, http:\/\/homepages.mcs.vuw.ac.nz\/~downey\/publications\/LOJan24.pdf."},{"key":"ref004","unstructured":"V.S.\u00a0Harizanov, Degree spectrum of a recursive relation on a recursive structure, PhD thesis, University of Wisconsin\u2013Madison, 1987."},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"ref006","unstructured":"A.\u00a0Marks, T.\u00a0Slaman and J.\u00a0Steel, Martin\u2019s conjecture, arithmetic equivalence, and countable Borel equivalence relations, ArXiv e-prints, 2011."},{"key":"ref007","unstructured":"A.\u00a0Montalb\u00e1n, Personal communication."},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0084969"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31933-4"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180086","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-180086","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:58Z","timestamp":1777391998000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,15]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,24]]}},"alternative-id":["10.3233\/COM-180086"],"URL":"https:\/\/doi.org\/10.3233\/com-180086","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,15]]}}}