Počet záznamů: 1
How Much Propositional Logic Suffices for Rosser's Undecidability Theorem?
- 1.
SYSNO ASEP 0523434 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název How Much Propositional Logic Suffices for Rosser's Undecidability Theorem? Tvůrce(i) Badia, G. (AT)
Cintula, Petr (UIVT-O) RID, ORCID, SAI
Hájek, Petr (UIVT-O) RID, SAI
Tedder, Andrew (UIVT-O) RID, ORCID, SAIZdroj.dok. Review of Symbolic Logic. - : Cambridge University Press - ISSN 1755-0203
Roč. 15, č. 2 (2022), s. 487-504Poč.str. 18 s. Jazyk dok. eng - angličtina Země vyd. GB - Velká Británie Klíč. slova undecidability ; substructural logic ; Robinson arithmetic Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics CEP GA17-04630S GA ČR - Grantová agentura ČR Způsob publikování Omezený přístup Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000797598200010 EID SCOPUS 85091839606 DOI 10.1017/S175502032000012X Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2023 Elektronická adresa http://dx.doi.org/10.1017/S175502032000012X
Počet záznamů: 1