UC Berkeley

We make the following contributions to modal logics with propositional quantifiers and modal logics with comparative operators in this dissertation:

- We define a general notion of normal modal logics with propositional quantifiers. We call them normal Π-logics. Then, as was done by Scrogg's theorem on extensions of the modal logic S5, we study in general the normal Π-logics extending S5. We show that they are all complete with respect to their algebraic semantics based on complete simple monadic algebras. We also show that the lattice formed by these logics is isomorphic to the lattice of the open sets of the disjoint union of two copies of the one-point compactification of N with the natural order topology. Further, we show how to determine the computability of normal Pi-logics extending S5Π. A corollary is that they can be of arbitrarily high Turing-degree.

- Regarding the normal Π-logics extending the modal logic KD45, we identify two important axioms: Immod: □∀p(□p → p) and 4∀: ∀p□φ→□∀p□φ. We argue that when □ is interpreted as the belief operator, we should not accept Immod in the logic of belief while 4∀ is desirable in settings with full introspection. Then we provide algebraic semantics based on complete well-connected pseudo monadic algebras for Box and ∀p and show that with respect to these algebras, normal Π-logics extending KD45 and 4∀ with a finite list of formulas are complete. We also give a general completeness theorem for atomic complete well-connected pseudo monadic algebras and a sufficient condition for the decidability of logics obtained by classes of these algebras, atomic or not. A special case of these general theorems is that the normal Π-logic of serial, transitive, and Euclidean Kripke frames, that is, the Kripke frames validating KD45, is axiomatized by KD45, 4∀, Immod, and ∃p(p∧∀q(q→□(p→q))) together with the usual axioms and rules for propositional quantifiers, and this logic is decidable.

Other than completeness and decidability, we also show that 4∀ is not in the smallest normal Π-logic extending KD45, using a countermodel based on a possible-world frame with propositional contingency, and that 4∀ is valid in any complete Boolean algebra expansion validating KD45.

- For modal logics with comparative operators, we first provide an axiomatization of the logic of comparing the cardinality of sets, as defined by Cantor. The main technical contribution is the observation that in a purely comparative language, we can define finiteness well enough so that an axiomatization can be done by combining the logic of comparative cardinality for finite sets and the logic of comparative cardinality for infinite sets. Note that these two logics are very different: the former contains the axiom of qualitative additivity: |A| ≥ |B| iff |A \ B| ≥ |B \ A| but not the axiom of absorption: if |A| ≥ |B| and |A| ≥ |C| then |A| ≥ |B ∪ C|, while the latter does the opposite.

- Then we consider modal logics for comparative imprecise probability. In these logics, comparisons are made according to a set of probability measures and can be intuitively read as either "at least as likely as" (symbolized by ≥) or "more likely than" (symbolized by >). We first disambiguate two interpretations of "more likely than" based on a set of probability measures and show that the stronger interpretation is not definable from "at least as likely as" while the weaker sense is. Then, we go on to axiomatize the logic of imprecise probability in a sequence of languages obtained by adding to the language with just "at least as likely as", one by one, the comparative operator > for "more likely than" (in the stronger sense), a unary operator ♢ for "possibly", and a binary operator <φ>ψ for "possibly φ, and after learning the truth of φ, ψ''. We also comment on the expressivity of these languages and the decidability of the logics in these languages. In particular, we show that many distinctive features of the imprecise probability approach of representing the doxastic states of agents, such as the problem of dilation, are observable at this purely comparative level. Finally, we add a pair of operators Ipφ and Ip-φ, intuitively read, respectively, as "after learning the existence of an actually true new proposition, now named by p, φ", and "after learning the existence of an actually false new proposition, now named by p, φ". We show that this pair of operators allow us to formalize a common kind of information dynamics and will boost the expressivity of the language to a quantitative level.