{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:23:04Z","timestamp":1740108184529,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"7-8","license":[{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["M 2461"],"award-info":[{"award-number":["M 2461"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Nazarbayev University Faculty Development Competitive Research Grants","award":["N090118FD5342","N090118FD5342"],"award-info":[{"award-number":["N090118FD5342","N090118FD5342"]}]},{"name":"Nazarbayev University Faculty Development Competitive Research Grants","award":["N090118FD5342"],"award-info":[{"award-number":["N090118FD5342"]}]},{"name":"PSR program of the University of Siena"},{"DOI":"10.13039\/501100011051","name":"Council on grants of the President of the Russian Federation","doi-asserted-by":"publisher","award":["MK-1214.2019.1"],"award-info":[{"award-number":["MK-1214.2019.1"]}],"id":[{"id":"10.13039\/501100011051","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["18-11-00028"],"award-info":[{"award-number":["18-11-00028"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science Committee of the Republic of Kazakhstan","award":["AP05131579"],"award-info":[{"award-number":["AP05131579"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\leqslant _c$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:msub>\n<mml:mo>\u2a7d<\/mml:mo>\n<mml:mi>c<\/mml:mi>\n<\/mml:msub>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This gives rise to a rich degree structure. In this paper, we lift the study of <jats:italic>c<\/jats:italic>-degrees to the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta ^0_2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:msubsup>\n<mml:mi>\u0394<\/mml:mi>\n<mml:mn>2<\/mml:mn>\n<mml:mn>0<\/mml:mn>\n<\/mml:msubsup>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> case. In doing so, we rely on the Ershov hierarchy. For any notation <jats:italic>a<\/jats:italic> for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\leqslant _c$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:msub>\n<mml:mo>\u2a7d<\/mml:mo>\n<mml:mi>c<\/mml:mi>\n<\/mml:msub>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> on the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Sigma ^{-1}_{a}\\smallsetminus \\Pi ^{-1}_a$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:msubsup>\n<mml:mi>\u03a3<\/mml:mi>\n<mml:mi>a<\/mml:mi>\n<mml:mrow>\n<mml:mo>-<\/mml:mo>\n<mml:mn>1<\/mml:mn>\n<\/mml:mrow>\n<\/mml:msubsup>\n<mml:mo>\\<\/mml:mo>\n<mml:msubsup>\n<mml:mi>\u03a0<\/mml:mi>\n<mml:mi>a<\/mml:mi>\n<mml:mrow>\n<mml:mo>-<\/mml:mo>\n<mml:mn>1<\/mml:mn>\n<\/mml:mrow>\n<\/mml:msubsup>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of <jats:italic>c<\/jats:italic>-degrees.<\/jats:p>","DOI":"10.1007\/s00153-020-00710-1","type":"journal-article","created":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T10:03:22Z","timestamp":1581588202000},"page":"835-864","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Classifying equivalence relations in the Ershov hierarchy"],"prefix":"10.1007","volume":"59","author":[{"given":"Nikolay","family":"Bazhenov","sequence":"first","affiliation":[]},{"given":"Manat","family":"Mustafa","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3156-6870","authenticated-orcid":false,"given":"Luca","family":"San Mauro","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Sorbi","sequence":"additional","affiliation":[]},{"given":"Mars","family":"Yamaleev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,13]]},"reference":[{"key":"710_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, U., Badaev, S., Sorbi, A.: A survey on universal computably enumerable equivalence relations. In: Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A., Rosamond, F. (Eds.), Computability and Complexity. Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pp. 418\u2013451. Springer (2017)","DOI":"10.1007\/978-3-319-50062-1_25"},{"issue":"01","key":"710_CR2","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1017\/jsl.2013.8","volume":"79","author":"U Andrews","year":"2014","unstructured":"Andrews, U., Lempp, S., Miller, J.S., Ng, K.M., San\u00a0Mauro, L., Sorbi, A.: Universal computably enumerable equivalence relations. J. Symb. Logic 79(01), 60\u201388 (2014)","journal-title":"J. Symb. Logic"},{"issue":"3\u20134","key":"710_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.3233\/COM-180098","volume":"8","author":"U Andrews","year":"2019","unstructured":"Andrews, U., Sorbi, A.: Joins and meets in the structure of ceers. Computability 8(3\u20134), 193\u2013241 (2019)","journal-title":"Computability"},{"key":"710_CR4","unstructured":"Ash, C.J., Knight, J.: Computable structures and the hyperarithmetical hierarchy, vol. 144. Newnes (2000)"},{"issue":"03","key":"710_CR5","doi-asserted-by":"publisher","first-page":"529","DOI":"10.2307\/2273443","volume":"48","author":"C Bernardi","year":"1983","unstructured":"Bernardi, C., Sorbi, A.: Classifying positive equivalence relations. J. Symb. Logic 48(03), 529\u2013538 (1983)","journal-title":"J. Symb. Logic"},{"key":"710_CR6","unstructured":"Cooper, S.B.: Degrees of unsolvability. Ph.D. thesis, University of Leicester (1971)"},{"issue":"1","key":"710_CR7","doi-asserted-by":"publisher","first-page":"15","DOI":"10.3233\/COM-2012-004","volume":"1","author":"S Coskey","year":"2012","unstructured":"Coskey, S., Hamkins, J.D., Miller, R.: The hierarchy of equivalence relations on the natural numbers under computable reducibility. Computability 1(1), 15\u201338 (2012)","journal-title":"Computability"},{"issue":"1","key":"710_CR8","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02218750","volume":"7","author":"YL Ershov","year":"1968","unstructured":"Ershov, Y.L.: A hierarchy of sets. I. Algebra Log. 7(1), 25\u201343 (1968)","journal-title":"Algebra Log."},{"issue":"4","key":"710_CR9","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/BF02218664","volume":"7","author":"YL Ershov","year":"1968","unstructured":"Ershov, Y.L.: On a hierarchy of sets, II. Algebra Log. 7(4), 212\u2013232 (1968)","journal-title":"Algebra Log."},{"issue":"1","key":"710_CR10","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/BF02219847","volume":"9","author":"YL Ershov","year":"1970","unstructured":"Ershov, Y.L.: On a hierarchy of sets, III. Algebra Log. 9(1), 20\u201331 (1970)","journal-title":"Algebra Log."},{"key":"710_CR11","unstructured":"Ershov, Y.L.: Teoriya Numeratsii. Nauka, Novosibirsk (1977) (in Russian)"},{"key":"710_CR12","doi-asserted-by":"crossref","unstructured":"Ershov, Y.L.: Theory of numberings. In: Griffor, E.G. (Ed.), Handbook of Computability Theory, Volume 140 of Studies Logic Found. Math., pp. 473\u2013503. North-Holland (1999)","DOI":"10.1016\/S0049-237X(99)80030-5"},{"issue":"2","key":"710_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1017\/jsl.2015.11","volume":"81","author":"E Fokina","year":"2016","unstructured":"Fokina, E., Khoussainov, B., Semukhin, P., Turetsky, D.: Linear orders realized by ce equivalence relations. J. Symb. Log. 81(2), 463\u2013482 (2016)","journal-title":"J. Symb. Log."},{"issue":"3\u20134","key":"710_CR14","doi-asserted-by":"publisher","first-page":"265","DOI":"10.3233\/COM-180100","volume":"8","author":"E Fokina","year":"2019","unstructured":"Fokina, E., Rossegger, D., San Mauro, L.: Measuring the complexity of reductions between equivalence relations. Computability 8(3\u20134), 265\u2013280 (2019)","journal-title":"Computability"},{"issue":"1","key":"710_CR15","doi-asserted-by":"publisher","first-page":"122","DOI":"10.2178\/jsl\/1327068695","volume":"77","author":"EB Fokina","year":"2012","unstructured":"Fokina, E.B., Friedman, S.-D., Harizanov, V., Knight, J.F., McCoy, C., Montalb\u00e1n, A.: Isomorphism relations on computable structures. J. Symb. Log. 77(1), 122\u2013132 (2012)","journal-title":"J. Symb. Log."},{"issue":"03","key":"710_CR16","doi-asserted-by":"publisher","first-page":"894","DOI":"10.2307\/2274750","volume":"54","author":"H Friedman","year":"1989","unstructured":"Friedman, H., Stanley, L.: A Borel reducibility theory for classes of countable structures. J. Symb. Log. 54(03), 894\u2013914 (1989)","journal-title":"J. Symb. Log."},{"issue":"1","key":"710_CR17","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1023\/A:1010521410739","volume":"67","author":"S Gao","year":"2001","unstructured":"Gao, S., Gerdes, P.: Computably enumerable equivalence relations. Stud. Log. 67(1), 27\u201359 (2001)","journal-title":"Stud. Log."},{"issue":"7","key":"710_CR18","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1016\/j.apal.2014.04.001","volume":"165","author":"A Gavruskin","year":"2014","unstructured":"Gavruskin, A., Jain, S., Khoussainov, B., Stephan, F.: Graphs realised by r.e. equivalence relations. Ann. Pure Appl. Log. 165(7), 1263\u20131290 (2014)","journal-title":"Ann. Pure Appl. Log."},{"issue":"2","key":"710_CR19","doi-asserted-by":"publisher","first-page":"397","DOI":"10.2307\/2274228","volume":"50","author":"F Montagna","year":"1985","unstructured":"Montagna, F., Sorbi, A.: Universal recursion theoretic properties of r.e. preordered structures. J. Symb. Log. 50(2), 397\u2013406 (1985)","journal-title":"J. Symb. Log."},{"issue":"4","key":"710_CR20","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1215\/00294527-2019-0028","volume":"60","author":"KM Ng","year":"2019","unstructured":"Ng, K.M., Yu, H.: On the degree structure of equivalence relations under computable reducibility. Notre Dame J. Formal Logic 60(4), 733\u2013761 (2019)","journal-title":"Notre Dame J. Formal Logic"},{"key":"710_CR21","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1017\/S0960129516000335","volume":"28","author":"A Nies","year":"2018","unstructured":"Nies, A., Sorbi, A.: Calibrating word problems of groups via the complexity of equivalence relations. Math. Struct. Comput. Sci 28, 457\u2013471 (2018)","journal-title":"Math. Struct. Comput. Sci"},{"issue":"4","key":"710_CR22","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10469-015-9349-2","volume":"54","author":"S Ospichev","year":"2015","unstructured":"Ospichev, S.: Friedberg numberings in the Ershov hierarchy. Algebra Log. 54(4), 283\u2013295 (2015)","journal-title":"Algebra Log."},{"key":"710_CR23","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-1-4615-0755-0_14","volume-title":"Computability and Models","author":"V Selivanov","year":"2003","unstructured":"Selivanov, V.: Positive structures. In: Cooper, S.B., Goncharov, S.S. (eds.) Computability and Models, pp. 321\u2013350. Springer, New York (2003)"},{"issue":"1","key":"710_CR24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF00968968","volume":"26","author":"VL Selivanov","year":"1985","unstructured":"Selivanov, V.L.: Ershov hierarchy. Siberian Math. J. 26(1), 105\u2013117 (1985)","journal-title":"Siberian Math. J."},{"key":"710_CR25","series-title":"Perspectives in Mathematical Logic, Omega Series","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. Perspectives in Mathematical Logic, Omega Series. Springer, Heidelberg (1987)"},{"key":"710_CR26","unstructured":"Visser, A.: Numerations, $$\\lambda $$-calculus and arithmetic. To HB Curry: Essays on Combinatory Logic, Lambda-Calculus and Formalism, pp. 259\u2013284. Academic Press, New York (1980)"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-020-00710-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00153-020-00710-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-020-00710-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:21:35Z","timestamp":1613089295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00153-020-00710-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,13]]},"references-count":26,"journal-issue":{"issue":"7-8","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["710"],"URL":"https:\/\/doi.org\/10.1007\/s00153-020-00710-1","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"type":"print","value":"0933-5846"},{"type":"electronic","value":"1432-0665"}],"subject":[],"published":{"date-parts":[[2020,2,13]]},"assertion":[{"value":"8 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}