Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter

Studia Logica 107 (4):695-717 (2018)
  Copy   BIBTEX

Abstract

We prove that the positive fragment of first-order intuitionistic logic in the language with two individual variables and a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable. This holds true regardless of whether we consider semantics with expanding or constant domains. We then generalise this result to intervals \ and \, where QKC is the logic of the weak law of the excluded middle and QBL and QFL are first-order counterparts of Visser’s basic and formal logics, respectively. We also show that, for most “natural” first-order modal logics, the two-variable fragment with a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable, regardless of whether we consider semantics with expanding or constant domains. These include all sublogics of QKTB, QGL, and QGrz—among them, QK, QT, QKB, QD, QK4, and QS4.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,923

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

Predicate Modal Logics Do Not Mix Very Well.Olivier Gasquet - 1998 - Mathematical Logic Quarterly 44 (1):45-49.
Completeness and incompleteness for intuitionistic logic.Charles Mccarty - 2008 - Journal of Symbolic Logic 73 (4):1315-1327.
The monadic hybrid calculus.Omar Alaqeeli & William Wadge - 2017 - Journal of Applied Non-Classical Logics 27 (1-2):33-49.
Deciding regular grammar logics with converse through first-order logic.Stéphane Demri & Hans De Nivelle - 2005 - Journal of Logic, Language and Information 14 (3):289-329.

Analytics

Added to PP
2018-07-17

Downloads
27 (#606,449)

6 months
9 (#352,597)

Historical graph of downloads
How can I increase my downloads?