{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:56:34Z","timestamp":1757624194059,"version":"3.44.0"},"reference-count":33,"publisher":"SAGE Publications","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2022,12,21]]},"abstract":"<jats:p>The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f : \u03c9 \u2192 \u03c9 that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous.<\/jats:p>","DOI":"10.3233\/com-210375","type":"journal-article","created":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T12:18:05Z","timestamp":1652444285000},"page":"187-221","source":"Crossref","is-referenced-by-count":3,"title":["Primitive recursive equivalence relations and their primitive recursive complexity"],"prefix":"10.1177","volume":"11","author":[{"given":"Nikolay","family":"Bazhenov","sequence":"first","affiliation":[{"name":"Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., Novosibirsk, 630090, Russia"}]},{"given":"Keng Meng","family":"Ng","sequence":"additional","affiliation":[{"name":"School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore"}]},{"given":"Luca","family":"San Mauro","sequence":"additional","affiliation":[{"name":"Department of Mathematics \u201cGuido Castelnuovo\u201d, Sapienza University of Rome, I-00185 Rome, Italy"}]},{"given":"Andrea","family":"Sorbi","sequence":"additional","affiliation":[{"name":"Department of Information Engineering and Mathematics, University of Siena, I-53100 Siena, Italy"}]}],"member":"179","reference":[{"key":"10.3233\/COM-210375_ref1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01459088","article-title":"Zum Hilbertschen Aufbau der reellen Zahlen","volume":"99","author":"Ackermann","year":"1928","journal-title":"Math. Ann."},{"key":"10.3233\/COM-210375_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50062-1_33"},{"issue":"1","key":"10.3233\/COM-210375_ref4","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1017\/jsl.2013.8","article-title":"Universal computably enumerable equivalence relations","volume":"79","author":"Andrews","year":"2014","journal-title":"J. Symb. Logic"},{"key":"10.3233\/COM-210375_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2020.102811"},{"issue":"3\u20134","key":"10.3233\/COM-210375_ref6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.3233\/COM-180098","article-title":"Joins and meets in the structure of ceers","volume":"8","author":"Andrews","year":"2019","journal-title":"Computability"},{"issue":"2","key":"10.3233\/COM-210375_ref7","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1017\/bsl.2019.20","article-title":"Foundations of online structure theory","volume":"25","author":"Bazhenov","year":"2019","journal-title":"Bull. Symbolic Logic"},{"key":"10.3233\/COM-210375_ref8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.tcs.2020.08.021","article-title":"Online presentations of finitely generated structures","volume":"844","author":"Bazhenov","year":"2020","journal-title":"Theoret. Comput. Sci."},{"issue":"7\u20138","key":"10.3233\/COM-210375_ref9","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s00153-020-00710-1","article-title":"Classifying equivalence relations in the Ershov hierarchy","volume":"59","author":"Bazhenov","year":"2020","journal-title":"Arch. Math. Logic"},{"issue":"3","key":"10.3233\/COM-210375_ref10","doi-asserted-by":"publisher","first-page":"529","DOI":"10.2307\/2273443","article-title":"Classifying positive equivalence relations","volume":"48","author":"Bernardi","year":"1983","journal-title":"J. Symb. Logic"},{"issue":"4","key":"10.3233\/COM-210375_ref11","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.2178\/jsl\/1318338855","article-title":"Strong isomorphism reductions in complexity theory","volume":"76","author":"Buss","year":"2011","journal-title":"J. Symb. Logic"},{"issue":"1","key":"10.3233\/COM-210375_ref12","doi-asserted-by":"publisher","first-page":"15","DOI":"10.3233\/COM-2012-004","article-title":"The hierarchy of equivalence relations on the natural numbers under computable reducibility","volume":"1","author":"Coskey","year":"2012","journal-title":"Computability"},{"issue":"3","key":"10.3233\/COM-210375_ref13","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.46298\/lmcs-17(3:6)2021","article-title":"Foundations of online structure theory II: The operator approach","volume":"17","author":"Downey","year":"2021","journal-title":"Log. Methods Comput. Sci."},{"key":"10.3233\/COM-210375_ref14","unstructured":"Y.L. Ershov, Theory of Numberings, Nauka, Moscow, 1977, in Russian."},{"key":"10.3233\/COM-210375_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(99)80030-5"},{"issue":"1","key":"10.3233\/COM-210375_ref16","doi-asserted-by":"publisher","first-page":"122","DOI":"10.2178\/jsl\/1327068695","article-title":"Isomorphism relations on computable structures","volume":"77","author":"Fokina","year":"2012","journal-title":"J. Symb. Logic"},{"issue":"3","key":"10.3233\/COM-210375_ref17","doi-asserted-by":"publisher","first-page":"894","DOI":"10.2307\/2274750","article-title":"A Borel reducibility theory for classes of countable structures","volume":"54","author":"Friedman","year":"1989","journal-title":"J. Symb. Logic"},{"key":"10.3233\/COM-210375_ref18","doi-asserted-by":"crossref","unstructured":"S. Gao, Invariant Descriptive Set Theory, CRC Press, Boca Raton, 2008.","DOI":"10.1201\/9781584887942"},{"issue":"1","key":"10.3233\/COM-210375_ref19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1023\/A:1010521410739","article-title":"Computably enumerable equivalence relations","volume":"67","author":"Gao","year":"2001","journal-title":"Stud. Log."},{"issue":"2","key":"10.3233\/COM-210375_ref20","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1215\/00294527-3867118","article-title":"On polynomial-time relation reducibility","volume":"58","author":"Gao","year":"2017","journal-title":"Notre Dame J. Form. Log."},{"issue":"4","key":"10.3233\/COM-210375_ref21","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1090\/S0894-0347-1990-1057041-5","article-title":"A Glimm-Effros dichotomy for Borel equivalence relations","volume":"3","author":"Harrington","year":"1990","journal-title":"J. Amer. Math. Soc."},{"key":"10.3233\/COM-210375_ref22","doi-asserted-by":"crossref","unstructured":"P.G. Hinman, Recursion-Theoretic Hierarchies, Springer, Berlin, 1978.","DOI":"10.1007\/978-3-662-12898-5"},{"key":"10.3233\/COM-210375_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-5764-9_5"},{"issue":"3","key":"10.3233\/COM-210375_ref24","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1017\/jsl.2013.33","article-title":"Complexity of equivalence relations and preorders from computability theory","volume":"79","author":"Ianovski","year":"2014","journal-title":"J. Symb. Logic"},{"key":"10.3233\/COM-210375_ref25","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2017.01.029","article-title":"Algebraic structures computable without delay","volume":"674","author":"Kalimullin","year":"2017","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"10.3233\/COM-210375_ref26","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","article-title":"On the structure of polynomial time reducibility","volume":"22","author":"Ladner","year":"1975","journal-title":"J. ACM"},{"key":"10.3233\/COM-210375_ref27","unstructured":"A.I. Mal\u2019cev, The Metamathematics of Algebraic Systems. Collected Papers: 1936\u20131967, Vol. 66, North-Holland, Amsterdam, 1971."},{"issue":"3","key":"10.3233\/COM-210375_ref28","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1070\/RM1961v016n03ABEH001120","article-title":"Constructive algebras. I","volume":"16","author":"Mal\u2019tsev","year":"1961","journal-title":"Russ. Math. Surv."},{"issue":"2","key":"10.3233\/COM-210375_ref29","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0022-0000(76)80035-9","article-title":"Polynomial and abstract subrecursive classes","volume":"12","author":"Mehlhorn","year":"1976","journal-title":"J. Comput. System Sci."},{"issue":"7","key":"10.3233\/COM-210375_ref30","doi-asserted-by":"publisher","first-page":"3113","DOI":"10.1090\/proc\/15020","article-title":"A structure of punctual dimension two","volume":"148","author":"Melnikov","year":"2020","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.3233\/COM-210375_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58741-7_8"},{"issue":"4","key":"10.3233\/COM-210375_ref32","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1215\/00294527-2019-0028","article-title":"On the degree structure of equivalence relations under computable reducibility","volume":"60","author":"Ng","year":"2019","journal-title":"Notre Dame J. Form. Log."},{"key":"10.3233\/COM-210375_ref33","unstructured":"P. Odifreddi, Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Elsevier, 1992."},{"key":"10.3233\/COM-210375_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85165-1_20"}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-210375","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:14Z","timestamp":1757420534000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-210375"}},"subtitle":[],"editor":[{"given":"Vasco","family":"Brattka","sequence":"additional","affiliation":[]},{"given":"Noam","family":"Greenberg","sequence":"additional","affiliation":[]},{"given":"Iskander","family":"Kalimullin","sequence":"additional","affiliation":[]},{"given":"Mariya","family":"Soskova","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,12,21]]},"references-count":33,"journal-issue":{"issue":"3-4"},"URL":"https:\/\/doi.org\/10.3233\/com-210375","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"type":"electronic","value":"2211-3576"},{"type":"print","value":"2211-3568"}],"subject":[],"published":{"date-parts":[[2022,12,21]]}}}