Viewing the language of modal logic as a language for describing directed graphs, a natural type of directed graph to study modally is one where the nodes are sets and the edge relation is the subset or superset relation. A well-known example from the literature on intuitionistic logic is the class of Medvedev frames $\langle W,R\rangle$ where $W$ is the set of nonempty subsets of some nonempty finite set $S$, and $xRy$ iff $x\supseteq y$, or more liberally, where $\langle W,R\rangle$ (...) is isomorphic as a directed graph to $\langle \wp(S)\setminus\{\emptyset\},\supseteq\rangle$. Prucnal [32] proved that the modal logic of Medvedev frames is not finitely axiomatizable. Here we continue the study of Medvedev frames with extended modal languages. Our results concern definability. We show that the class of Medvedev frames is definable by a formula in the language of tense logic, i.e., with a converse modality for quantifying over supersets in Medvedev frames, extended with any one of the following standard devices: nominals (for naming nodes), a difference modality (for quantifying over those $y$ such that $x\not= y$), or a complement modality (for quantifying over those $y$ such that $x\not\supseteq y$). It follows that either the logic of Medvedev frames in one of these tense languages is finitely axiomatizable---which would answer the open question of whether Medvedev's [31] "logic of finite problems'' is decidable---or else the minimal logics in these languages extended with our defining formulas are the beginnings of infinite sequences of frame-incomplete logics. (shrink)

We consider modal logics whose intermediate fragments lie between the logic of infinite problems [20] and the Medvedev logic of finite problems [15]. There is continuum of such logics [19]. We prove that none of them is finitely axiomatizable. The proof is based on methods from [12] and makes use of some graph-theoretic constructions (operations on coverings, and colourings).

In Bayesian belief revision a Bayesian agent revises his prior belief by conditionalizing the prior on some evidence using Bayes’ rule. We define a hierarchy of modal logics that capture the logical features of Bayesian belief revision. Elements in the hierarchy are distinguished by the cardinality of the set of elementary propositions on which the agent’s prior is defined. Inclusions among the modal logics in the hierarchy are determined. By linking the modal logics in the hierarchy to the strongest modal (...) companion of Medvedev’s logic of finite problems it is shown that the modal logic of belief revision determined by probabilities on a finite set of elementary propositions is not finitely axiomatizable. (shrink)