Inquisitive modal logic, InqML, is a generalisation of standard Kripke-style modal logic. In its epistemic incarnation, it extends standard epistemic logic to capture not just the information that agents have, but also the questions that they are interested in. Technically, InqML fits within the family of logics based on team semantics. From a model-theoretic perspective, it takes us a step in the direction of monadic second-order logic, as inquisitive modal operators involve quantification over sets of worlds. We introduce and investigate (...) the natural notion of bisimulation equivalence in the setting of InqML. We compare the expressiveness of InqML and first-order logic in the context of relational structures with two sorts, one for worlds and one for information states, and characterise inquisitive modal logic as the bisimulation invariant fragment of first-order logic over various natural classes of two-sorted structures. (shrink)

We define bisimulations for temporal logic with Since and Until. This new notion is compared to existing notions of bisimulations, and then used to develop the basic model theory of temporal logic with Since and Until. Our results concern both invariance and definability. We conclude with a brief discussion of the wider applicability of our ideas.

We prove that every first-order formula that is invariant under quasi-injective bisimulations is equivalent to a formula of the hybrid logic . Our proof uses a variation of the usual unravelling technique. We also briefly survey related results, and show in a standard way that it is undecidable whether a first-order formula is invariant under quasi-injective bisimulations.

It has been known since the seventies that the formulas of modal logic are invariant for bisimulations between possible worlds models — while conversely, all bisimulation-invariant first-order formulas are modally definable. In this paper, we extend this semantic style of analysis from modal formulas to dynamic program operations. We show that the usual regular operations are safe for bisimulation, in the sense that the transition relations of their values respect any given bisimulation for their arguments. Our main (...) result is a complete syntactic characterization of all first-order definable program operations that are safe for bisimulation. This is a semantic functional completeness result for programming, which may be contrasted with the more usual analysis in terms of computational power. The 'Safety Theorem' can be modulated in several ways. We conclude with a list of variants, extensions, and further developments. (shrink)

The language of standard propositional modal logic has one operator (? or ?), that can be thought of as being determined by the quantifiers ? or ?, respectively: for example, a formula of the form ?F is true at a point s just in case all the immediate successors of s verify F.This paper uses a propositional modal language with one operator determined by a generalized quantifier to discuss a simple connection between standard invariance conditions on modal formulas and (...) generalized quantifiers: the combined generalized quantifier conditions of conservativity and extension correspond to the modal condition of invariance under generated submodels, and the modal condition of invariance under bisimulations corresponds to the generalized quantifier being a Boolean combination of ? and ? (shrink)

Consider any logical system, what is its natural repertoire of logical operations? This question has been raised in particular for first-order logic and its extensions with generalized quantifiers, and various characterizations in terms of semantic invariance have been proposed. In this paper, our main concern is with modal and dynamic logics. Drawing on previous work on invariance for first-order operations, we find an abstract connection between the kind of logical operations a system uses and the kind of (...) class='Hi'>invariance conditions the system respects. This analysis yields (a) a characterization of invariance and safety under bisimulation as natural conditions for logical operations in modal and dynamic logics, and (b) some new transfer results between first-order logic and modal logic. (shrink)

We extend the languages of both basic and graded modal logic with the infinity diamond, a modality that expresses the existence of infinitely many successors having a certain property. In both cases we define a natural notion of bisimilarity for the resulting formalisms, that we dub $\mathtt {ML}^{\infty }$ and $\mathtt {GML}^{\infty }$, respectively. We then characterise these logics as the bisimulation-invariant fragments of the naturally corresponding predicate logic, viz., the extension of first-order logic with the infinity quantifier. Furthermore, (...) for both $\mathtt {ML}^{\infty }$ and $\mathtt {GML}^{\infty }$ we provide a sound and complete axiomatisation for the set of formulas that are valid in every Kripke frame, we prove a small model property with respect to a widened class of weighted models, and we establish decidability of the satisfiability problem. (shrink)

We take Carnap’s problem to be to what extent standard consequence relations in various formal languages fix the meaning of their logical vocabulary, alone or together with additional constraints on the form of the semantics. This paper studies Carnap’s problem for basic modal logic. Setting the stage, we show that neighborhood semantics is the most general form of compositional possible worlds semantics, and proceed to ask which standard modal logics (if any) constrain the box operator to be interpreted as in (...) relational Kripke semantics. Except when restricted to finite domains, no modal logic characterizes all the Kripkean interpretation of P. Moreover, we show that, in contrast with the case of first-order logic, the obvious requirement of permutation invariance is not adequate in the modal case. After pointing out some known facts about modal logics that nevertheless force the Kripkean interpretation, we focus on another feature often taken to embody the gist of modal logic: locality. We show that invariance under point-generated subframes (properly defined) does single out the Kripkean interpretations, but only among topological interpretations, not in general. Finally, we define a notion of bisimulation invariance — another aspect of locality — that, together with a reasonable closure condition, gives the desired general result. Along the way, we propose a new perspective on normal neighborhood frames as filter frames, consisting of a set of worlds equipped with an accessibility relation, and a free filter at every world. (shrink)

A variety of logical frameworks have been developed to study rational agents interacting over time. This paper takes a closer look at one particular interface, between two systems that both address the dynamics of knowledge and information flow. The first is Epistemic Temporal Logic (ETL) which uses linear or branching time models with added epistemic structure induced by agents’ different capabilities for observing events. The second framework is Dynamic Epistemic Logic (DEL) that describes interactive processes in terms of epistemic event (...) models which may occur inside modalities of the language. This paper systematically and rigorously relates the DEL framework with the ETL framework. The precise relationship between DEL and ETL is explored via a new representation theorem characterizing the largest class of ETL models corresponding to DEL protocols in terms of notions of Perfect Recall, No Miracles, and Bisimulation Invariance. We then focus on new issues of completeness. One contribution is an axiomatization for the dynamic logic of public announcements constrained by protocols, which has been an open problem for some years, as it does not fit the usual ‘reduction axiom’ format of DEL. Finally, we provide a number of examples that show how DEL suggests an interesting fine-structure inside ETL. (shrink)

We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem’s theorem, which says that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus (...) on frame classes that play a major role in modal correspondence theory and often correspond to typical application domains of modal logics. Classical model theoretic arguments do not apply to many of the most interesting classes–for instance, rooted frames, finite rooted frames, finite transitive frames, well-founded transitive frames, finite equivalence frames–as these are not elementary. Instead we develop and extend the game-based analysis over such classes and provide bisimulation preserving model constructions within these classes. Over most of the classes considered, we obtain finite model theory analogues of the classically expected characterisations, with new proofs also for the classical setting. The class of transitive frames is a notable exception, with a marked difference between the classical and the finite model theory of bisimulation invariant first-order properties. Over the class of all finite transitive frames in particular, we find that monadic second-order logic is no more expressive than first-order as far as bisimulation invariant properties are concerned — though both are more expressive here than basic modal logic. We obtain ramifications of the de Jongh–Sambin theorem and a new and specific analogue of the Janin–Walukiewicz characterisation of bisimulation invariant monadic second-order for finite transitive frames. (shrink)

A variety of logical frameworks have been developed to study rational agents interacting over time. This paper takes a closer look at one particular interface, between two systems that both address the dynamics of knowledge and information flow. The first is Epistemic Temporal Logic (ETL) which uses linear or branching time models with added epistemic structure induced by agents’ different capabilities for observing events. The second framework is Dynamic Epistemic Logic (DEL) that describes interactive processes in terms of epistemic event (...) models which may occur inside modalities of the language. This paper systematically and rigorously relates the DEL framework with the ETL framework. The precise relationship between DEL and ETL is explored via a new representation theorem characterizing the largest class of ETL models corresponding to DEL protocols in terms of notions of Perfect Recall , No Miracles , and Bisimulation Invariance . We then focus on new issues of completeness . One contribution is an axiomatization for the dynamic logic of public announcements constrained by protocols, which has been an open problem for some years, as it does not fit the usual ‘reduction axiom’ format of DEL. Finally, we provide a number of examples that show how DEL suggests an interesting fine-structure inside ETL. (shrink)

We generalize two well-known model-theoretic characterization theorems from propositional modal logic to first-order modal logic. We first study FML-definable frames and give a version of the Goldblatt–Thomason theorem for this logic. The advantage of this result, compared with the original Goldblatt–Thomason theorem, is that it does not need the condition of ultrafilter reflection and uses only closure under bounded morphic images, generated subframes and disjoint unions. We then investigate Lindström type theorems for first-order modal logic. We show that FML has (...) the maximal expressive power among the logics extending FML which satisfy compactness, bisimulation invariance and the Tarski union property. (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.

The tangle modality is a propositional connective that extends basic modal logic to a language that is expressively equivalent over certain classes of finite frames to the bisimulation-invariant fragments of both first-order and monadic second-order logic. This paper axiomatises several logics with tangle, including some that have the universal modality, and shows that they have the finite model property for Kripke frame semantics. The logics are specified by a variety of conditions on their validating frames, including local and global (...) connectedness properties. Some of the results have been used to obtain completeness theorems for interpretations of tangled modal logics in topological spaces. (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.

We consider systems of rational agents who act and interact in pursuit of their individual and collective objectives. We study and formalise the reasoning of an agent, or of an external observer, about the expected choices of action of the other agents based on their objectives, in order to assess the reasoner’s ability, or expectation, to achieve their own objective. To formalize such reasoning we extend Pauly’s Coalition Logic with three new modal operators of conditional strategic reasoning, thus introducing the (...) Logic for Local Conditional Strategic Reasoning \. We provide formal semantics for the new conditional strategic operators in concurrent game models, introduce the matching notion of bisimulation for each of them, prove bisimulation invariance and Hennessy–Milner property for each of them, and discuss and compare briefly their expressiveness. Finally, we also propose systems of axioms for each of the basic operators of \ and for the full logic. (shrink)

Interpretability logic is a modal logic that can be used to describe relative interpretability between extensions of a given first-order arithmetical theory. Verbrugge semantics is a generalization of the basic semantics for interpretability logic. Bisimulation is the basic equivalence between models for modal logic. The Van Benthem Correspondence Theorem establishes modal logic as the bisimulation invariant fragment of first-order logic. In this paper we show that a special type of bisimulations, the so-called w-bisimulations, enable an analogue of the (...) Van Benthem Theorem for interpretability logic w.r.t. Verbrugge semantics. (shrink)

This essay aims to provide a modal logic for rational intuition. Similarly to treatments of the property of knowledge in epistemic logic, I argue that rational intuition can be codified by a modal operator governed by the modal $\mu$-calculus. Via correspondence results between fixed point modal propositional logic and the bisimulation-invariant fragment of monadic second-order logic, a precise translation can then be provided between the notion of 'intuition-of', i.e., the cognitive phenomenal properties of thoughts, and the modal operators regimenting (...) the notion of 'intuition-that'. I argue that intuition-that can further be shown to entrain conceptual elucidation, by way of figuring as a dynamic-interpretational modality which induces the reinterpretation of both domains of quantification and the intensions and hyperintensions of mathematical concepts that are formalizable in monadic first- and second-order formal languages. Hyperintensionality is countenanced via a topic-sensitive epistemic two-dimensional truthmaker semantics. (shrink)

Graphs are among the most frequently used structures in Computer Science. Some of the properties that must be checked in many applications are connectivity, acyclicity and the Eulerian and Hamiltonian properties. In this work, we analyze how we can express these four properties with modal logics. This involves two issues: whether each of the modal languages under consideration has enough expressive power to describe these properties and how complex it is to use these logics to actually test whether a given (...) graph has some desired property. First, we show that these properties are not definable in a basic modal logic or in any bisimulation-invariant extension of it, like the modal μ-calculus. We then show that it is possible to express some of the above properties in a basic hybrid logic. Unfortunately, the Hamiltonian and Eulerian properties still cannot be efficiently checked. In a second attempt, we propose an extension of CTL* with nominals and show that the Hamiltonian property can be more efficiently checked in this logic than in the previous one. In a third attempt, we extend the basic hybrid logic with the ↓ operator and show that we can check the Hamiltonian property with optimal complexity in this logic. Finally, we tackle the Eulerian property in two different ways. First, we develop a generic method to express edge-related properties in hybrid logics and use it to express the Eulerian property. Second, we express a necessary and sufficient condition for the Eulerian property to hold using a graded modal logic. (shrink)

We consider a modal language over crisp frames and formulas evaluated on a finite MTL-chain (a linearly ordered commutative integral residuated lattice). We first show that the basic modal abstract logic with constants for the values of the MTL-chain is the maximal abstract logic satisfying Compactness, the Tarski Union Property and strong invariance for bisimulations. Finally, we improve this result by replacing the Tarski Union Property by a relativization property.

Notions of k-asimulation and asimulation are introduced as asymmetric counterparts to k-bisimulation and bisimulation, respectively. It is proved that a first-order formula is equivalent to a standard translation of an intuitionistic propositional formula iff it is invariant with respect to k-asimulations for some k, and then that a first-order formula is equivalent to a standard translation of an intuitionistic propositional formula iff it is invariant with respect to asimulations. Finally, it is proved that a first-order formula is equivalent (...) to a standard translation of an intuitionistic propositional formula over the class of intuitionistic Kripke models iff it is invariant with respect to asimulations between intuitionistic models. (shrink)

We propose a new perspective on logics of computation by combining instantial neighborhood logic INL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {INL}$$\end{document} with bisimulation safe operations adapted from PDL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PDL}$$\end{document}. INL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {INL}$$\end{document} is a recent modal logic, based on an extended neighborhood semantics which permits quantification over individual neighborhoods plus their contents. This system has a natural interpretation as (...) a logic of computation in open systems. Motivated by this interpretation, we show that a number of familiar program constructors can be adapted to instantial neighborhood semantics to preserve invariance for instantial neighborhood bisimulations, the appropriate bisimulation concept for INL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {INL}$$\end{document}. We also prove that our extended logic IPDL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {IPDL}$$\end{document} is a conservative extension of dual-free game logic, and its semantics generalizes the monotone neighborhood semantics of game logic. Finally, we provide a sound and complete system of axioms for IPDL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {IPDL}$$\end{document}, and establish its finite model property and decidability. (shrink)

We characterize the expressive power of the modal mu-calculus on monotone neighborhood structures, in the style of the Janin-Walukiewicz theorem for the standard modal mu-calculus. For this purpose we consider a monadic second-order logic for monotone neighborhood structures. Our main result shows that the monotone modal mu-calculus corresponds exactly to the fragment of this second-order language that is invariant for neighborhood bisimulations.

We propose a new perspective on logics of computation by combining instantial neighborhood logic \ with bisimulation safe operations adapted from \. \ is a recent modal logic, based on an extended neighborhood semantics which permits quantification over individual neighborhoods plus their contents. This system has a natural interpretation as a logic of computation in open systems. Motivated by this interpretation, we show that a number of familiar program constructors can be adapted to instantial neighborhood semantics to preserve (...) class='Hi'>invariance for instantial neighborhood bisimulations, the appropriate bisimulation concept for \. We also prove that our extended logic \ is a conservative extension of dual-free game logic, and its semantics generalizes the monotone neighborhood semantics of game logic. Finally, we provide a sound and complete system of axioms for \, and establish its finite model property and decidability. (shrink)

Hybrid languages are introduced in order to evaluate the strength of “minimal” mereologies with relatively strong frame definability properties. Appealing to a robust form of nominalism, I claim that one investigated language \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}_{\textsf {m}}$\end{document} is maximally acceptable for nominalistic mereology. In an extension \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}_{\textsf {gem}}$\end{document} of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}_{\textsf {m}}$\end{document}, a modal analog (...) for the classical systems of Leonard and Goodman and Leśniewski is introduced and shown to be complete with respect to 0-deleted Boolean algebras. We characterize the formulas of first-order logic invariant for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}_{\textsf {gem}}$\end{document}-bisimulations. (shrink)

We introduce a notion of bisimulation for graded modal logic. Using this notion, the model theory of graded modal logic can be developed in a uniform manner. We illustrate this by establishing the finite model property and proving invariance and definability results.

Transition systems can be viewed either as process diagrams or as Kripke structures. The rst perspective is that of process theory, the second that of modal logic. This paper shows how various formalisms of modal logic can be brought to bear on processes. Notions of bisimulation can not only be motivated by operations on transition systems, but they can also be suggested by investigations of modal formalisms. To show that the equational view of processes from process algebra is closely (...) related to modal logic, we consider various ways of looking at the relation between the calculus of basic process algebra and propositional dynamic logic. More concretely, the paper contains preservation results for various bisimulation notions, a result on the expressive power of propositional dynamic logic, and a de nition of bisimulation which is the proper notion of invariance for concurrent propositional dynamic logic. (shrink)

How can we prove that some fragment of a given logic has the power to define precisely all structural properties that satisfy some characteristic semantic preservation condition? This issue is a fundamental one for classical model theory and applications in non-classical settings alike. While methods differ greatly, and while the classical methods can usually not be matched for instance in the setting of finite model theory, this note surveys some interesting commonality revolving around the use and availability of tractable representatives (...) in the relevant model classes. The construction of models in which simple invariants like partial types based on some weak fragment control all the relevant structural properties, may be seen at the heart of such questions. We highlight some constructions involving degrees of acyclicity and saturation that can be achieved in finite model constructions, and discuss their uses towards expressive completeness w.r.t. bisimulation based equivalences in hypergraphs and relational structures. The emphasis is on the combinatorial challenges in such more constructive approaches that work in non-classical settings and especially in finite model theory. One new result concerns expressive completeness w.r.t. guarded negation bisimulation, a back-and-forth equivalence involving local homomorphisms. (shrink)

Consider the bounded variable logics $L^k_{\infty\omega}$ (with k variable symbols), and $C^k_{\infty\omega}$ (with k variables in the presence of counting quantifiers $\exists^{\geq m}$ ). These fragments of infinitary logic $L_{\infty\omega}$ are well known to provide an adequate logical framework for some important issues in finite model theory. This paper deals with a translation that associates equivalence of structures in the k-variable fragments with bisimulation equivalence between derived structures. Apart from a uniform and intuitively appealing treatment of these equivalences, this (...) approach relates some interesting issues for the case of an arbitrary number of variables to the case of just three variables. Invertibility of the invariants for $\equiv_{C^3}$ , in particular, would imply a positive answer to the tempting conjecture that fixed-point logic with counting captures $\bigcup_k$ Ptime $\cap C^k_{\infty\omega}$. (shrink)

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to this (...) general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too. (shrink)

This chapter contains sections titled: Enriching Extensional Logic with Intensional Notions Changing Views of Modal Logic A Précis of Basic Modal Logic The Major Applications Fine‐Structure of Expressive Power System Combination: Action and Information Back to the Heartland Conclusion.

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to this (...) general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too. (shrink)

As a new type of epistemic logics, the logics of knowing how capture the high-level epistemic reasoning about the knowledge of various plans to achieve certain goals. Existing work on these logics focuses on axiomatizations; this paper makes the first study of their model theoretical properties. It does so by introducing suitable notions of bisimulation for a family of five knowing how logics based on different notions of plans. As an application, we study and compare the expressive power of (...) these logics. (shrink)

We give a definition of bisimulation for conditional modalities interpreted on selection functions and prove the correspondence between bisimilarity and modal equivalence, generalizing the Hennessy–Milner Theorem to a wide class of conditional operators. We further investigate the operators and semantics to which these results apply. First, we show how to derive a solid notion of bisimulation for conditional belief, behaving as desired both on plausibility models and on evidence models. These novel definitions of bisimulations are exploited in a (...) series of undefinability results. Second, we treat relativized common knowledge, underlining how the same results still hold for a different modality in a different semantics. Third, we show the flexibility of the approach by generalizing it to multi-agent systems, encompassing the case of multi-agent plausibility models. (shrink)

Eino Kaila's thought occupies a curious position within the logical empiricist movement. Along with Hans Reichenbach, Herbert Feigl, and the early Moritz Schlick, Kaila advocates a realist approach towards science and the project of a “scientific world conception”. This realist approach was chiefly directed at both Kantianism and Poincaréan conventionalism. The case in point was the theory of measurement. According to Kaila, the foundations of physical reality are characterized by the existence of invariant systems of relations, which he called structures. (...) In a certain sense, these invariant structures, he maintained, are constituted in the act of measuring. By “constitution”, however, Kaila meant neither the dependency of the objects of measurement on a priori concepts (or Kantian categories) nor their being effected by conventional stipulations in a Poincaréan sense. He held that invariant structures are, quite literally, real: they exist prior to and independently of our theoretical capacity. By executing measurements, invariant structures are detected and objectively determinable by laws of nature. (shrink)

Interpretability logic is a modal formalization of relative interpretability between first‐order arithmetical theories. Verbrugge semantics is a generalization of Veltman semantics, the basic semantics for interpretability logic. Bisimulation is the basic equivalence between models for modal logic. We study various notions of bisimulation between Verbrugge models and develop a new one, which we call w‐bisimulation. We show that the new notion, while keeping the basic property that bisimilarity implies modal equivalence, is weak enough to allow the converse (...) to hold in the finitary case. To do this, we develop and use an appropriate notion of bisimulation games between Verbrugge models. (shrink)

Excerpts from Robert Nozick's "Invariances" Necessary truths are invariant across all possible worlds, contingent ones across only some.

Plausibility models are Kripke models that agents use to reason about knowledge and belief, both of themselves and of each other. Such models are used to interpret the notions of conditional belief, degrees of belief, and safe belief. The logic of conditional belief contains that modality and also the knowledge modality, and similarly for the logic of degrees of belief and the logic of safe belief. With respect to these logics, plausibility models may contain too much information. A proper notion (...) of bisimulation is required that characterises them. We define that notion of bisimulation and prove the required characterisations: on the class of image-finite and preimage-finite models, two pointed Kripke models are modally equivalent in either of the three logics, if and only if they are bisimilar. As a result, the information content of such a model can be similarly expressed in the logic of conditional belief, or the logic of degrees of belief, or that of safe belief. This, we found a surprising result. Still, that does not mean that the logics are equally expressive: the logics of conditional and degrees of belief are incomparable, the logics of degrees of belief and safe belief are incomparable, while the logic of safe belief is more expressive than the logic of conditional belief. In view of the result on bisimulation characterisation, this is an equally surprising result. We hope our insights may contribute to the growing community of formal epistemology and on the relation between qualitative and quantitative modelling. (shrink)

A modal accessibility relation is just a transition relation, and so can be represented by a {0, 1} valued transition matrix. Starting from this observation, I first show that the machinery of matrices, over Boolean algebras more general than the two-valued one, is appropriate for investigating multi-modal semantics. Then I show that bisimulations have a rather elegant theory, when expressed in terms of transformations on Boolean vector spaces. The resulting theory is a curious hybrid, fitting between conventional modal semantics and (...) conventional linear algebra. I don’t know where the investigations begun here will ultimately wind up, but in the meantime the approach has a kind of curious charm that others may find appealing. (shrink)

I argue that in order to apply the most common type of criteria for logicality, invariance criteria, to natural language, we need to consider both invariance of content—modeled by functions from contexts into extensions—and invariance of character—modeled, à la Kaplan, by functions from contexts of use into contents. Logical expressionsshould be invariant in both senses. If we do not require this, then old objections due to Timothy McCarthy and William Hanson, suitably modified, demonstrate that content invariant expressions (...) can display intuitive marks of non-logicality. If we do require this, we neatly avoid these objections while also managing to demonstrate desirable connections of logicality to necessity. The resulting view is more adequate as a demarcation of the logical expressions of natural language. (shrink)

Plausibility models are Kripke models that agents use to reason about knowledge and belief, both of themselves and of each other. Such models are used to interpret the notions of conditional belief, degrees of belief, and safe belief. The logic of conditional belief contains that modality and also the knowledge modality, and similarly for the logic of degrees of belief and the logic of safe belief. With respect to these logics, plausibility models may contain too much information. A proper notion (...) of bisimulation is required that characterises them. We define that notion of bisimulation and prove the required characterisations: on the class of image-finite and preimage-finite models, two pointed Kripke models are modally equivalent in either of the three logics, if and only if they are bisimilar. As a result, the information content of such a model can be similarly expressed in the logic of conditional belief, or the logic of degrees of belief, or that of safe belief. This, we found a surprising result. Still, that does not mean that the logics are equally expressive: the logics of conditional and degrees of belief are incomparable, the logics of degrees of belief and safe belief are incomparable, while the logic of safe belief is more expressive than the logic of conditional belief. In view of the result on bisimulation characterisation, this is an equally surprising result. We hope our insights may contribute to the growing community of formal epistemology and on the relation between qualitative and quantitative modelling. (shrink)

This article refines a foundational tenet of rational choice theory known as the principle of description invariance. Attempts to apply this principle to human agents with imperfect knowledge have paid insufficient attention to two aspects: first, agents’ epistemic situations, i.e. whether and when they recognize alternative descriptions of an object to be equivalent; and second, the individuation of objects of description, i.e. whether and when objects count as the same or different. An important consequence is that many apparent ‘framing (...) effects’ may not violate the principle of description invariance, and the subjects of these effects may not be irrational. (shrink)

It is tempting to think that a process of choosing a point at random from the surface of a sphere can be probabilistically symmetric, in the sense that any two regions of the sphere which differ by a rotation are equally likely to include the chosen point. Isaacs, Hájek, and Hawthorne (2022) argue from such symmetry principles and the mathematical paradoxes of measure to the existence of imprecise chances and the rationality of imprecise credences. Williamson (2007) has argued from a (...) related symmetry principle to the failure of probabilistic regularity. We contend that these arguments fail, because they rely on auxiliary assumptions about probability which are inconsistent with symmetry to begin with. We argue, moreover, that symmetry should be rejected in light of this inconsistency, and because it has implausible decision- theoretic implications. -/- The weaker principle of probabilistic invariance says that the probabilistic comparison of any two regions is unchanged by rotations of the sphere. This principle supports a more compelling argument for imprecise probability. We show, however, that invariance is incompatible with mundane judgments about what is probable. Ultimately, we find reason to be suspicious of the application of principles like symmetry and invariance to nonmeasurable regions. (shrink)

This chapter contains sections titled: Invariance qua Uniform Applicability Invariance qua Transindividual Concurrence Invariance qua Timelessness and Ubiquity Limits on Invariance Concluding Remarks.

Invariance criteria are widely accepted as a means to demarcate the logical vocabulary of a language. In previous work, I proposed a framework of “semantic constraints” for model theoretic consequence which does not rely on a strict distinction between logical and nonlogical terms, but rather on a range of constraints on models restricting the interpretations of terms in the language in different ways. In this paper I show how invariance criteria can be generalized so as to apply to (...) semantic constraints on models. Some obviously unpalatable semantic constraints turn out to be invariant under isomorphisms. I shall connect our discussion to known counterexamples to invariance criteria for logical terms, and so the generalization will also shed light on the current existing debate on logicality. I analyse the failure of invariance to fulfil its role as a criterion for logicality, and argue that invariance conditions should best be thought of as merely methodological meta-constraints restricting the ways the model-theoretic apparatus should be used. (shrink)