Undecidability of First-Order Intuitionistic and Modal Logics with Two variables

Publisher： Cambridge University Press

E-ISSN： 1943-5894|11|3|428-438

ISSN： 1079-8986

Source： Bulletin of Symbolic Logic, Vol.11, Iss.3, 2005-09, pp. : 428-438

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified modal logics, including those in the standard nomenclature above, even the monadic two-variable fragments turn out to be undecidable.

Related content

Undecidability of modal and intermediate first-order logics with two individual variables

By  

The Journal of Symbolic Logic, Vol. 58, Iss. 3, 1993-09 ,pp. : 800-823 (24)

Cambridge University Press

Access to resources Recommend Favorite

Decidable fragments of first-order modal logics

By  

The Journal of Symbolic Logic, Vol. 66, Iss. 3, 2001-09 ,pp. : 1415-1438 (24)

Cambridge University Press

Access to resources Recommend Favorite

The continuum and first-order intuitionistic logic

By  

The Journal of Symbolic Logic, Vol. 57, Iss. 4, 1992-12 ,pp. : 1417-1424 (8)

Cambridge University Press

Access to resources Recommend Favorite

Small substructures and decidability issues for first-order logic with two variables

By  

The Journal of Symbolic Logic, Vol. 77, Iss. 3, 2012-09 ,pp. : 729-765 (37)

Cambridge University Press

Access to resources Recommend Favorite

First-order definability in modal logic

By  

The Journal of Symbolic Logic, Vol. 40, Iss. 1, 1975-03 ,pp. : 35-40 (6)

Cambridge University Press

Access to resources Recommend Favorite