Number of the records: 1
How Much Propositional Logic Suffices for Rosser's Undecidability Theorem?
- 1.
SYSNO ASEP 0523434 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title How Much Propositional Logic Suffices for Rosser's Undecidability Theorem? Author(s) Badia, G. (AT)
Cintula, Petr (UIVT-O) RID, ORCID, SAI
Hájek, Petr (UIVT-O) RID, SAI
Tedder, Andrew (UIVT-O) RID, ORCID, SAISource Title Review of Symbolic Logic. - : Cambridge University Press - ISSN 1755-0203
Roč. 15, č. 2 (2022), s. 487-504Number of pages 18 s. Language eng - English Country GB - United Kingdom Keywords undecidability ; substructural logic ; Robinson arithmetic Subject RIV BA - General Mathematics OECD category Pure mathematics R&D Projects GA17-04630S GA ČR - Czech Science Foundation (CSF) Method of publishing Limited access Institutional support UIVT-O - RVO:67985807 UT WOS 000797598200010 EID SCOPUS 85091839606 DOI 10.1017/S175502032000012X Annotation In this paper we explore the following question: how weak can a logic be for Rosser’s essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson’s Q is essentially undecidable in intuitionistic logic, and P. Hájek proved it in the fuzzy logic BL for Grzegorczyk’s variant of Q 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’s R (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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2023 Electronic address http://dx.doi.org/10.1017/S175502032000012X
Number of the records: 1