{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:57:07Z","timestamp":1753876627599,"version":"3.41.2"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T00:00:00Z","timestamp":1706572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The complexity classification of computably enumerable equivalence relations (or ceers, for short) has received much attention in the recent literature. A measure of complexity is typically provided by an appropriate notion of a reduction. Given binary relations $R$ and $S$ on natural numbers, a total function $f$ is a reduction from $R$ to $S$ if for arbitrary $x$ and $y$, the conditions $x~R~y$ and $f(x)~S~f(y)$ are always equivalent. If the function $f$ can be chosen primitive recursive, then we say that $R$ is primitively recursively reducible to $S$, denoted by $R \\leq _{pr} S$. We investigate the degree structure $(\\textbf {Ceers},\\leq _{pr})$ of $\\leq _{pr}$-degrees of ceers. We examine when pairs of incomparable degrees have an infimum and a supremum. In particular, we show that $(\\textbf {Ceers},\\leq _{pr})$ is neither an upper semilattice nor a lower semilattice. We also study first-order definable subclasses of $(\\textbf {Ceers},\\leq _{pr})$. In particular, we prove that the set of equivalences that have only finitely many classes is definable in $(\\textbf {Ceers},\\leq _{pr})$. Finally, we show that the structure of $\\leq _{pr}$-degrees of computably enumerable preorders has a hereditarily undecidable theory.<\/jats:p>","DOI":"10.1093\/logcom\/exad082","type":"journal-article","created":{"date-parts":[[2024,1,31]],"date-time":"2024-01-31T12:22:37Z","timestamp":1706703757000},"source":"Crossref","is-referenced-by-count":1,"title":["Computably enumerable equivalence relations via primitive recursive reductions"],"prefix":"10.1093","volume":"35","author":[{"given":"Birzhan S","family":"Kalmurzayev","sequence":"first","affiliation":[{"name":"Kazakh-British Technical University , 59 Tole Bi Street, Almaty, 050000, Kazakhstan and Al-Farabi Kazakh National University, 71 al Farabi Avenue, Almaty, 050040, Kazakhstan"}]},{"given":"Nikolay A","family":"Bazhenov","sequence":"additional","affiliation":[{"name":"Kazakh-British Technical University , 59 Tole Bi Street, Almaty, 050000, Kazakhstan"}]},{"given":"Alibek M","family":"Iskakov","sequence":"additional","affiliation":[{"name":"Kazakh-British Technical University , 59 Tole Bi Street, Almaty, 050000, Kazakhstan and Al-Farabi Kazakh National University, 71 al Farabi Avenue, Almaty, 050040, Kazakhstan"}]}],"member":"286","published-online":{"date-parts":[[2024,1,30]]},"reference":[{"key":"2025030912423528000_ref1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-18170-9_149","article-title":"Minimal pairs for polynomial time reducibilities","volume-title":"Computation Theory and Logic","author":"Ambos-Spies","year":"1987"},{"key":"2025030912423528000_ref2","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1016\/S0049-237X(99)80034-2","article-title":"Polynomial time reducibilities and degrees","volume-title":"Handbook of Computability Theory","author":"Ambos-Spies","year":"1999"},{"key":"2025030912423528000_ref3","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1017\/jsl.2019.39","article-title":"On isomorphism classes of computably enumerable equivalence relations","volume":"85","author":"Andrews","year":"2020","journal-title":"Journal of Symbolic Logic"},{"key":"2025030912423528000_ref4","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1007\/978-3-319-50062-1_25","article-title":"A survey on universal computably enumerable equivalence relations","volume-title":"Computability and Complexity\u2014Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday","author":"Andrews","year":"2017"},{"key":"2025030912423528000_ref5","doi-asserted-by":"crossref","first-page":"1038","DOI":"10.1017\/jsl.2022.28","article-title":"On the structure of computable reducibility on equivalence relations of natural numbers","volume":"88","author":"Andrews","year":"2023","journal-title":"Journal of Symbolic Logic"},{"key":"2025030912423528000_ref6","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1017\/jsl.2013.8","article-title":"Universal computably enumerable equivalence relations","volume":"79","author":"Andrews","year":"2014","journal-title":"Journal of Symbolic Logic"},{"key":"2025030912423528000_ref7","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1093\/logcom\/exab045","article-title":"The first-order theory of the computably enumerable equivalence relations in the uncountable setting","volume":"32","author":"Andrews","year":"2022","journal-title":"Journal of Logic and Computation"},{"key":"2025030912423528000_ref8","doi-asserted-by":"crossref","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"},{"key":"2025030912423528000_ref9","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1017\/S1755020319000273","article-title":"Effective inseparability, lattices, and preordering relations","volume":"14","author":"Andrews","year":"2021","journal-title":"Review of Symbolic Logic"},{"key":"2025030912423528000_ref10","doi-asserted-by":"crossref","first-page":"102811","DOI":"10.1016\/j.apal.2020.102811","article-title":"The theory of ceers computes true arithmetic","volume":"171","author":"Andrews","year":"2020","journal-title":"Annals of Pure and Applied Logic"},{"key":"2025030912423528000_ref11","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s10469-020-09592-x","article-title":"The structure of computably enumerable preorder relations","volume":"59","author":"Badaev","year":"2020","journal-title":"Algebra and Logic"},{"key":"2025030912423528000_ref12","doi-asserted-by":"crossref","first-page":"1630","DOI":"10.1017\/jsl.2019.26","article-title":"Automatic and polynomial-time algebraic structures","volume":"84","author":"Bazhenov","year":"2019","journal-title":"Journal of Symbolic Logic"},{"key":"2025030912423528000_ref13","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1017\/S0960129522000093","article-title":"Rogers semilattices of punctual numberings","volume":"32","author":"Bazhenov","year":"2022","journal-title":"Mathematical Structures in Computer Science"},{"key":"2025030912423528000_ref14","doi-asserted-by":"crossref","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":"Archive for Mathematical Logic"},{"key":"2025030912423528000_ref15","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1134\/S199508022002002X","article-title":"Minimal equivalence relations in hyperarithmetical and analytical hierarchies","volume":"41","author":"Bazhenov","year":"2020","journal-title":"Lobachevskii Journal of Mathematics"},{"key":"2025030912423528000_ref16","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1017\/bsl.2019.20","article-title":"Foundations of online structure theory","volume":"25","author":"Bazhenov","year":"2019","journal-title":"The Bulletin of Symbolic Logic"},{"key":"2025030912423528000_ref17","doi-asserted-by":"crossref","first-page":"187","DOI":"10.3233\/COM-210375","article-title":"Primitive recursive equivalence relations and their primitive recursive complexity","volume":"11","author":"Bazhenov","year":"2022","journal-title":"Computability"},{"key":"2025030912423528000_ref18","doi-asserted-by":"crossref","first-page":"529","DOI":"10.2307\/2273443","article-title":"Classifying positive equivalence relations","volume":"48","author":"Bernardi","year":"1983","journal-title":"Journal of Symbolic Logic"},{"key":"2025030912423528000_ref19","article-title":"Foundations of online structure theory II: the operator approach","volume":"17","author":"Downey","year":"2021","journal-title":"Logical Methods in Computer Science"},{"key":"2025030912423528000_ref20","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/BF02218645","article-title":"Positive equivalences","volume":"10","author":"Ershov","year":"1971","journal-title":"Algebra and Logic"},{"volume-title":"Theory of Numberings","year":"1977","author":"Ershov","key":"2025030912423528000_ref21"},{"key":"2025030912423528000_ref22","doi-asserted-by":"crossref","DOI":"10.1201\/9781584887942","volume-title":"Invariant Descriptive Set Theory","author":"Gao","year":"2008"},{"key":"2025030912423528000_ref23","doi-asserted-by":"crossref","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 Journal of Formal Logic"},{"key":"2025030912423528000_ref24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1023\/A:1010521410739","article-title":"Computably enumerable equivalence relations","volume":"67","author":"Gao","year":"2001","journal-title":"Studia Logica"},{"key":"2025030912423528000_ref25","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/978-1-4020-5764-9_5","article-title":"Borel equivalence relations","volume-title":"Handbook of Set Theory","author":"Hjorth","year":"2010"},{"key":"2025030912423528000_ref26","doi-asserted-by":"crossref","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":"Theoretical Computer Science"},{"author":"Kalmurzayev","key":"2025030912423528000_ref27","article-title":"A note on the degree structure of primitive recursive $m$-reducibility"},{"key":"2025030912423528000_ref28","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1002\/malq.19870330106","article-title":"A note on positive equivalence relations","volume":"33","author":"Lachlan","year":"1987","journal-title":"Mathematical Logic Quarterly"},{"key":"2025030912423528000_ref29","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1070\/RM1961v016n03ABEH001120","article-title":"Constructive algebras. I","volume":"16","author":"Mal\u2019tsev","year":"1961","journal-title":"Russian Mathematical Surveys"},{"key":"2025030912423528000_ref30","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1007\/s11856-019-1948-5","article-title":"The back-and-forth method and computability without delay","volume":"234","author":"Melnikov","year":"2019","journal-title":"Israel Journal of Mathematics"},{"key":"2025030912423528000_ref31","doi-asserted-by":"crossref","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 Journal of Formal Logic"},{"volume-title":"Classical Recursion Theory","year":"1992","author":"Odifreddi","key":"2025030912423528000_ref32"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/2\/exad082\/56486780\/exad082.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/2\/exad082\/56486780\/exad082.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,9]],"date-time":"2025-03-09T12:42:50Z","timestamp":1741524170000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exad082\/7591913"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,30]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3,8]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exad082","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2025,3]]},"published":{"date-parts":[[2024,1,30]]},"article-number":"exad082"}}