{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:19:51Z","timestamp":1772119191599,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T00:00:00Z","timestamp":1730073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T00:00:00Z","timestamp":1730073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Mathematical Center in Akademgorodok","award":["075-15-2022-281"],"award-info":[{"award-number":["075-15-2022-281"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2025,2]]},"abstract":"Abstract<\/jats:title>\n \n We investigate the degree spectra of computable relations on canonically ordered natural numbers\n \n \n $$(\\omega ,<)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03c9<\/mml:mi>\n ,<\/mml:mo>\n <<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and integers\n \n \n $$(\\zeta ,<)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03b6<\/mml:mi>\n ,<\/mml:mo>\n <<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . As for\n \n \n $$(\\omega ,<)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03c9<\/mml:mi>\n ,<\/mml:mo>\n <<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we provide several criteria that fix the degree spectrum of a computable relation to all c.e. or to all\n \n \n $$\\Delta _2$$<\/jats:tex-math>\n \n \n \u0394<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n degrees; this includes the complete characterization of the degree spectra of so-called computable block functions that have only finitely many types of blocks. Compared to Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1\u20138:20, 2022), we obtain a more general solution to the problem regarding possible degree spectra on\n \n \n $$(\\omega ,<)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03c9<\/mml:mi>\n ,<\/mml:mo>\n <<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , answering the question whether there are infinitely many such spectra. As for\n \n \n $$(\\zeta ,<)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03b6<\/mml:mi>\n ,<\/mml:mo>\n <<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we prove the following dichotomy result: given an arbitrary computable relation\n R<\/jats:italic>\n on\n \n \n $$(\\zeta ,<)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03b6<\/mml:mi>\n ,<\/mml:mo>\n <<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , its degree spectrum is either trivial or it contains all c.e. degrees. This result, and the proof techniques required to solve it, extend the analogous theorem for\n \n \n $$(\\omega ,<)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03c9<\/mml:mi>\n ,<\/mml:mo>\n <<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n obtained by Wright (Computability 7:349\u2013365, 2018), and provide initial insight to Wright\u2019s question whether such a dichotomy holds on computable ill-founded linear orders. This article is an extended version of Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1\u20138:20, 2022).\n <\/jats:p>","DOI":"10.1007\/s00153-024-00942-5","type":"journal-article","created":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T17:22:31Z","timestamp":1730136151000},"page":"299-331","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Degrees of relations on canonically ordered natural numbers and integers"],"prefix":"10.1007","volume":"64","author":[{"given":"Nikolay","family":"Bazhenov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dariusz","family":"Kaloci\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Wroc\u0142awski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,28]]},"reference":[{"key":"942_CR1","unstructured":"Ash, C.J., Knight, J.: Computable Structures and the Hyperarithmetical Hierarchy. Studies in logic and the foundations of mathematics, vol. 144. Elsevier, Amsterdam (2000)"},{"key":"942_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108525749","volume-title":"Computable structure theory: within the arithmetic","author":"A Montalb\u00e1n","year":"2021","unstructured":"Montalb\u00e1n, A.: Computable structure theory: within the arithmetic. Cambridge University Press, Cambridge (2021)"},{"issue":"4","key":"942_CR3","doi-asserted-by":"publisher","first-page":"723","DOI":"10.2307\/2273222","volume":"46","author":"LJ Richter","year":"1981","unstructured":"Richter, L.J.: Degrees of structures. J. Symb. Log. 46(4), 723\u2013731 (1981). https:\/\/doi.org\/10.2307\/2273222","journal-title":"J. Symb. Log."},{"key":"942_CR4","unstructured":"Harizanov, V.S.: Degree spectrum of a recursive relation on a recursive structure. PhD thesis, University of Wisconsin-Madinson (1987)"},{"issue":"2","key":"942_CR5","doi-asserted-by":"publisher","first-page":"197","DOI":"10.2307\/421207","volume":"6","author":"DR Hirschfeldt","year":"2000","unstructured":"Hirschfeldt, D.R.: Degree spectra of relations on computable structures. Bull. Symb. Logic 6(2), 197\u2013212 (2000). https:\/\/doi.org\/10.2307\/421207","journal-title":"Bull. Symb. Logic"},{"key":"942_CR6","doi-asserted-by":"publisher","unstructured":"Fokina, E.B., Harizanov, V., Melnikov, A.: Computable model theory. In: Downey, R. (ed.) turing\u2019s legacy: developments from turing\u2019s ideas in logic. Lecture Notes in Logic, vol. 42, pp. 124\u2013194. Cambridge University Press, Cambridge (2014). https:\/\/doi.org\/10.1017\/CBO9781107338579.006","DOI":"10.1017\/CBO9781107338579.006"},{"issue":"25\u201330","key":"942_CR7","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1002\/malq.19860322514","volume":"32","author":"M Moses","year":"1986","unstructured":"Moses, M.: Relations intrinsically recursive in linear orders. Math. Log. Q. 32(25\u201330), 467\u2013472 (1986). https:\/\/doi.org\/10.1002\/malq.19860322514","journal-title":"Math. Log. Q."},{"key":"942_CR8","unstructured":"Downey, R., Khoussainov, B., Miller, J.S., Yu, L.: Degree spectra of unary relations on $$(\\omega ,\\le )$$. In: Logic. methodology and philosophy of science: Proceedings of the 13th International Congress, pp. 35\u201355. College Publications, UK (2009)"},{"issue":"4","key":"942_CR9","doi-asserted-by":"publisher","first-page":"349","DOI":"10.3233\/COM-180086","volume":"7","author":"M Wright","year":"2018","unstructured":"Wright, M.: Degrees of relations on ordinals. Computability 7(4), 349\u2013365 (2018). https:\/\/doi.org\/10.3233\/COM-180086","journal-title":"Computability"},{"key":"942_CR10","unstructured":"Knoll, C.A.: Degree spectra of unary relations on $$\\omega $$ and $$\\zeta $$. Master\u2019s thesis, University of Waterloo (2009)"},{"issue":"1208","key":"942_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/memo\/1208","volume":"253","author":"M Harrison-Trainor","year":"2018","unstructured":"Harrison-Trainor, M.: Degree spectra of relations on a cone. Mem. Amer. Math. Soc. 253(1208), 1\u2013120 (2018). https:\/\/doi.org\/10.1090\/memo\/1208","journal-title":"Mem. Amer. Math. Soc."},{"key":"942_CR12","doi-asserted-by":"publisher","unstructured":"Bazhenov, N., Kaloci\u0144ski, D., Wroc\u0142awski, M.: Intrinsic complexity of recursive functions on natural numbers with standard order. In: Berenbrink, P., Monmege, B. (eds.). In 39th international symposium on theoretical aspects of computer science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 219. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.8. pages 8:1\u20138:20","DOI":"10.4230\/LIPIcs.STACS.2022.8"},{"key":"942_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively enumerable sets and degrees","author":"RI Soare","year":"1987","unstructured":"Soare, R.I.: Recursively enumerable sets and degrees. Springer, New York (1987)"},{"issue":"1","key":"942_CR14","doi-asserted-by":"publisher","first-page":"28","DOI":"10.2307\/2270580","volume":"30","author":"EM Gold","year":"1965","unstructured":"Gold, E.M.: Limiting recursion. J. Symb. Log. 30(1), 28\u201348 (1965). https:\/\/doi.org\/10.2307\/2270580","journal-title":"J. Symb. Log."},{"issue":"1","key":"942_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.2307\/2270581","volume":"30","author":"H Putnam","year":"1965","unstructured":"Putnam, H.: Trial and error predicates and the solution to a problem of Mostowski. J. Symb. Log. 30(1), 49\u201357 (1965). https:\/\/doi.org\/10.2307\/2270581","journal-title":"J. Symb. Log."},{"key":"942_CR16","doi-asserted-by":"publisher","first-page":"644","DOI":"10.2307\/1970028","volume":"69","author":"JR Shoenfield","year":"1959","unstructured":"Shoenfield, J.R.: On degrees of unsolvability. Ann. Math. 69, 644\u2013653 (1959). https:\/\/doi.org\/10.2307\/1970028","journal-title":"Ann. Math."},{"issue":"1","key":"942_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/s00153-008-0110-6","volume":"48","author":"J Chubb","year":"2009","unstructured":"Chubb, J., Frolov, A., Harizanov, V.: Degree spectra of the successor relation of computable linear orderings. Arch. Math. Log. 48(1), 7\u201313 (2009). https:\/\/doi.org\/10.1007\/s00153-008-0110-6","journal-title":"Arch. Math. Log."},{"issue":"1\u20132","key":"942_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1142\/S0219061310000924","volume":"10","author":"R Downey","year":"2010","unstructured":"Downey, R., Lempp, S., Wu, G.: On the complexity of the successivity relation in computable linear orderings. J. Math. Log. 10(1\u20132), 83\u201399 (2010). https:\/\/doi.org\/10.1142\/S0219061310000924","journal-title":"J. Math. Log."},{"issue":"1","key":"942_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.3103\/S1066369X22010066","volume":"66","author":"YA Michailovskaya","year":"2022","unstructured":"Michailovskaya, Y.A., Frolov, A.N.: Computable linear orders and the Ershov hierarchy. Russ. Math. 66(1), 71\u201374 (2022). https:\/\/doi.org\/10.3103\/S1066369X22010066","journal-title":"Russ. Math."},{"issue":"3","key":"942_CR20","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1134\/S0037446620030076","volume":"61","author":"MV Zubkov","year":"2020","unstructured":"Zubkov, M.V., Frolov, A.N.: Spectral universality of linear orders with one binary relation. Sib. Math. J. 61(3), 463\u2013467 (2020). https:\/\/doi.org\/10.1134\/S0037446620030076","journal-title":"Sib. Math. J."},{"issue":"1","key":"942_CR21","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1305\/ndjfl\/1093883561","volume":"23","author":"S Shapiro","year":"1982","unstructured":"Shapiro, S.: Acceptable notation. Notre Dame J. Form. Log. 23(1), 14\u201320 (1982). https:\/\/doi.org\/10.1305\/ndjfl\/1093883561","journal-title":"Notre Dame J. Form. Log."},{"key":"942_CR22","doi-asserted-by":"publisher","unstructured":"Wroc\u0142awski, M.: Representations of natural numbers and computability of various functions. In: Manea, F., Martin, B., Paulusma, D., Primiero, G. (eds.) Computing with Foresight and Industry, pp. 298\u2013309. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-22996-2_26","DOI":"10.1007\/978-3-030-22996-2_26"},{"key":"942_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2022.02.015","volume":"915","author":"K Zdanowski","year":"2022","unstructured":"Zdanowski, K.: On efficiency of notations for natural numbers. Theoret. Comput. Sci. 915, 1\u201310 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.02.015","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"942_CR24","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s00153-022-00836-4","volume":"62","author":"D Kaloci\u0144ski","year":"2023","unstructured":"Kaloci\u0144ski, D., Wroc\u0142awski, M.: Generalization of Shapiro\u2019s theorem to higher arities and noninjective notations. Arch. Math. Log. 62(1\u20132), 257\u2013288 (2023). https:\/\/doi.org\/10.1007\/s00153-022-00836-4","journal-title":"Arch. Math. Log."},{"key":"942_CR25","doi-asserted-by":"publisher","unstructured":"Bazhenov, N., Kaloci\u0144ski, D.: Degree spectra, and relative acceptability of notations. In: Klin, B., Pimentel, E. (eds.). In 31st EACSL annual conference on computer science logic (CSL 2023). Leibniz international proceedings in informatics (LIPIcs), vol. 252. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, pp. 11:1\u201311:20 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2023.11","DOI":"10.4230\/LIPIcs.CSL.2023.11"},{"issue":"4","key":"942_CR26","doi-asserted-by":"publisher","first-page":"345","DOI":"10.3233\/FI-2019-1772","volume":"164","author":"D Kaloci\u0144ski","year":"2019","unstructured":"Kaloci\u0144ski, D.: Some remarks on least moduli. Fund. Inform. 164(4), 345\u2013358 (2019). https:\/\/doi.org\/10.3233\/FI-2019-1772","journal-title":"Fund. Inform."},{"issue":"2","key":"942_CR27","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF02937291","volume":"67","author":"SB Cooper","year":"1989","unstructured":"Cooper, S.B., Lempp, S., Watson, P.: Weak density and cupping in the d-r.e. degrees. Israel J. Math. 67(2), 137\u2013152 (1989). https:\/\/doi.org\/10.1007\/BF02937291","journal-title":"Israel J. Math."},{"issue":"2","key":"942_CR28","doi-asserted-by":"publisher","first-page":"300","DOI":"10.2307\/1970393","volume":"80","author":"GE Sacks","year":"1964","unstructured":"Sacks, G.E.: The recursively enumerable degrees are dense. Ann. Math. 80(2), 300\u2013312 (1964). https:\/\/doi.org\/10.2307\/1970393","journal-title":"Ann. Math."},{"key":"942_CR29","unstructured":"Mitrinovi\u0107, D.S., S\u00e1ndor, J., Crstici, B.: Handbook of number theory. Mathematics and its applications, vol. 351. Kluwer, Dordrecht (1995)"},{"key":"942_CR30","volume-title":"Linear Orderings","author":"JG Rosenstein","year":"1982","unstructured":"Rosenstein, J.G.: Linear Orderings. Academic Press, New York (1982)"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00942-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-024-00942-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00942-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T00:40:39Z","timestamp":1739320839000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-024-00942-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,28]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["942"],"URL":"https:\/\/doi.org\/10.1007\/s00153-024-00942-5","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2771816\/v1","asserted-by":"object"}]},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,28]]},"assertion":[{"value":"3 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}