How Much Propositional Logic Suffices for Rosser’s Essential Undecidability Theorem?

Review of Symbolic Logic:1-18 (forthcoming)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 86,412

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.. Edited by Andrzej Mostowski & Raphael M. Robinson.
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

31 (#425,205)

6 months
3 (#340,711)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Guillermo Badia
University of Queensland
Andrew Tedder
University of Connecticut

Citations of this work

No citations found.

Add more citations

References found in this work

Relevant Logics and Their Rivals.Richard Routley, Val Plumwood, Robert K. Meyer & Ross T. Brady - 1982 - Ridgeview. Edited by Richard Sylvan & Ross Brady.
Extensions of some theorems of gödel and church.Barkley Rosser - 1936 - Journal of Symbolic Logic 1 (3):87-91.

Add more references