{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,25]],"date-time":"2025-05-25T10:02:40Z","timestamp":1748167360335,"version":"3.40.5"},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:00:00Z","timestamp":1648512000000},"content-version":"unspecified","delay-in-days":56,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The paper works within the framework of punctual computability, which is focused on eliminating unbounded search from constructions in algebra and infinite combinatorics. We study <jats:italic>punctual numberings<\/jats:italic>, that is, uniform computations for families <jats:italic>S<\/jats:italic> of primitive recursive functions. The <jats:italic>punctual reducibility<\/jats:italic> between numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called <jats:italic>Rogers pr-semilattices<\/jats:italic>. We show that any infinite, uniformly primitive recursive family <jats:italic>S<\/jats:italic> induces an infinite Rogers pr-semilattice <jats:italic>R<\/jats:italic>. We prove that the semilattice <jats:italic>R<\/jats:italic> does not have minimal elements, and every nontrivial interval inside <jats:italic>R<\/jats:italic> contains an infinite antichain. In addition, every non-greatest element from <jats:italic>R<\/jats:italic> is a part of an infinite antichain. We show that the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000093_inline1.png\"\/><jats:tex-math>\n$\\Sigma_1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-fragment of the theory <jats:italic>Th<\/jats:italic>(<jats:italic>R<\/jats:italic>) is decidable.<\/jats:p>","DOI":"10.1017\/s0960129522000093","type":"journal-article","created":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T07:31:20Z","timestamp":1648539080000},"page":"164-188","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Rogers semilattices of punctual numberings"],"prefix":"10.1017","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5834-2770","authenticated-orcid":false,"given":"Nikolay","family":"Bazhenov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manat","family":"Mustafa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergei","family":"Ospichev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,3,29]]},"reference":[{"key":"S0960129522000093_ref21","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/malq.19770231902","article-title":"Theorie der Numerierungen III","volume":"23","author":"Er\u0161ov","year":"1977","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"S0960129522000093_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19730191901"},{"first-page":"23","year":"2000","author":"Badaev","key":"S0960129522000093_ref2"},{"key":"S0960129522000093_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02671553"},{"key":"S0960129522000093_ref27","first-page":"233","article-title":"On primitive recursive functions of large oscillation","volume":"71","author":"Kuznecov","year":"1950","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0960129522000093_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/bsl.2019.20"},{"key":"S0960129522000093_ref17","unstructured":"Ershov, Y. L. (1977). Theory of Numberings, Moscow, Nauka. In Russian."},{"first-page":"1","year":"2020","author":"Bazhenov","key":"S0960129522000093_ref7"},{"key":"S0960129522000093_ref31","doi-asserted-by":"crossref","unstructured":"Metakides, G. and Nerode, A. (1982). The introduction of nonrecursive methods into mathematics. In: The L. E. J. Brouwer Centenary Symposium (Noordwijkerhout, 1981), Studies in Logic and the Foundations of Mathematics, vol. 110, Amsterdam, North-Holland, 319\u2013335.","DOI":"10.1016\/S0049-237X(09)70135-1"},{"key":"S0960129522000093_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2019.26"},{"key":"S0960129522000093_ref9","unstructured":"Bazhenov, N. , Ospichev, S. and Yamaleev, M. (2019d). Isomorphism types of Rogers semilattices in the analytical hierarchy. Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. To appear, preprint arXiv:1912.05226."},{"key":"S0960129522000093_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01875946"},{"key":"S0960129522000093_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-019-09540-4"},{"key":"S0960129522000093_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-020-09613-9"},{"key":"S0960129522000093_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-006-0034-3"},{"key":"S0960129522000093_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.02.004"},{"key":"S0960129522000093_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210164"},{"key":"S0960129522000093_ref22","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015352513117"},{"key":"S0960129522000093_ref28","first-page":"75","article-title":"Positive and negative numerations","volume":"6","author":"Mal\u2019cev","year":"1965","journal-title":"Soviet Mathematics. Doklady"},{"first-page":"381","year":"1998","author":"Cenzer","key":"S0960129522000093_ref11"},{"key":"S0960129522000093_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01040653"},{"key":"S0960129522000093_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68546-5_2"},{"key":"S0960129522000093_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.016"},{"key":"S0960129522000093_ref4","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1243948330"},{"key":"S0960129522000093_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-018-0647-y"},{"key":"S0960129522000093_ref15","first-page":"1","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":"S0960129522000093_ref18","volume-title":"Studies in Logic and the Foundations of Mathematics","volume":"140","author":"Ershov","year":"1999"},{"key":"S0960129522000093_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-019-1948-5"},{"first-page":"77","year":"2017","author":"Melnikov","key":"S0960129522000093_ref29"},{"key":"S0960129522000093_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2020.51"},{"key":"S0960129522000093_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.01.029"},{"key":"S0960129522000093_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102716"},{"key":"S0960129522000093_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-015-9349-2"},{"key":"S0960129522000093_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219842"},{"key":"S0960129522000093_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s11202-008-0107-8"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129522000093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,15]],"date-time":"2022-11-15T10:28:29Z","timestamp":1668508109000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129522000093\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["S0960129522000093"],"URL":"https:\/\/doi.org\/10.1017\/s0960129522000093","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2022,2]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}