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

Review of Symbolic Logic 15 (2):487 - 504 (2022)
  Copy   BIBTEX

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.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,597

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.
Weak Theories of Concatenation and Arithmetic.Yoshihiro Horihata - 2012 - Notre Dame Journal of Formal Logic 53 (2):203-222.
On Interpretability in the Theory of Concatenation.Vítězslav Švejdar - 2009 - Notre Dame Journal of Formal Logic 50 (1):87-95.
Cardinal arithmetic in the style of Baron Von münchhausen.Albert Visser - 2009 - Review of Symbolic Logic 2 (3):570-589.
Basic Predicate Calculus.Wim Ruitenburg - 1998 - Notre Dame Journal of Formal Logic 39 (1):18-46.
Arithmetic on semigroups.Mihai Ganea - 2009 - Journal of Symbolic Logic 74 (1):265-278.
Essential hereditary undecidability.Albert Visser - 2024 - Archive for Mathematical Logic 63 (5):529-562.

Analytics

Added to PP
2020-06-30

Downloads
67 (#316,410)

6 months
13 (#265,352)

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