Neighborhood semantics for modal logic (Q2399881): Difference between revisions

Neighbourhood frames offer an interpretation to systems of modal logic that generalises the more traditional relational frames. A \textit{neighbourhood frame} is a pair \(\langle W,N\rangle\) where \(W\) is a nonempty set (whose members are the \textit{states}) and \(N\) (the \textit{neighbourhood function}) maps every member of \(W\) to a set of subsets of \(W\). Given a \textit{valuation} \(V\) that maps all atomic propositions \(p\) to a subset of \(W\) (the set of states at which \(p\) is true), the truth of a modal propositional formula in the \textit{model} \(\mathcal M=\langle W,N,V\rangle\) at \(w\in W\) is inductively defined as expected for the Boolean combinations of smaller formulas, and for formulas of the form \(\square\varphi\) and \(\diamondsuit\varphi\), as ``some member of \(N(w)\) is precisely the set of states \(w'\) such that \(\varphi\) is true in \(\mathcal M\) at \(w'\)'' and ``the set of states \(w'\) such that \(\varphi\) is false in \(\mathcal M\) at \(w'\) is not a member of \(N(w)\)'', respectively. Other modalities can be defined, together with their duals: \(\langle]\varphi\) is true in \(\mathcal M\) at \(w\) if ``there exists \(X\in N(w)\) such that \(\varphi\) is true in \(\mathcal M\) at all \(w'\in X\)''; \(\langle\rangle\varphi\) is true in \(\mathcal M\) at \(w\) if ``there exists \(X\in N(w)\) and \(w'\in X\) such that \(\varphi\) is true in \(\mathcal M\) at \(w'\)''. As indicated on page 46 of the book, ``an important theme in this book is to compare and contrast neighbourhood models with alternative models for the basic model language'' -- relational models in particular: the class of relational models is modally equivalent to the class of \textit{augmented} neighbourhood models -- a neighbourhood frame \(\langle W,N\rangle\) is augmented if for all \(w\in W\), \(N(w)\) is closed under supersets and contains its core, namely, \(\bigcap N(w)\) (two frameworks are modally equivalent if for any model \(\mathcal M\) and state \(w\) in one framework, there is a corresponding model \(\mathcal M'\) and state \(w'\) in the other framework such that the same formulas are true in \(\mathcal M\) at \(w\) and in \(\mathcal M'\) at \(w'\)). Chapter 1 examines the main properties that can be imposed to \textit{subset spaces} (such as being augmented), to be applied to the sets denoted \(N(w)\) above. Then a few logical notions are defined, and interpretations are discussed that invalidate some of the axioms and rules of inference that are valid on all relational models, justifying the consideration of non-normal modal logics (e.g., deontic logic, logic of ability, logic of classical deduction). Then, claiming that ``neighbourhood models are an interesting and rich class of mathematical structures that can be fruitfully studied using modal logic'', the author introduces topological models and establishes a relationship between those and neighbourhood frames, before briefly discussing many frameworks, most notably, hypergraphs, conditional logic, evidence models, and coalition logic. This chapter, possibly even more than the next two chapters, is characterised by the introduction of a very large number of notions and elementary results, loosely connected, without clear articulations. The reader should approach the material with the view that ``it is interesting'' and ''let us to study all this and that notion'', more than trying to find a flowing narrative. Chapter 2, ``Core theory'', introduces the notions of \textit{monotonic bisimulation} and \textit{bounded morphism} as tools to study how truth of formulas is preserved across various neighbourhood models. The text then jumps to variations on and generalisation of relational models, including in particular a framework to embed \textit{impossible worlds}, before examining which of the axioms and rules of inference that are valid in relational frames, but invalid in some non-normal modal logics, are also invalid in some neighbourhood frames. A more classical section follows on (weak and strong) completeness, with canonical models as standard tools. \textit{General neighbourhood frames} are then defined, that allow one to ``bypass the incompleteness results mentioned above and to prove a general completeness theorem for all classical model logics'', but the theory is not fully developed; the relevant pointers to the literature are given, here like in all parts of the book. Thanks to a notion of \textit{filtration}, satisfiability results are given, in particular for logics with \textit{non-iterative} axioms, namely, axioms in which no modal operator is within the scope of another modal operator. The next section fulfils the promise stated at the beginning of the chapter that ``the satisfiability problem for many non-normal modal logics is NP-complete, whereas it is PSPACE-complete'' with respect to some classes of neighbourhood frames. Follows a sequent-based proof system for non-normal modal logics. The chapter ends with various translations, most notably: one between neighbourhood frames and \textit{plausibility models}, defined on the basis of particular order relations; one that shows that ``neighbourhood models are just a special case of relational models''; one that ``shows that non-normal modal logic can be viewed as a fragment of first-order logic. The third chapter goes over a broad range of extra topics, some of which are more directly related to the author's own research, on game logic and public announcements in particular. All proofs are either given in great detail or left to the reader as exercises. Many notions are illustrated with welcome examples. The author has not really decided on what is assumed knowledge and what is not. With relational frames in particular, there is an appendix while at the same time, some notions are defined in the main text and in some parts, the reader is assumed to have the necessary background (on proof systems in particular). The text could be better organised, as notions are neither presented from most general to most specific, nor from most specific to most general. The coverage of many settings does not go much beyond a few definitions together with a result or two over a page or so. Considering the number of notions and the way the text is organised, the reader is likely to occasionally regret that there is no index; it would have made navigation much easier, it can be difficult to find where a notion is being defined. This is a book that should be read with pen and paper to, as suggested, find and write the proofs of the statements left as exercises, which can be done without excessive difficulty considering the detailed proofs given for the surrounding statements. Doing so will very well help the reader to learn the techniques used in this area of research. Complemented with the numerous pointers to the literature that it provides, the book will be a valuable source of information and practice for PhD students.