Propositional modal logic over relational frames is naturally extended with propositional quantifiers by letting them range over arbitrary sets of worlds of the relevant frame. This is also known as second-order propositional modal logic. The propositionally quantified modal logic of a class of relational frames is often not axiomatizable, although there are known exceptions, most notably the case of frames validating the strong modal logic $\mathrm {S5}$. Here, we develop new general methods with which many of the open questions in (...) this area can be answered. We illustrate the usefulness of these methods by applying them to a range of examples, which provide a detailed picture of which normal modal logics define classes of relational frames whose propositionally quantified modal logic is axiomatizable. We also apply these methods to establish new results in the multimodal case. (shrink)

We consider extending the modal logic KD45, commonly taken as the baseline system for belief, with propositional quantifiers that can be used to formalize natural language sentences such as “everything I believe is true” or “there is something that I neither believe nor disbelieve.” Our main results are axiomatizations of the logics with propositional quantifiers of natural classes of complete Boolean algebras with an operator validating KD45. Among them is the class of complete, atomic, and completely multiplicative BAOs validating KD45. (...) Hence, by duality, we also cover the usual method of adding propositional quantifiers to normal modal logics by considering their classes of Kripke frames. In addition, we obtain decidability for all the concrete logics we discuss. (shrink)

In two of the earliest papers on extending modal logic with propositional quantifiers, R. A. Bull and K. Fine studied a modal logic S5Π extending S5 with axioms and rules for propositional quantification. Surprisingly, there seems to have been no proof in the literature of the completeness of S5Π with respect to its most natural algebraic semantics, with propositional quantifiers interpreted by meets and joins over all elements in a complete Boolean algebra. In this note, we give such a proof. (...) This result raises the question: For which normal modal logics. (shrink)

In this note we provide a simple proof of the incompactness over Routley-Meyer B-frames of the A1 fragment of the second order propositional relevant language.

In two of the earliest papers on extending modal logic with propositional quantifiers, R. A. Bull and K. Fine studied a modal logic S5Π extending S5 with axioms and rules for propositional quantification. Surprisingly, there seems to have been no proof in the literature of the completeness of S5Π with respect to its most natural algebraic semantics, with propositional quantifiers interpreted by meets and joins over all elements in a complete Boolean algebra. In this note, we give such a proof. (...) This result raises the question: For which normal modal logics L can one axiomatize the quantified propositional modal logic determined by the complete modal algebras for L? (shrink)

Propositional quantifiers are added to a propositional modal language with two modal operators. The resulting language is interpreted over so-called products of Kripke frames whose accessibility relations are equivalence relations, letting propositional quantifiers range over the powerset of the set of worlds of the frame. It is first shown that full second-order logic can be recursively embedded in the resulting logic, which entails that the two logics are recursively isomorphic. The embedding is then extended to all sublogics containing the logic (...) of so-called fusions of frames with equivalence relations. This generalizes a result due to Antonelli and Thomason, who construct such an embedding for the logic of such fusions. (shrink)

This paper defines a Sahlqvist fragment for relevant logic and establishes that each class of frames in the Routley-Meyer semantics which is definable by a Sahlqvist formula is also elementary, that is, it coincides with the class of structures satisfying a given first order property calculable by a Sahlqvist-van Benthem algorithm. Furthermore, we show that some classes of Routley-Meyer frames definable by a relevant formula are not elementary.

Robert Stalnaker has recently advocated propositional contingentism, the claim that it is contingent what propositions there are. He has proposed a philosophical theory of contingency in what propositions there are and sketched a possible worlds model theory for it. In this paper, such models are used to interpret two propositional modal languages: one containing an existential propositional quantifier, and one containing an existential propositional operator. It is shown that the resulting logic containing an existential quantifier is not recursively axiomatizable, as (...) it is recursively isomorphic to second-order logic, and a natural candidate axiomatization for the resulting logic containing an existential operator is shown to be incomplete. (shrink)

Following a result by De Rijke for modal logic, it is shown that the basic weak entailment model-theoretic language with absurdity is the maximal model-theoretic language having the finite occurrence property, preservation under relevant directed bisimulations and the finite depth property. This can be seen as a generalized preservation theorem characterizing propositional weak entailment formulas among formulas of other model-theoretic languages.

We investigate uniform interpolants in propositional modal logics from the proof-theoretical point of view. Our approach is adopted from Pitts’ proof of uniform interpolationin intuitionistic propositional logic [15]. The method is based on a simulation of certain quantifiers ranging over propositional variables and uses a terminating sequent calculus for which structural rules are admissible.

The Routley-Meyer relational semantics for relevant logics is extended to give a sound and complete model theory for many propositionally quantified relevant logics (and some non-relevant ones). This involves a restriction on which sets of worlds are admissible as propositions, and an interpretation of propositional quantification that makes ∀ pA true when there is some true admissible proposition that entails all p -instantiations of A . It is also shown that without the admissibility qualification many of the systems considered are (...) semantically incomplete, including all those that are sub-logics of the quantified version of Anderson and Belnap’s system E of entailment, extended by the mingle axiom and the Ackermann constant t . The incompleteness proof involves an algebraic semantics based on atomless complete Boolean algebras. (shrink)

We show that Pitts' modeling of propositional quantification in intuitionistic logic (as the appropriate interpolants) does not coincide with the topological interpretation. This contrasts with the case of the monadic language and the interpretation over sufficiently regular topological spaces. We also point to the difference between the topological interpretation over sufficiently regular spaces and the interpretation of propositional quantifiers in Kripke models.

Fine and Kripke extended S5, S4, S4.2 and such to produce propositionally quantified systems , , : given a Kripke frame, the quantifiers range over all the sets of possible worlds. is decidable and, as Fine and Kripke showed, many of the other systems are recursively isomorphic to second-order logic. In the present paper I consider the propositionally quantified system that arises from the topological semantics for S4, rather than from the Kripke semantics. The topological system, which I dub , (...) is strictly weaker than its Kripkean counterpart. I prove here that second-order arithmetic can be recursively embedded in . In the course of the investigation, I also sketch a proof of Fine's and Kripke's results that the Kripkean system is recursively isomorphic to second-order logic. (shrink)

We consider second-order propositional modal logic (SOPML), an extension of the basic modal language with propositional quantifiers introduced by Kit Fine in 1970. We determine the precise expressive power of SOPML by giving analogues of the Van Benthem–Rosen theorem and the Goldblatt Thomason theorem. Furthermore, we show that the basic modal language is the bisimulation invariant fragment of SOPML, and we characterize the bounded fragment of first-order logic as being the intersection of first-order logic and SOPML.

Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers ∀p, ∃p, where the propositional variables range over upward-closed subsets of the set of worlds in a Kripke structure. If the permitted accessibility relations are arbitrary partial orders, the resulting logic is known to be recursively isomorphic to full second-order logic (Kremer, 1997). It is shown that if the Kripke structures are restricted to trees of at height and width at most ω, the resulting logics are decidable. (...) This provides a partial answer to a question by Kremer. The result also transfers to modal S4 and some Gödel-Dummett logics with quantifiers over propositions. (shrink)