Review of Symbolic Logic:1-18 (forthcoming)
Authors |
|
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 |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Relevant Logics and Their Rivals.Richard Routley, Val Plumwood, Robert K. Meyer & Ross T. Brady - 1982 - Ridgeview.
Undecidable Theories.Alfred Tarski, Andrzej Mostowski & Raphael M. Robinson - 1953 - Philosophy 30 (114):278-279.
Extensions of Some Theorems of Gödel and Church.Barkley Rosser - 1936 - Journal of Symbolic Logic 1 (3):87-91.
Variants of Robinson's Essentially Undecidable theoryR.James P. Jones & John C. Shepherdson - 1983 - Archive for Mathematical Logic 23 (1):61-64.
Citations of this work BETA
No citations found.
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.
Generic Generalized Rosser Fixed Points.Dick H. J. de Jongh & Franco Montagna - 1987 - Studia Logica 46 (2):193-203.
On Theories and Models in Fuzzy Predicate Logics.Petr Hájek & Petr Cintula - 2006 - Journal of Symbolic Logic 71 (3):863 - 880.
Generic Generalized Rosser Fixed Points.Dick H. J. Jongh & Franco Montagna - 1987 - Studia Logica 46 (2):193 - 203.
Gödel’s Second Incompleteness Theorem: How It is Derived and What It Delivers.Saeed Salehi - 2020 - Bulletin of Symbolic Logic 26 (3-4):241-256.
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.
Review: H. B. Curry, A New Proof of the Church-Rosser Theorem. [REVIEW]J. Barkley Rosser - 1956 - Journal of Symbolic Logic 21 (4):377-378.
On the Proof of Solovay's Theorem.Dick Jongh, Marc Jumelet & Franco Montagna - 1991 - Studia Logica 50 (1):51 - 69.
A Bounded Translation of Intuitionistic Propositional Logic Into Basic Propositional Logic.Mojtaba Aghaei & Mohammad Ardeshir - 2000 - Mathematical Logic Quarterly 46 (2):195-206.
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
22 ( #512,827 of 2,505,763 )
Recent downloads (6 months)
1 ( #416,705 of 2,505,763 )
2020-06-30
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?
Downloads