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)

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)

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.

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)

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)

There are known characterisations of several fragments of hybrid logic by means of invariance under bisimulations of some kind. The fragments include $\{\mathord {\downarrow }, \mathord {@}\}$ with or without nominals (Areces, Blackburn, Marx), $\mathord {@}$ with or without nominals (ten Cate), and $\mathord {\downarrow }$ without nominals (Hodkinson, Tahiri). Some pairs of these characterisations, however, are incompatible with one another. For other fragments of hybrid logic no such characterisations were known so far. We prove a generic bisimulation characterisation (...) theorem for all standard fragments of hybrid logic, in particular for the case with $\mathord {\downarrow }$ and nominals, left open by Hodkinson and Tahiri. Our characterisation is built on a common base and for each feature extension adds a specific condition, so it is modular in an engineering sense. (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)

are considered with a view toward analyzing operational semantics from the perspective of predicate logic. The notion of a bisimulation is employed in two distinct ways: (i) as an extensional notion of equivalence on programs (or processes) generalizing input/output equivalence (at a cost exceeding II' ,over certain transition predicates computable in log space). and (ii) as a tool for analyzing the dependence of transitions on data (which can be shown to be elementary or nonelementary. depending on the formulation of (...) the transitions). (shrink)

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.

Interpretability logic is an extension of provability logic. Veltman models and generalized Veltman models are two semantics for interpretability logic. We consider a connection between Veltman semantics and generalized Veltman semantics. We prove that for a complete image-finite generalized Veltman modelW there is a Veltman model W ′ that is bisimular to W.

The aim of this paper is to introduce the notion of a game for intuitionistic first-order Kripke models. We also establish links between notions presented here and the notions of logical equivalence and bounded bisimulation for intuitionistic first-order Kripke models, and the Ehrenfeucht–Fraïssé game for classical first-order structures.

Provability logic is a modal logic for studying properties of provability predicates, and Interpretability logic for studying interpretability between logical theories. Their natural models are GL-models and Veltman models, for which the accessibility relation is well-founded. That’s why the usual counterexample showing the necessity of finite image property in Hennessy-Milner theorem (see [1]) doesn’t exist for them. However, we show that the analogous condition must still hold, by constructing two GL-models with worlds in them that are modally equivalent but not (...) bisimilar, and showing how these GL-models can be converted to Veltman models with the same properties. In the process we develop some useful constructions: games on Veltman models, chains, and general method of transformation from GL-models/frames to Veltman ones. (shrink)

We consider the relation between the uniform interpolation property and the elimination of non-standard quantifiers (the bisimulation quantifiers) in the context of the?-calculus. In particular, we isolate classes of frames where the correspondence between these two properties is nicely smooth.

In this paper, a suitable notion of bisimulation is proposed for the bimodal logic with contingency and accident. We obtain several van Benthem Characterization Theorems, and axiomatize the bimodal logic over the class of Eulidean frames and over some more restricted classes, showing their strong completeness via a novel strategy, thereby answering two open questions raised in the literature. With the new bisimulation notion, we also correct an error in the expressivity results in the literature.

We have been discussing modal operators modelling structural changes in graphs represented as moves in different graph games. For this work, the focus is on the corresponding notions of bisimulation that explore the similarities in these graph structures. We provide an algorithmic study of the same, for sabotage modal logic vis-à-vis the sabotage games in particular, paving the way for a general study to check whether different graph game models involving certain structural changes are bisimilar. This, in turn, provides (...) us with the corresponding concepts of logical equivalences, especially for such model-changing modal logics. Through our algorithmic analyses we provide a PSPACE upper bound of the bisimulation/model comparison problem of sabotage modal logic and then generalise the result to similar other model-changing modal logics. We also provide some insight into the higher complexity of the model comparison problem for these logics compared to that for the basic modal logic. (shrink)

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 aim of this paper is to establish a new notion of equivalencebetween temporal models, so-called S-similarity, as the appropriate notionof bisimilarity for temporal logic with Since and Until. The main technicalresults of the paper provide semantical characterizations of the first-orderformulas that are equivalent to a temporal formula: Theorem 3.7 concernsthe equivalence of temporal and first-order formulas with respect to pointedtemporal models, whereas Theorem 4.4 takes the level of temporal modelsinto account.

We take the well-known intuitionistic modal logic of Fischer Servi with semantics in bi-relational Kripke frames, and give the natural extension to topological Kripke frames. Fischer Servi’s two interaction conditions relating the intuitionistic pre-order with the modal accessibility relation generalize to the requirement that the relation and its inverse be lower semi-continuous with respect to the topology. We then investigate the notion of topological bisimulation relations between topological Kripke frames, as introduced by Aiello and van Benthem, and show that (...) their topology-preserving conditions are equivalent to the properties that the inverse relation and the relation are lower semi-continuous with respect to the topologies on the two models. The first main result is that this notion of topological bisimulation yields semantic preservation w.r.t. topological Kripke models for both intuitionistic tense logics, and for their classical companion multi-modal logics in the setting of the Gödel translation. After giving canonical topological Kripke models for the Hilbert-style axiomatizations of the Fischer Servi logic and its classical companion logic, we use the canonical model in a second main result to characterize a Hennessy–Milner class of topological models between any pair of which there is a maximal topological bisimulation that preserve the intuitionistic semantics. (shrink)

In this work we summarise the concept of bisimulation, widely used both in computational sciences and in modal logic, that characterises modal structures with the same behaviour in terms of accessibility relations. Then, we offer a sketch of categorical interpretation of bisimulation between modal structures, which comprise both the structure and the valuation from a propositional language.

Review by: Julian Gutierrez The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 108-110, March 2013.

We analyze extensive games as interactive process models, using modallanguages plus matching notions of bisimulation as varieties of gameequivalences. Our technical results show how to fit existing modalnotions into this new setting.

Operators can be compared in at least two respects: expressive strength and deductive strength. Inspired by Hintikka’s treatment of question embedding verbs, the variations of noncontingency operator, and also the various combinations of modal operators and Boolean connectives, we propose a logic with strong noncontingency operator as the only primitive modality. The novel operator is deductively but not expressively stronger than both noncontingency operator and essence operator, and expressively but not deductively weaker than the necessity operator. The frame-definability power of (...) this new logic is in between standard modal logic and noncontingency logic. A notion of bisimulation is proposed to characterize this logic within standard modal logic and first-order logic. Axiomatizations over various frame classes are presented, among which the minimal logic is related to the treatment of an alternative semantics of the agreement operator proposed by Lloyd Humberstone. (shrink)

In epistemic logic, the beliefs of an agent are modeled in a way very similar to knowledge, except that they are fallible. Thus, the pattern of an agent’s true beliefs is an interesting subject to study. In this paper, we conduct a systematic study on a novel modal logic with the bundled operator ⊡ϕ:=□ϕ∧ϕ as the only primitive modality, where ⊡ captures the notion of true belief. With the help of a novel notion of ⊡-bisimulation, we characterize the expressivity (...) of this new language on relational models, and offer various completeness results. We also discuss some interesting connections between our work and previous works on reflexive-insensitive logics and the so-called boxdot conjecture. Finally, we study two generalizations of the ⊡-operator: one is the iterated true belief operator □nϕ:=ϕ∧□ϕ∧⋯∧□nϕ, the other is the neighborhood semantics for the ⊡-operator. (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)

We show that given a finite, transitive and reflexive Kripke model 〈 W , ≼, ⟦ ⋅ ⟧ 〉 and $${w \in W}$$ , the property of being simulated by w (i.e., lying on the image of a literalpreserving relation satisfying the ‘forth’ condition of bisimulation) is modally undefinable within the class of S4 Kripke models. Note the contrast to the fact that lying in the image of w under a bi simulation is definable in the standard modal language (...) even over the class of K4 models, a fairly standard result for which we also provide a proof. We then propose a minor extension of the language adding a sequent operator $${\natural}$$ (‘tangle’) which can be interpreted over Kripke models as well as over topological spaces. Over finite Kripke models it indicates the existence of clusters satisfying a specified set of formulas, very similar to an operator introduced by Dawar and Otto. In the extended language $${{\sf L}^+ = {\sf L}^{\square\natural}}$$ , being simulated by a point on a finite transitive Kripke model becomes definable, both over the class of (arbitrary) Kripke models and over the class of topological S4 models. As a consequence of this we obtain the result that any class of finite, transitive models over finitely many propositional variables which is closed under simulability is also definable in L + , as well as Boolean combinations of these classes. From this it follows that the μ -calculus interpreted over any such class of models is decidable. (shrink)

The aim of this paper is to initiate a systematic exploration of the model theory of epistemic plausibility models (EPMs). There are two subtly different definitions in the literature: one by van Benthem and one by Baltag and Smets. Because van Benthem's notion is the most general, most of the paper is dedicated to this notion. We focus on the notion of bisimulation, and show that the most natural generalization of bisimulation to van Benthem-type EPMs fails. We then (...) introduce parametrized bisimulations, and prove various bisimulationimplies- equivalence theorems, a Hennessy-Milner theorem, and several (un)definability results. We discuss the problems arising from the fact that these bisimulations are syntax-dependent (and thus not fully structural), and we present and compare two different ways of coping with this issue: adding a modality to the language, and putting extra constraints on the models. We argue that the most successful solution involves restricting to uniform and locally connected (van Benthem-type) EPMs: for this subclass the intuitively most natural notion of bisimulation and the technically sound notion coincide. Such EPMs turn out to correspond exactly with Baltag/Smets-type EPMs, which can be interpreted as constituting a methodological argument, favoring Baltag and Smets's definition of EPM over that of van Benthem. (shrink)

While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic ( $\mathcal{PAL }$ ) with distributed knowledge, in particular their expressivity, axiomatisations and complexity. $\mathcal{PAL }$ extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on $\mathcal{PACD }$ , the result of adding both common and (...) distributed knowledge to $\mathcal{PAL }$ , which is more expressive than each of its component logics. We introduce an axiomatisation of $\mathcal{PACD }$ , which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with $S5$ knowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show that $\mathcal{PACD }$ is decidable, more precisely that it is $\textsc {exptime}$ -complete. This result also carries over to $\mathcal{S 5\mathcal CD }$ with common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs. (shrink)

The effects of public announcements, private communications, deceptive messages to groups, and so on, can all be captured by a general mechanism of updating multi-agent models with update action models, now in widespread use. There is a natural extension of the definition of a bisimulation to action models. Surely enough, updating with bisimilar action models gives the same result. But the converse turns out to be false: update models may have the same update effects without being bisimilar. We propose (...) action emulation as a notion of equivalence more appropriate for action models, and generalizing standard bisimulation. It is proved that action emulation provides a full characterization of update effect. We first concentrate on the general case, and next focus on the important case of action models with propositional preconditions. Our notion of action emulation yields a simplification procedure for action models, and it gives designers of multi-agent systems a useful tool for comparing different ways of representing a particular communicative action. (shrink)

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)

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)

In this paper we present a neighborhood semantics for Intuitionistic Propositional Logic (IPL). We show that for each Kripke model of the logic there is a pointwise equivalent neighborhood model and vice versa. In this way, we establish soundness and completeness of IPL with respect to the neighborhood semantics. The relation between neighborhood and topological semantics are also investigated. Moreover, the notions of bisimulation and n-bisimulation between neighborhood models of IPL are defined naturally and some of their basic (...) properties are proved. We also consider Basic Propositional Logic (BPL), a logic weaker than IPL introduced by Albert Visser, and introduce and study its neighborhood models in the same manner. (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 study term modal logics, where modalities can be indexed by variables that can be quantified over. We suggest that these logics are appropriate for reasoning about systems of unboundedly many reasoners and define a notion of bisimulation which preserves propositional fragment of term modal logics. Also we show that the propositional fragment is already undecidable but that its monodic fragment is decidable, and expressive enough to include interesting assertions.

Natural language provides motivation for studying modal backwards-looking operators such as “now”, “then” and “actually” that evaluate their argument formula at some previously considered point instead of the current one. This paper investigates the expressive power over models of both propositional and first-order basic modal language enriched with such operators. Having defined an appropriate notion of bisimulation for first-order modal logic, I show that backwards-looking operators increase its expressive power quite mildly, contrary to beliefs widespread among philosophers of language (...) and formal semanticists. That in turn presents a strong argument for the use of operator-based systems in the semantics of natural language, instead of systems with explicit quantification over worlds and times that have become a de-facto standard for such applications. The popularity of such explicit-quantification systems is shown to be based on the misinterpretation of a claim by Cresswell, which led many philosophers and linguists to assume that introducing “now” and “then” is expressively equivalent to explicitly quantifying over worlds and times. (shrink)

The effects of public announcements, private communications, deceptive messages to groups, and so on, can all be captured by a general mechanism of updating multi-agent models with update action models, now in widespread use. There is a natural extension of the definition of a bisimulation to action models. Surely enough, updating with bisimilar action models gives the same result (modulo bisimulation). But the converse turns out to be false: update models may have the same update effects without being (...) bisimilar. We propose action emulation as a notion of equivalence more appropriate for action models, and generalizing standard bisimulation. It is proved that action emulation provides a full characterization of update effect. We first concentrate on the general case, and next focus on the important case of action models with propositional preconditions. Our notion of action emulation yields a simplification procedure for action models, and it gives designers of multi-agent systems a useful tool for comparing different ways of representing a particular communicative action. (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 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)

In this paper we investigate Kripke models, used to model knowledge or belief in a static situation, and action models, used to model communicative actions that change this knowledge or belief. The appropriate notion for structural equivalence between modal structures such as Kripke models is bisimulation: Kripke models that are bisimilar are modally equivalent. We would like to find a structural relation that can play the same role for the action models that play a prominent role in information updating. (...) Two action models are equivalent if they yield the same results when updating Kripke models. More precisely, two action models are equivalent if it holds for all Kripke models that the result of updating with one action model is bisimilar to the result of updating with the other action model. We propose a new notion of action emulation that characterizes the structural equivalence of the important class of canonical action models. Since every action model has an equivalent canonical action model, this gives a method to decide the equivalence of any pair of action models. We also give a partial result that holds for the class of all action models. Our results extend the work in van Eijck et al. (Synthese 185(1):131–151, 2012). (shrink)

Given the frequency of human error, it seems rational to believe that some of our own rational beliefs are false. This is the axiom of epistemic modesty. Unfortunately, using standard propositional quantification, and the usual relational semantics, this axiom is semantically inconsistent with a common logic for rational belief, namely KD45. Here we explore two alternative semantics for KD45 and the axiom of epistemic modesty. The first uses the usual relational semantics and bisimulation quantifiers. The second uses a topological (...) semantics and standard propositional quantification. We show the two different semantics validate many of the same formulas, though we do not know whether they validate exactly the same formulas. Along the way we address various philosophical concerns. (shrink)

Weakly Aggregative Modal Logic ) is a collection of disguised polyadic modal logics with n-ary modalities whose arguments are all the same. \ has interesting applications on epistemic logic, deontic logic, and the logic of belief. In this paper, we study some basic model theoretical aspects of \. Specifically, we first give a van Benthem–Rosen characterization theorem of \ based on an intuitive notion of bisimulation. Then, in contrast to many well known normal or non-normal modal logics, we show (...) that each basic \ system \ lacks Craig interpolation. Finally, by model theoretical techniques, we show that an extension of \ does have Craig interpolation, as an example of amending the interpolation problem of \. (shrink)

Weakly Aggregative Modal Logic (WAML) is a collection of disguised polyadic modal logics with n-ary modalities whose arguments are all the same. WAML has some interesting applications on epistemic logic and logic of games, so we study some basic model theoretical aspects of WAML in this paper. Specifically, we give a van Benthem-Rosen characterization theorem of WAML based on an intuitive notion of bisimulation and show that each basic WAML system Kn lacks Craig Interpolation.

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)