Noncompactness in propositional modal logic
S. K. Thomason
Abstract
S. K. Thomason
Abstract
We have come to believe that propositional modal logic (with the usual relational semantics) must be understood as a rather strong fragment of classical second-order predicate logic. (The interpretation of propositional modal logic in second-order predicate logic is well known; see e.g. [2, §1].) “Strong” refers of course to the expressive power of the languages, not to the deductive power of formal systems. By “rather strong” we mean sufficiently strong that theorems about first-order logic which fail for second-order logic usually fail even for propositional modal logic. Some evidence for this belief is contained in [2] and [3]. In the former is exhibited a finitely axiomatized consistent tense logic having no relational models, and the latter presents a finitely axiomatized modal logic between T and S4, such that □p → □2p is valid in all relational models of the logic but is not a thesis of the logic. The result of [2] is strong evidence that bimodal logic is essentially second-order, but that of [3] does not eliminate the possibility that unimodal logic only appears to be incomplete because we have not adopted sufficiently powerful rules of inference. In the present paper we present stronger evidence of the essentially second-order nature of unimodal logic.
OpenAlex reports 30 citations for this work. Citation counts describe recorded attention and do not establish research quality.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
We have come to believe that propositional modal logic (with the usual relational semantics) must be understood as a rather strong fragment of classical second-order predicate logic. (The interpretation of propositional modal logic in second-order predicate logic is well known; see e.g. [2, §1].) “Strong” refers of course to the expressive power of the languages, not to the deductive power of formal systems. By “rather strong” we mean sufficiently strong that theorems about first-order logic which fail for second-order logic usually fail even for propositional modal logic. Some evidence for this belief is contained in [2] and [3]. In the former is exhibited a finitely axiomatized consistent tense logic having no relational models, and the latter presents a finitely axiomatized modal logic between T and S4, such that □p → □2p is valid in all relational models of the logic but is not a thesis of the logic. The result of [2] is strong evidence that bimodal logic is essentially second-order, but that of [3] does not eliminate the possibility that unimodal logic only appears to be incomplete because we have not adopted sufficiently powerful rules of inference. In the present paper we present stronger evidence of the essentially second-order nature of unimodal logic.
Key concepts: Predicate logic, Intermediate logic, Zeroth-order logic, Dynamic logic (digital electronics), Modal logic, Normal modal logic, Predicate variable, Autoepistemic logic