Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T05:27:33.459Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  12 March 2014

D. M. Gabbay
Affiliation:
Department of Computing, Imperial College, London SW7 2BZ, E-mail: dg@doc.ic.ac.uk
V. B. Shehtman
Affiliation:
Institute of New Technologies, Kirovogradskaya 11, Moscow 113587, E-mail: amuchnik@globlab.msk.su

Extract

The interest in fragments of predicate logics is motivated by the well-known fact that full classical predicate calculus is undecidable (cf. Church [1936]). So it is desirable to find decidable fragments which are in some sense “maximal”, i.e., which become undecidable if they are “slightly” extended. Or, alternatively, we can look for “minimal” undecidable fragments and try to identify the vague boundary between decidability and undecidability. A great deal of work in this area concerning mainly classical logic has been done since the thirties. We will not give a complete review of decidability and undecidability results in classical logic, referring the reader to existing monographs (cf. Suranyi [1959], Lewis [1979], and Dreben, Goldfarb [1979]). A short summary can also be found in the well-known book Church [1956]. Let us recall only several facts. Herein we will consider only logics without functional symbols, constants, and equality.

(C1) The fragment of the classical logic with only monadic predicate letters is decidable (cf. Behmann [1922]).

(C2) The fragment of the classical logic with a single binary predicate letter is undecidable. (This is a consequence of Gödel [1933].)

(C3) The fragment of the classical logic with a single individual variable is decidable; in fact it is equivalent to Lewis S5 (cf. Wajsberg [1933]).

(C4) The fragment of the classical logic with two individual variables is decidable (Segerberg [1973] contains a proof using modal logic; Scott [1962] and Mortimer [1975] give traditional proofs.)

(C5) The fragment of the classical logic with three individual variables and binary predicate letters is undecidable (cf. Surańyi [1943]). In fact this paper considers formulas of the following type

φ,ψ being quantifier-free and the set of binary predicate letters which can appear in φ or ψ being fixed and finite.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable