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.

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)

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)

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)

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)

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 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 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.

Under a proper translation, the languages of propositional (and quantified relevant logic) with an absurdity constant are characterized as the fragments of first order logic preserved under (world-object) relevant directed bisimulations. Furthermore, the properties of pointed models axiomatizable by sets of propositional relevant formulas have a purely algebraic characterization. Finally, a form of the interpolation property holds for the relevant fragment of first order logic.

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)

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)

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)

Section 1 provides a brief summary of the pair-list literature singling out some points that are particularly relevant for the coming discussion. -/- Section 2 shows that the dilemma of quantifi cation versus domain restriction arises only in extensional complement interrogatives. In matrix questions and in intensional complements only universals support pairlist readings, whence the simplest domain restriction treatment suffices. Related data including conjunction, disjunction, and cumulative readings are discussed -/- Section 3 argues that in the case of extensional complements (...) the domain restriction treatment is inadequate for at least two independent reasons. One has to do with the fact that not only upward monotonic quantifi ers support pairlist readings, and the other with the derivation of apparent scope out readings. The reasoning is supplemented with some discussion of the semantic properties of layered quantifi ers.  The above will establish the need for quantifi cation, so the question arises how the objections explicitly enlisted in the literature against quantifi cation can be answered. Section 4 considers the de dicto reading of the quantifi er s restriction, quanti cational variability, and the absence of pairlist readings with whether questions, and argues that they need not militate against the quanti ficational analysis. -/- Section 5 summarizes the emergent proposal -/- Finally, section 6 discusses the signifi cance of the above findings for the behavior of weak islands. (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.

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)

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)

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)

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)

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.

The growth of self-tracking and personal surveillance has given rise to the Quantified Self movement. Members of this movement seek to enhance their personal well-being, productivity, and self-actualization through the tracking and gamification of personal data. The technologies that make this possible can also track and gamify aspects of our interpersonal, romantic relationships. Several authors have begun to challenge the ethical and normative implications of this development. In this article, we build upon this work to provide a detailed ethical analysis (...) of the Quantified Relationship. We identify eight core objections to the QR and subject them to critical scrutiny. We argue that although critics raise legitimate concerns, there are ways in which tracking technologies can be used to support and facilitate good relationships. We thus adopt a stance of cautious openness toward this technology and advocate the development of a research agenda for the positive use of QR technologies. (shrink)

Quantification is a topic which brings together linguistics, logic, and philosophy. Quantifiers are the essential tools with which, in language or logic, we refer to quantity of things or amount of stuff. In English they include such expressions as no, some, all, both, many. Peters and Westerstahl present the definitive interdisciplinary exploration of how they work - their syntax, semantics, and inferential role.

We investigate quantifier-free induction for Lisp-like lists constructed inductively from the empty list $$ nil $$ nil and the operation $${\textit{cons}}$$ cons, that adds an element to the front of a list. First we show that, for $$m \ge 1$$ m ≥ 1, quantifier-free $$m$$ m -step induction does not simulate quantifier-free $$(m + 1)$$ ( m + 1 ) -step induction. Secondly, we show that for all $$m \ge 1$$ m ≥ 1, quantifier-free $$m$$ m -step induction does not (...) prove the right cancellation property of the concatenation operation on lists defined by left-recursion. (shrink)

In this paper, we provide a comprehensive survey of the space of possible analyses of the phenomenon of quantifier domain restriction, together with a set of considerations which militate against all but our own proposal. Among the many accounts we consider and reject are the ‘explicit’ approach to quantifier domain restric‐tion discussed, for example, by Stephen Neale, and the pragmatic approach to quantifier domain restriction proposed by Kent Bach. Our hope is that the exhaustive discussion of this special case of (...) context‐dependence will provide guidelines for how to decide, for an arbitrary case of context‐dependent discourse, whether it should be treated syntactically, semantically, or pragmatically. (shrink)

This paper extends the investigations into logical properties of the quantified argument calculus (Quarc) by suggesting a series of proper subsystems which, although retaining the entire vocabulary of Quarc, restrict quantification in such a way as to make the result decidable. The proof of decidability is via a procedure that prunes the infinite branches of a derivation tree in what is a syntactic counterpart of semantic filtration. We demonstrate an application of one of these systems by showing that Aristotle’s assertoric (...) syllogistic is embeddable within, thus also providing another method of showing its decidability. (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)

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.

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)

Quantifier variance is a well-known view in contemporary metaontology, but it remains very widely misunderstood by critics. Here we briefly and clearly explain the metasemantics of quantifier variance and distinguish between modest and strong forms of variance (Section I), explain some key applications (Section II), clear up some misunderstandings and address objections (Section III), and point the way toward future directions of quantifier-variance-related research (Section IV).

Quantified expressions in natural language generally are taken to act like quantifiers in logic, which either range over entities that need to satisfy or not satisfy the predicate in order for the sentence to be true or otherwise are substitutional quantifiers. I will argue that there is a philosophically rather important class of quantified expressions in English that act quite differently, a class that includes something, nothing, and several things. In addition to expressing quantification, such expressions act like (...) nominalizations, introducing a new domain of objects that would not have been present in the semantic structure of the sentence otherwise. The entities those expressions introduce are of just the same sort as those that certain ordinary nominalizations refer to (such as John's wisdom or John's belief that S), namely they are tropes or entities related to tropes. Analysing certain quantifiers as nominalizing quantifiers will shed a new light on philosophical issues such as the status of properties and the nature of propositional attitudes. (shrink)

This essay clarifies quantifier variance and uses it to provide a theory of indefinite extensibility that I call the variance theory of indefinite extensibility. The indefinite extensibility response to the set-theoretic paradoxes sees each argument for paradox as a demonstration that we have come to a different and more expansive understanding of ‘all sets’. But indefinite extensibility is philosophically puzzling: extant accounts are either metasemantically suspect in requiring mysterious mechanisms of domain expansion, or metaphysically suspect in requiring nonstandard assumptions about (...) mathematical objects. Happily, the view of quantifier meanings that underwrites quantifier variance can be used to provide an account of indefinite extensibility that is both metasemantically and metaphysically satisfying. Section 1 introduces the puzzle of indefinite extensibility; section 2 develops and clarifies the metasemantics of quantifier variance; section 3 solves section 1's puzzle of indefinite extensibility by applying section 2's account of quantifier meanings; and section 4 compares the theory developed in section 3 to several other theories in the literature. (shrink)

This volume on the semantic complexity of natural language explores the question why some sentences are more difficult than others. While doing so, it lays the groundwork for extending semantic theory with computational and cognitive aspects by combining linguistics and logic with computations and cognition. -/- Quantifier expressions occur whenever we describe the world and communicate about it. Generalized quantifier theory is therefore one of the basic tools of linguistics today, studying the possible meanings and the inferential power of quantifier (...) expressions by logical means. The classic version was developed in the 1980s, at the interface of linguistics, mathematics and philosophy. Before this volume, advances in "classic" generalized quantifier theory mainly focused on logical questions and their applications to linguistics, this volume adds a computational component, the third pillar of language use and logical activity. This book is essential reading for researchers in linguistics, philosophy, cognitive science, logic, AI, and computer science. (shrink)

Recently a number of works in meta-ontology have used a variant of J.H. Harris's collapse argument in the philosophy of logic as an argument against Eli Hirsch's quantifier variance. There have been several responses to the argument in the literature, but none of them have identified the central failing of the argument, viz., the argument has two readings: one on which it is sound but doesn't refute quantifier variance and another on which it is unsound. The central lesson I draw (...) is that arguments against quantifier variance must pay strict attention to issues of translation and interpretation. The paper also has a substantial appendix in which I prove the equivalence of plural mereological nihilism and standard first-order atomistic mereology; results of this kind are often appealed to in the literature on quantifier variance but without many details on the nature or proof of the result. (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)

I defend a neo-Lewisean form of contextualism about knowledge attributions. Understanding the context-sensitivity of knowledge attributions in terms of the context-sensitivity of universal quantifiers provides an appealing approach to knowledge. Among the virtues of this approach are solutions to the skeptical paradox and the Gettier problem. I respond to influential objections to Lewis’s account.

In discussing propositional quantifiers we have considered two kinds of variables: variables occupying the argument places of connectives, and variables occupying the argument places of predicates.We began with languages which contained the first kind of variable, i.e., variables taking sentences as substituends. Our first point was that there appear to be no sentences in English that serve as adequate readings of formulas containing propositional quantifiers. Then we showed how a certain natural and illuminating extension of English by prosentences (...) did provide perspicuous readings. The point of introducing prosentences was to provide a way of making clear the grammar of propositional variables: propositional variables have a prosentential character — not a pronominal character. Given this information we were able to show, on the assumption that the grammar of propositional variables in philosopher's English should be determined by their grammar in formal languages (unless a separate account of their grammar is provided), that propositional variables can be used in a grammatically and philosophically acceptable way in philosophers' English. According to our criteria of well-formedness Carnap's semantic definition of truth does not lack an ‘essential’ predicate - despite arguments to the contrary. It also followed from our account of the prosentential character of bound propositional variables that in explaining propositional quantification, sentences should not be construed as names.One matter we have not discussed is whether such quantification should be called ‘propositional’, ‘sentential’, or something else. As our variables do not range over (they are not terms) either propositions, or sentences, each name is inappropriate, given the usual picture of quantification. But we think the relevant question in this context is, are we obtaining generality with respect to propositions, sentences, or something else?Because people have argued that all bound variables must have a pronominal character, we presented and discussed in the third section languages in which the variables take propositional terms as substituends. In our case we included names of propositions, that-clauses, and names of sentences in the set of propositional terms. We made a few comparisons with the languages discussed in the second section. We showed among other things how a truth predicate could be used to obtain generality. In contrast, the languages of the second section, using propositional variables, obtain generality without the use of a truth predicate. (shrink)

Quantifier variance faces a number of difficulties. In this paper we first formulate the view as holding that the meanings of the quantifiers may vary, and that languages using different quantifiers may be charitably translated into each other. We then object to the view on the basis of four claims: (i) quantifiers cannot vary their meaning extensionally by changing the domain of quantification; (ii) quantifiers cannot vary their meaning intensionally without collapsing into logical pluralism; (iii) quantifier (...) variance is not an ontological doctrine; (iv) quantifier variance is not compatible with charitable translation and as such is internally inconsistent. In light of these troubles, we recommend the dissolution of quantifier variance and suggest that the view be laid to rest. (shrink)

In the work of both Matti Eklund and John Hawthorne there is an influential semantic argument for a maximally expansive ontology that is thought to undermine even modest forms of quantifier variance. The crucial premise of the argument holds that it is impossible for an ontologically "smaller" language to give a Tarskian semantics for an ontologically "bigger" language. After explaining the Eklund-Hawthorne argument (in section I), we show this crucial premise to be mistaken (in section II) by developing a Tarskian (...) semantics for a mereological universalist language within a mereological nihilist language (a case which we, and Eklund and Hawthorne, take as representative). After developing this semantics we step back (in section III) to discuss the philosophical motivations behind the Eklund- Hawthorne argument’s demand for a semantics. We ultimately conclude that quantifier variantists can meet any demand for a semantics that might reasonably be imposed upon them. (shrink)