Review of Symbolic Logic:1-18 (forthcoming)

Guillermo Badia
University of Queensland
Andrew Tedder
Czech Academy of Sciences
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. Hajek proved it in the fuzzy logic BL for Grzegorczyk's variant of Q which interprets the arithmetic operations as non-total non-functional 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.
Keywords nonclassical logic  decidability  formal arithmetic
Categories (categorize this paper)
DOI 10.1017/s175502032000012x
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,039
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Extensions of Some Theorems of Gödel and Church.Barkley Rosser - 1936 - Journal of Symbolic Logic 1 (3):87-91.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Towards Metamathematics of Weak Arithmetics Over Fuzzy Logic.Petr Hájek - 2011 - Logic Journal of the IGPL 19 (3):467-475.
A Lindström Theorem for Intuitionistic Propositional Logic.Guillermo Badia - 2020 - Notre Dame Journal of Formal Logic 61 (1):11-30.
On Theories and Models in Fuzzy Predicate Logics.Petr Hájek & Petr Cintula - 2006 - Journal of Symbolic Logic 71 (3):863 - 880.
Undecidable Theories.Alfred Tarski - 1953 - Amsterdam: North-Holland Pub. Co..
Infinitary Propositional Relevant Languages with Absurdity.Guillermo Badia - 2017 - Review of Symbolic Logic 10 (4):663-681.
New Sequent Calculi for Visser's Formal Propositional Logic.Katsumasa Ishii - 2003 - Mathematical Logic Quarterly 49 (5):525.
Deductive Completeness.Kosta Došen - 1996 - Bulletin of Symbolic Logic 2 (3):243-283.
Contraction-Elimination for Implicational Logics.Ryo Kashima - 1997 - Annals of Pure and Applied Logic 84 (1):17-39.


Added to PP index

Total views
22 ( #512,827 of 2,505,763 )

Recent downloads (6 months)
1 ( #416,705 of 2,505,763 )

How can I increase my downloads?


My notes