Studia Logica 105 (1):13-35 (2017)

Wesley H. Holliday
University of California, Berkeley
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.
Keywords Medvedev frames  modal logic  definability  nominal tense logic  difference modality  complement modality  axiomatizability  Kripke frame incompleteness
Categories (categorize this paper)
DOI 10.1007/s11225-016-9680-1
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,634
Through your library

References found in this work BETA

Modal Logic with Names.George Gargov & Valentin Goranko - 1993 - Journal of Philosophical Logic 22 (6):607 - 636.
The Modal Logic of Inequality.Maarten de Rijke - 1992 - Journal of Symbolic Logic 57 (2):566-584.
An Ascending Chain of S4 Logics.Kit Fine - 1974 - Theoria 40 (2):110-116.
Nominal Tense Logic.Patrick Blackburn - 1992 - Notre Dame Journal of Formal Logic 34 (1):56-83.
Modal Definability in Enriched Languages.Valentin Goranko - 1989 - Notre Dame Journal of Formal Logic 31 (1):81-105.

View all 13 references / Add more references

Citations of this work BETA

The Modal Logic of Bayesian Belief Revision.Zalán Gyenis, Miklós Rédei & William Brown - 2019 - Journal of Philosophical Logic 48 (5):809-824.
Standard Bayes Logic is Not Finitely Axiomatizable.Zalán Gyenis - 2020 - Review of Symbolic Logic 13 (2):326-337.
On the Modal Logic of Jeffrey Conditionalization.Zalán Gyenis - 2018 - Logica Universalis 12 (3-4):351-374.

Add more citations

Similar books and articles

Tense Logic Without Tense Operators.Frank Wolter - 1996 - Mathematical Logic Quarterly 42 (1):145-171.
Speaking About Transitive Frames in Propositional Languages.Yasuhito Suzuki, Frank Wolter & Michael Zakharyaschev - 1998 - Journal of Logic, Language and Information 7 (3):317-339.
General Frames for Relevant Modal Logics.Takahiro Seki - 2003 - Notre Dame Journal of Formal Logic 44 (2):93-109.
Completeness and Definability in the Logic of Noncontingency.Evgeni E. Zolin - 1999 - Notre Dame Journal of Formal Logic 40 (4):533-547.
On Fragments of Medvedev's Logic.Miros>law Szatkowski - 1981 - Studia Logica 40 (1):39 - 54.
On Fragments of Medvedev's Logic.Mirosław Szatkowski - 1981 - Studia Logica 40 (1):39 - 54.
Properties of Tense Logics.Frank Wolter - 1996 - Mathematical Logic Quarterly 42 (1):481-500.
First-Order Logic in the Medvedev Lattice.Rutger Kuyper - 2015 - Studia Logica 103 (6):1185-1224.
The Modal Logic of the Countable Random Frame.Valentin Goranko & Bruce Kapron - 2003 - Archive for Mathematical Logic 42 (3):221-243.
Modal Sequents and Definability.Bruce M. Kapron - 1987 - Journal of Symbolic Logic 52 (3):756-762.
Modal Logic, Truth, and the Master Modality.Torben Braüner - 2002 - Journal of Philosophical Logic 31 (4):359-386.
The Medvedev Lattice of Computably Closed Sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.


Added to PP index

Total views
8 ( #917,864 of 2,348,958 )

Recent downloads (6 months)
1 ( #512,628 of 2,348,958 )

How can I increase my downloads?


My notes