Review of Symbolic Logic:1-18 (forthcoming)

Authors
Guillermo Badia
University of Queensland
Andrew Tedder
Czech Academy of Sciences
Abstract
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
Options
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: 58,769
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 - 1968 - 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.

Analytics

Added to PP index
2020-06-30

Total views
17 ( #597,588 of 2,425,357 )

Recent downloads (6 months)
7 ( #102,586 of 2,425,357 )

How can I increase my downloads?

Downloads

My notes