{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:50:19Z","timestamp":1773820219595,"version":"3.50.1"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001824","name":"GA \u010cR","doi-asserted-by":"publisher","award":["19-05497S"],"award-info":[{"award-number":["19-05497S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007251","name":"National Research University Higher School of Economics","doi-asserted-by":"publisher","award":["19-04-050"],"award-info":[{"award-number":["19-04-050"]}],"id":[{"id":"10.13039\/501100007251","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,12,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Presburger arithmetic is the true theory of natural numbers with addition. We study interpretations of Presburger arithmetic in itself. The main result of this paper is that all self-interpretations are definably isomorphic to the trivial one. Here we consider interpretations that might be multi-dimensional. We note that this resolves a conjecture by Visser (1998, An overview of interpretability logic. Advances in Modal Logic, pp. 307\u2013359). In order to prove the result, we show that all linear orderings that are interpretable in $({\\mathbb{N}},+)$ are scattered orderings with the finite Hausdorff rank and that the ranks are bounded in the terms of the dimensions of the respective interpretations.<\/jats:p>","DOI":"10.1093\/logcom\/exaa050","type":"journal-article","created":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T19:26:39Z","timestamp":1599679599000},"page":"1681-1693","source":"Crossref","is-referenced-by-count":4,"title":["Multi-dimensional Interpretations of Presburger Arithmetic in Itself"],"prefix":"10.1093","volume":"30","author":[{"given":"Fedor","family":"Pakhomov","sequence":"first","affiliation":[{"name":"Institute of Mathematics of the Czech Academy of Sciences, \u017ditn\u00e1 25, 115 67, Praha 1, Czech Republic and Steklov Mathematical Institute of Russian Academy of Sciences, 8, Gubkina Str., Moscow, 119991, Russian Federation"}]},{"given":"Alexander","family":"Zapryagaev","sequence":"additional","affiliation":[{"name":"National Research University Higher School of Economics, 6, Usacheva Str., Moscow 119048, Russian Federation"}]}],"member":"286","published-online":{"date-parts":[[2020,9,22]]},"reference":[{"key":"2020120307171543800_ref1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1002\/malq.19660120111","article-title":"Axiomatische untersuchungen \u00fcber einige mit der presburgerschen arithmetik verwandte systeme","volume":"12","author":"Apelt","year":"1966","journal-title":"Mathematical Logic Quarterly"},{"key":"2020120307171543800_ref2","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","article-title":"On uniformity within NC1","volume":"41","author":"Barrington","year":"1990","journal-title":"Computer and System Sciences"},{"key":"2020120307171543800_ref3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1215\/S0012-7094-64-03132-1","article-title":"Combinatorial remarks on partitions of a multipartite number","volume":"31","author":"Blakley","year":"1964","journal-title":"Duke Mathematical Journal"},{"key":"2020120307171543800_ref4","doi-asserted-by":"crossref","first-page":"153","DOI":"10.2178\/jsl\/1045861509","article-title":"Presburger sets and p-minimal fields","volume":"68","author":"Cluckers","year":"2003","journal-title":"Journal of Symbolic Logic"},{"key":"2020120307171543800_ref5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","article-title":"Semigroups, Presburger formulas, and languages","volume":"16","author":"Ginsburg","year":"1966","journal-title":"Pacific Journal of Mathematics"},{"key":"2020120307171543800_ref6","article-title":"Metamathematics of First-Order Arithmetic","author":"H\u00e1jek","year":"1993","journal-title":"Springer"},{"key":"2020120307171543800_ref7","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/BF01451165","article-title":"Grundz\u00fcge einer theorie der geordneten mengen","volume":"65","author":"Hausdorff","year":"1908","journal-title":"Mathematische Annalen"},{"key":"2020120307171543800_ref8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"Hodges","year":"1993"},{"key":"2020120307171543800_ref9","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0022-0000(69)80014-0","article-title":"Every semilinear set is a finite union of disjoint linear sets","volume":"3","author":"Ito","year":"1969","journal-title":"Journal of Computer and System Sciences"},{"key":"2020120307171543800_ref10","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1145\/1094622.1094625","article-title":"Automatic linear orders and trees","volume":"6","author":"Khoussainov","year":"2005","journal-title":"ACM Transactions on Computational Logic"},{"key":"2020120307171543800_ref11","first-page":"92","article-title":"\u00dcber die vollst\u00e4ndigkeit eines gewissen Systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortritt","author":"Presburger","year":"1929","journal-title":"Comptes Rendus du I Congr\u00e8s de Math\u00e9maticiens des Pays Slaves"},{"key":"2020120307171543800_ref12","volume-title":"Linear Orderings","author":"Rosenstein","year":"1982"},{"key":"2020120307171543800_ref13","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/1071596.1071602","article-title":"Arithmetic, first-order logic, and counting quantifiers","volume":"6","author":"Schweikardt","year":"2005","journal-title":"ACM Transactions on Computational Logic"},{"key":"2020120307171543800_ref14","author":"Smorynski","year":"2012","journal-title":"Logical Number Theory I: An Introduction"},{"key":"2020120307171543800_ref15","article-title":"Presburger\u2019s article on integer arithmetic: remarks and translation","author":"Stansifer","year":"1984","journal-title":"Technical Report"},{"key":"2020120307171543800_ref16","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/0097-3165(95)90067-5","article-title":"On vector partition functions","volume":"72","author":"Sturmfels","year":"1995","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"2020120307171543800_ref17","volume-title":"Undecidable Theories","author":"Tarski","year":"1953"},{"key":"2020120307171543800_ref18","first-page":"44","article-title":"Non-archimedean models for arithmetic","volume":"6","author":"Tennenbaum","year":"1959","journal-title":"Notices of the American Mathematical Society"},{"key":"2020120307171543800_ref19","first-page":"307","article-title":"An overview of interpretability logic","author":"Visser","year":"1998","journal-title":"Advances in Modal Logic"},{"key":"2020120307171543800_ref20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-72056-2_22","volume-title":"Interpretations of Presburger arithmetic in itself","author":"Zapryagaev","year":"2018"},{"key":"2020120307171543800_ref21","volume-title":"Interpretations in Presburger Arithmetic","author":"Zoethout","year":"2015"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/8\/1681\/34673220\/exaa050.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/8\/1681\/34673220\/exaa050.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T12:20:04Z","timestamp":1606998004000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/30\/8\/1681\/5909508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":21,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,9,22]]},"published-print":{"date-parts":[[2020,12,10]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaa050","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,12]]},"published":{"date-parts":[[2020,9,22]]}}}