{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T15:59:13Z","timestamp":1702569553169},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6493,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1996,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200017400_inline1\" \/> be a first-order structure; we denote by DEF(<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200017400_inline1\" \/>) the set of all first-order definable relations and functions within <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200017400_inline1\" \/>. Let <jats:italic>\u03c0<\/jats:italic> be any one-to-one function from \u2115 into the set of prime integers.<\/jats:p><jats:p>Let <jats:italic>\u2223<\/jats:italic> and \u2022 be respectively the divisibility relation and multiplication as function. We show that the sets DEF(\u2115, <jats:italic>\u03c0<\/jats:italic>, <jats:italic>\u2223<\/jats:italic>) and DEF(\u2115, <jats:italic>\u03c0<\/jats:italic>, \u2022) are equal. However there exists function <jats:italic>\u03c0<\/jats:italic> such that the set DEF(\u2115, +, <jats:italic>\u2223<\/jats:italic>), or, equivalently, DEF(\u2115, <jats:italic>\u03c0<\/jats:italic>, \u2022) is not equal to DEF(\u2115, +, \u2022). Nevertheless, in all cases there is an {<jats:italic>\u03c0<\/jats:italic>, \u2022}-definable and hence also {<jats:italic>\u03c0<\/jats:italic>, <jats:italic>|<\/jats:italic>}-definable structure over <jats:italic>\u03c0<\/jats:italic> which is isomorphic to \u3008\u2115, +, \u2022\u3009. Hence theories TH(\u2115, <jats:italic>\u03c0<\/jats:italic>, <jats:italic>\u2223<\/jats:italic>) and TH(\u2115, <jats:italic>\u03c0<\/jats:italic>, \u2022) are <jats:italic>undecidable<\/jats:italic>.<\/jats:p><jats:p>The binary relation of <jats:italic>equipotence<\/jats:italic> between two positive integers saying that they have equal number of prime divisors is not definable within the divisibility lattice over positive integers. We prove it first by comparing the lower bound of the computational complexity of the additive theory of positive integers and of the upper bound of the computational complexity of the theory of the mentioned lattice.<\/jats:p><jats:p>The last section provides a self-contained alternative proof of this latter result based on a decision method linked to an elimination of quantifiers via specific tables.<\/jats:p>","DOI":"10.2307\/2275673","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:58:29Z","timestamp":1146941909000},"page":"515-540","source":"Crossref","is-referenced-by-count":2,"title":["Definability and decidability issues in extensions of the integers with the divisibility predicate"],"prefix":"10.1017","volume":"61","author":[{"given":"Patrick","family":"Cegielski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuri","family":"Matiyasevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Richard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200017400_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7"},{"key":"S0022481200017400_ref002","first-page":"330","volume-title":"Koningklijke Nederlandse Akademie van wetenschappen, Proceedings of the section of sciences","author":"Beth","year":"1953"},{"key":"S0022481200017400_ref023","first-page":"98","volume":"14","author":"Robinson","year":"1949","journal-title":"Definability and decision problems in arithmetic"},{"key":"S0022481200017400_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"S0022481200017400_ref024","doi-asserted-by":"publisher","DOI":"10.1111\/j.1755-2567.1959.tb00301.x"},{"key":"S0022481200017400_ref016","first-page":"309","volume-title":"Biblioth\u00e8que du Congr\u00e8s international de philosophie, Paris, 1900","volume":"3","author":"Padoa","year":"1901"},{"key":"S0022481200017400_ref018","unstructured":"Richard Denis , first publication in [19] and [22]."},{"key":"S0022481200017400_ref009","volume-title":"Mathematical Logic","author":"Ebbinghaus","year":"1984"},{"key":"S0022481200017400_ref007","first-page":"1431","article-title":"Ind\u00e9cidabilit\u00e9 de la th\u00e9orie des entiers naturels munis d'une \u00e9num\u00e9ration des premiers et de la divisibilit\u00e9","volume":"I","author":"Cegielski","year":"1992","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Scinces, Paris t. 315"},{"key":"S0022481200017400_ref026","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"},{"key":"S0022481200017400_ref004","first-page":"367","article-title":"La th\u00e9orie \u00e9l\u00e9mentaire de la divisibilit\u00e9 est finiment axiomatisable","volume":"I","author":"Cegielski","year":"1984","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences, Paris t. 299"},{"key":"S0022481200017400_ref020","first-page":"927","volume":"50","author":"Poizat","year":"1985","journal-title":"Answer to a problem raised by J. Robinson: the arithmetic of positive or negative integers is definable from successor and divisibility"},{"key":"S0022481200017400_ref017","volume-title":"Cours de th\u00e9orie des mod\u00e8les","author":"Poizat","year":"1985"},{"key":"S0022481200017400_ref003","first-page":"44","volume-title":"La th\u00e9orie \u00e9l\u00e9mentaire de la multiplication, Model theory and arithmetic","author":"Cegielski"},{"key":"S0022481200017400_ref022","first-page":"529","volume-title":"Number Theory and Applications","volume":"265","author":"Poizat","year":"1988"},{"key":"S0022481200017400_ref015","first-page":"343","article-title":"Images de spectres binaires par des polyn\u00f4mes","volume":"I","author":"More","year":"1992","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences, Paris, t. 315"},{"key":"S0022481200017400_ref025","unstructured":"Woods Alan , Some problems in logic and number theory and their connections, Thesis , University of Manchester, 1981."},{"key":"S0022481200017400_ref021","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90144-X","article-title":"All arithmetical sets ofpowers ofprimes are first-order definable in terms of the successor function and the coprimeness predicate","volume":"53","author":"Poizat","year":"1985","journal-title":"Discrete Mathematics"},{"key":"S0022481200017400_ref019","unstructured":"Poizat Bruno , D\u00e9finissabilit\u00e9 en arithm\u00e9tique et m\u00e9thode de codage Z.B.V. appliqu\u00e9e \u00e0 des langages avec successeurs et coprimarit\u00e9, Th\u00e8se de doctorat d'\u00c9tat , Universit\u00e9 de Lyon-I, 1985."},{"key":"S0022481200017400_ref012","first-page":"203","volume-title":"Luminy 1990","author":"Langevin","year":"1992"},{"key":"S0022481200017400_ref010","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1980.11995045"},{"key":"S0022481200017400_ref006","volume-title":"Mathematics and Computer Science","author":"Cegielski","year":"1996"},{"key":"S0022481200017400_ref011","first-page":"175","article-title":"Hilbert's Tenth Problem and the independence of recursive difference","volume":"10","author":"Goodstein","journal-title":"The Journal of the London Mathematical Society"},{"key":"S0022481200017400_ref005","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093635001"},{"key":"S0022481200017400_ref013","volume-title":"Introduction to mathematical logic","author":"Mendelson","year":"1964"},{"key":"S0022481200017400_ref014","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0095666"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200017400","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T17:28:51Z","timestamp":1557682131000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200017400\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,6]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,6]]}},"alternative-id":["S0022481200017400"],"URL":"https:\/\/doi.org\/10.2307\/2275673","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,6]]}}}