{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T11:14:10Z","timestamp":1652958850911},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T00:00:00Z","timestamp":1593388800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["The Review of Symbolic Logic"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we explore the following question: how weak can a logic be for Rosser\u2019s essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson\u2019s <jats:italic>Q<\/jats:italic> is essentially undecidable in intuitionistic logic, and P. H\u00e1jek proved it in the fuzzy logic BL for Grzegorczyk\u2019s variant of <jats:italic>Q<\/jats:italic> which interprets the arithmetic operations as nontotal nonfunctional relations. We present a proof of essential undecidability in a much weaker substructural logic and for a much weaker arithmetic theory, a version of Robinson\u2019s <jats:italic>R<\/jats:italic> (with arithmetic operations also interpreted as mere relations). Our result is based on a structural version of the undecidability argument introduced by Kleene and we show that it goes well beyond the scope of the Boolean, intuitionistic, or fuzzy logic.<\/jats:p>","DOI":"10.1017\/s175502032000012x","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T07:57:47Z","timestamp":1593417467000},"page":"487-504","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["HOW MUCH PROPOSITIONAL LOGIC SUFFICES FOR ROSSER\u2019S ESSENTIAL UNDECIDABILITY THEOREM?"],"prefix":"10.1017","volume":"15","author":[{"given":"GUILLERMO","family":"BADIA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PETR","family":"CINTULA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PETR","family":"H\u00c1JEK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANDREW","family":"TEDDER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,6,29]]},"reference":[{"key":"S175502032000012X_r15","volume-title":"Relevant Logics and Their Rivals","author":"Routley","year":"1982"},{"key":"S175502032000012X_r21","first-page":"14","volume-title":"Logic, Methodology and Philosophy of Science. Proceedings of the 1960 International Congress","author":"Vaught","year":"1962"},{"key":"S175502032000012X_r11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9452-5"},{"key":"S175502032000012X_r22","first-page":"7","volume-title":"Foundational Adventures\u2014Essays in Honour of Harvey M. Friedman","author":"Visser","year":"2014"},{"key":"S175502032000012X_r9","volume-title":"Introduction to Metamathematics","author":"Kleene","year":"1952"},{"key":"S175502032000012X_r1","volume-title":"Handbook of Mathematical Fuzzy Logic","author":"B\u011bhounek","year":"2011"},{"key":"S175502032000012X_r20","volume-title":"Undecidable Theories","author":"Tarski","year":"1953"},{"key":"S175502032000012X_r4","unstructured":"Grzegorczyk, A . (2006). Computable Relations and the Essential Undecidability of a Very Weak Arithmetic of Natural Numbers. Unpublished Manuscript."},{"key":"S175502032000012X_r3","volume-title":"Residuated Lattices: An Algebraic Glimpse at Substructural Logics","author":"Galatos","year":"2007"},{"key":"S175502032000012X_r19","first-page":"75","article-title":"On essential undecidability","volume":"14","author":"Tarski","year":"1949","journal-title":"Journal of Symbolic Logic"},{"key":"S175502032000012X_r6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3"},{"key":"S175502032000012X_r17","first-page":"347","article-title":"An interpretation of Robinson arithmetic in its Grzegorczyk\u2019s weaker variant","volume":"81","author":"\u0160vejdar","year":"2007","journal-title":"Fundamenta Informaticae"},{"key":"S175502032000012X_r7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02023013"},{"key":"S175502032000012X_r13","unstructured":"Robinson, R. M. (1950). An essentially undecidable axiom system. Proceedings of the International Congress of Mathematics 1950. Providence, RI: American Mathematical Society, pp. 729\u2013730."},{"key":"S175502032000012X_r2","doi-asserted-by":"publisher","DOI":"10.1145\/359138.359142"},{"key":"S175502032000012X_r12","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1960-0120150-1"},{"key":"S175502032000012X_r5","first-page":"155","article-title":"Mathematical fuzzy logic and natural numbers","volume":"81","author":"H\u00e1jek","year":"2007","journal-title":"Fundamenta Informaticae"},{"key":"S175502032000012X_r10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21635-4"},{"key":"S175502032000012X_r16","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882007"},{"key":"S175502032000012X_r14","doi-asserted-by":"publisher","DOI":"10.2307\/2269028"},{"key":"S175502032000012X_r8","first-page":"244","article-title":"A symmetric form of G\u00f6del\u2019s theorem","volume":"12","author":"Kleene","year":"1950","journal-title":"Indagationes Mathematicae"},{"key":"S175502032000012X_r18","first-page":"213","volume-title":"The Logica Yearbook 2007","author":"\u0160vejdar","year":"2008"}],"container-title":["The Review of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S175502032000012X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T10:55:34Z","timestamp":1652957734000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S175502032000012X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,29]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["S175502032000012X"],"URL":"https:\/\/doi.org\/10.1017\/s175502032000012x","relation":{},"ISSN":["1755-0203","1755-0211"],"issn-type":[{"value":"1755-0203","type":"print"},{"value":"1755-0211","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,29]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press on behalf of The Association for Symbolic Logic","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}