In two of the earliest papers on extending modal logic with propositional quantifiers, R. A. Bull and K. Fine studied a modal logic S5Π extending S5 with axioms and rules for propositional quantification. Surprisingly, there seems to have been no proof in the literature of the completeness of S5Π with respect to its most natural algebraic semantics, with propositional quantifiers interpreted by meets and joins over all elements in a complete Boolean algebra. In this note, we give such a proof. (...) This result raises the question: For which normal modal logics L can one axiomatize the quantified propositional modal logic determined by the complete modal algebras for L? (shrink)

Propositional quantifiers are added to a propositional modal language with two modal operators. The resulting language is interpreted over so-called products of Kripke frames whose accessibility relations are equivalence relations, letting propositional quantifiers range over the powerset of the set of worlds of the frame. It is first shown that full second-order logic can be recursively embedded in the resulting logic, which entails that the two logics are recursively isomorphic. The embedding is then extended to all sublogics containing the logic (...) of so-called fusions of frames with equivalence relations. This generalizes a result due to Antonelli and Thomason, who construct such an embedding for the logic of such fusions. (shrink)

A typical approach to semantics for relevance (and other) logics: specify a class of algebraic structures and take amodelto be one of these structures, α, together with some function or relation which associates with every formulaAa subset ofα. (This is the approach of, among others, Urquhart, Routley and Meyer and Fine.) In some cases there are restrictions on the class of subsets of α with which a formula can be associated: for example, in the semantics of Routley and Meyer [1973], (...) a formula can only be associated with subsets which are closed upwards. It is natural to take apropositionof α to be such a subset of α, and, further, to take the propositional quantifiers to range over these propositions. (Routley and Meyer [1973] explicitly consider this interpretation.) Given such an algebraic semantics, we call (following Routley and Meyer [1973], who follow Henkin [1950]) the above-described interpretation of the quantifiers theprimaryinterpretation associated with the semantics. (shrink)

This new edition of Introduction to Lattices and Order presents a radical reorganization and updating, though its primary aim is unchanged. The explosive development of theoretical computer science in recent years has, in particular, influenced the book's evolution: a fresh treatment of fixpoints testifies to this and Galois connections now feature prominently. An early presentation of concept analysis gives both a concrete foundation for the subsequent theory of complete lattices and a glimpse of a methodology for data analysis that is (...) of commercial value in social science. Classroom experience has led to numerous pedagogical improvements and many new exercises have been added. As before, exposure to elementary abstract algebra and the notation of set theory are the only prerequisites, making the book suitable for advanced undergraduates and beginning graduate students. It will also be a valuable resource for anyone who meets ordered structures. (shrink)

The principle of universal instantiation plays a pivotal role both in the derivation of intensional paradoxes such as Prior’s paradox and Kaplan’s paradox and the debate between necessitism and contingentism. We outline a distinctively free logical approach to the intensional paradoxes and note how the free logical outlook allows one to distinguish two different, though allied themes in higher-order necessitism. We examine the costs of this solution and compare it with the more familiar ramificationist approaches to higher-order logic. Our assessment (...) of both approaches is largely pessimistic, and we remain reluctantly inclined to take Prior’s and Kaplan’s derivations at face value. (shrink)

In _Modal Logic for Open Minds,_ Johan van Benthem provides an up-to-date introduction to the field of modal logic, outlining its major ideas and exploring the numerous ways in which various academic fields have adopted it. Van Benthem begins with the basic theories of modal logic, semantics, bisimulation, and axiomatics, and also covers more advanced topics, such as expressive power and computational complexity. The book then moves to a wide range of applications, including new developments in information flow, intelligent agency, (...) and games. Taken together, the chapters show modal logic at the crossroads of philosophy, mathematics, linguistics, computer science, and economics. Most of the chapters are followed by exercises, making this volume ideal for undergraduate and graduate students in philosophy, computer science, symbolic systems, cognitive science, and linguistics. (shrink)

According to propositional contingentism, it is contingent what propositions there are. This paper presents two ways of modeling contingency in what propositions there are using two classes of possible worlds models. The two classes of models are shown to be equivalent as models of contingency in what propositions there are, although they differ as to which other aspects of reality they represent. These constructions are based on recent work by Robert Stalnaker; the aim of this paper is to explain, expand, (...) and, in one aspect, correct Stalnaker's discussion. (shrink)

The system obtained by adding full propositional quantification to S5 is known to be decidable, while that obtained by doing so for T is known to be recursively intertranslatable with full second-order logic. Recently it was shown that the system with two S5 operators and full propositional quantification is also recursively intertranslatable with second-order logic. This note establishes that the map assigning [1][2]p to \squarep provides a validity and satisfaction preserving translation between the T system and the double S5 system, (...) thus providing an easier proof of the recent result. (shrink)

A Mathematical Introduction to Logic, Second Edition, offers increased flexibility with topic coverage, allowing for choice in how to utilize the textbook in a course. The author has made this edition more accessible to better meet the needs of today's undergraduate mathematics and philosophy students. It is intended for the reader who has not studied logic previously, but who has some experience in mathematical reasoning. Material is presented on computer science issues such as computational complexity and database queries, with additional (...) coverage of introductory material such as sets. Increased flexibility of the text, allowing instructors more choice in how they use the textbook in courses. Reduced mathematical rigour to fit the needs of undergraduate students. (shrink)

The aim of this book is to present the fundamental theoretical results concerning inference rules in deductive formal systems. Primary attention is focused on: admissible or permissible inference rules the derivability of the admissible inference rules the structural completeness of logics the bases for admissible and valid inference rules. There is particular emphasis on propositional non-standard logics (primary, superintuitionistic and modal logics) but general logical consequence relations and classical first-order theories are also considered. The book is basically self-contained and special (...) attention has been made to present the material in a convenient manner for the reader. Proofs of results, many of which are not readily available elsewhere, are also included. The book is written at a level appropriate for first-year graduate students in mathematics or computer science. Although some knowledge of elementary logic and universal algebra are necessary, the first chapter includes all the results from universal algebra and logic that the reader needs. For graduate students in mathematics and computer science the book is an excellent textbook. (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.

Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers ∀p, ∃p, where the propositional variables range over upward-closed subsets of the set of worlds in a Kripke structure. If the permitted accessibility relations are arbitrary partial orders, the resulting logic is known to be recursively isomorphic to full second-order logic (Kremer, 1997). It is shown that if the Kripke structures are restricted to trees of at height and width at most ω, the resulting logics are decidable. (...) This provides a partial answer to a question by Kremer. The result also transfers to modal S4 and some Gödel-Dummett logics with quantifiers over propositions. (shrink)

We define a propositionally quantified intuitionistic logic Hπ + by a natural extension of Kripke's semantics for propositional intutionistic logic. We then show that Hπ+ is recursively isomorphic to full second order classical logic. Hπ+ is the intuitionistic analogue of the modal systems S5π +, S4π +, S4.2π +, K4π +, Tπ +, Kπ + and Bπ +, studied by Fine.

A propositional system of modal logic is second-order if it contains quantifiers ∀p and ∃p, which, in the standard interpretation, are construed as ranging over sets of possible worlds (propositions). Most second-order systems of modal logic are highly intractable; for instance, when augmented with propositional quantifiers, K, B, T, K4 and S4 all become effectively equivalent to full second-order logic. An exception is S5, which, being interpretable in monadic second-order logic, is decidable.

In this paper I shall present some of the results I have obtained on modal theories which contain quantifiers for propositions. The paper is in two parts: in the first part I consider theories whose non-quantificational part is S5; in the second part I consider theories whose non-quantificational part is weaker than or not contained in S5. Unless otherwise stated, each theory has the same language L. This consists of a countable set V of propositional variables pl, pa, ... , (...) the operators v (or), ~ (not) and □ (necessarily), the universal quantifier (p), p a propositional variable, and brackets ( and ). The formulas of L are then defined in the usual way. (shrink)

In this thesis, I deal with the notions of a condition holding for some proposition and a proposition being true in a certain number of possible worlds. These notions are called propositional quantifiers and numerical modalizers respectively. In each chapter, I attempt to dispose of a system. A system consists of: a language; axioms and rules of inference; and an interpretation. To dispose of a system is to prove its decidability and its consistency and completeness for the given interpretation. I (...) shall, in passing, make applications to de definability, translatability and other topics. In Chapter 1, I consider the system 5SQ. Its language is that of 55 with Q as a fresh unary operator. Its axioms and rules of inference are those for 85 plus the following special axiom-schemes for Q: 1) QA::>MA 2) Q A ::> L V L 3) L ::> 4) Q A ::> L Q A. 'QA' is interpreted as 'A is true in exactly one possible world.' I dispose of the system by showing that every formula in it is equivalent to one in normal form. In Chapter 2 I consider the system S5n. Its language is that of S5 but with the unary operators Qk for each non-negative integer k. Its axioms and rules are those of S5 plus the following special axiom-schemes for Qk: 1) Qk A>~Q1 A, 1˂K 2) Qk A ≡ Vki≡oQi ˄ Qk-I 3) L ˂ 4) Qk A ˂ L Qk A 5) Qo A ≡ L ~ A, 1 ≥ 0, k ≥ 1 ‘Qk A’ is interpreted as 'A is true in exactly k possible worlds.' I dispose of this system by generalising the normal forms of S5Q. In the chapters 3-5, I consider three systems which result from adding propositional quantifiers to S5. The first two systems, S5╥+ and S5╥, contain the usual axioms and rules for quantifiers. The first contains, in addition, the axiom-scheme G = )). The last, S5╥-, results from S5╥ by restricting the Scheme of Specification, viz., A > A, B free for P in A, to formulas B of the propositional calculus. To interpret these systems we must specify which propositions the variable P ranges over. For St╥-, we merely require that if p and q are propositions, then and are also propositions. For S5╥+, we also require that each possible world be describable i.e. that there be a proposition which is true in that world alone. And for S5╥, we require not that each possible world be describable but that there be a proposition which is true in just those possible worlds which are describable. Again, we dispose of the systems by normal forms. This requires that we eliminate quantifiers and nested occurrences of L by adding new symbols to the language. For S5╥+, the operators Qk suffice. For S5╥, the operators Qk suffice. For S5╥, we also require the constant g and a fresh unary operator N. For S5╥-, even greater additions are required. In the last two chapters, 6 and 7, I turn to systems which have essentially the same language as S5╥. However, ‘Qk A' is now interpreted as 'A is true in exactly k possible worlds accessible from the given world.' Different conditions on R, the relation of accessibility, lead to different axioms. In chapter 6 I consider the conditions of reflexivity, symmetry and transitivity, and in Chapter 7 the conditions of being a partial, convergent, total or dense order. I prove consistency and completeness by the method of maximally consistent systems. The method can yield decidability results, but I do not go into the matter. I have, as a rule, not given acknowledgements for well-established results or terminology. The main references are at the end of each chapter. Fuller references are in the bibliography. (shrink)

This paper argues for two theses: that degrees of belief are context sensitive; that outright belief is belief to degree 1. The latter thesis is rejected quickly in most discussions of the relationship between credence and belief, but the former thesis undermines the usual reasons for doing so. Furthermore, identifying belief with credence 1 allows nice solutions to a number of problems for the most widely-held view of the relationship between credence and belief, the threshold view. I provide a sketch (...) of a formal framework on which both theses are true. This is a modified Bayesian framework; I argue that despite making credences context-sensitive, the framework lets Bayesians hold on to their signature explanatory successes. The sort of context-sensitivity claimed for credences here mirrors the sort of context-sensitivity I have elsewhere claimed for outright belief: one's credences depend, in part, on the space of alternative possibilities one takes seriously in a context. (shrink)

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)

Stalnaker, 169–199 2006) introduced a combined epistemic-doxastic logic that can formally express a strong concept of belief, a concept of belief as ‘subjective certainty’. In this paper, we provide a topological semantics for belief, in particular, for Stalnaker’s notion of belief defined as ‘epistemic possibility of knowledge’, in terms of the closure of the interior operator on extremally disconnected spaces. This semantics extends the standard topological interpretation of knowledge with a new topological semantics for belief. We prove that the belief (...) logic KD45 is sound and complete with respect to the class of extremally disconnected spaces and we compare our approach to a different topological setting in which belief is interpreted in terms of the derived set operator. We also study belief revision as well as belief dynamics by providing a topological semantics for conditional belief and belief update modalities, respectively. Our setting based on extremally disconnected spaces, however, encounters problems when extended with dynamic updates. We then propose a solution consisting in interpreting belief in a similar way based on hereditarily extremally disconnected spaces, and axiomatize the belief logic of hereditarily extremally disconnected spaces. Finally, we provide a complete axiomatization of the logic of conditional belief and knowledge, as well as a complete axiomatization of the corresponding dynamic logic. (shrink)

I am interested in extending modal calculi by adding propositional quantifiers, given by the rules for quantifier introduction: provided that p does not occur free in A.

Robert Stalnaker has recently advocated propositional contingentism, the claim that it is contingent what propositions there are. He has proposed a philosophical theory of contingency in what propositions there are and sketched a possible worlds model theory for it. In this paper, such models are used to interpret two propositional modal languages: one containing an existential propositional quantifier, and one containing an existential propositional operator. It is shown that the resulting logic containing an existential quantifier is not recursively axiomatizable, as (...) it is recursively isomorphic to second-order logic, and a natural candidate axiomatization for the resulting logic containing an existential operator is shown to be incomplete. (shrink)

In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of van Benthem, “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, ${\cal V}$-baos. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s article resolves the open question (...) in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to ${\cal V}$-baos, namely the provability logic $GLB$. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is ${\cal V}$-complete. After these results, we generalize the Blok Dichotomy to degrees of ${\cal V}$-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness. (shrink)

Many criticisms of epistemic logic have centered around its use of devices such as idealized knowers with logical omniscience and perfect self-knowledge. One possible response to such criticisms is to say that these idealizations are normative devices, and that epistemic logic tells us how agents ought to behave. This paper will take a different approach, treating epistemic logic as descriptive, and drawing the analogy between its formal models and idealized scientific models on that basis. Treating it as descriptive matches the (...) way in which some philosophers, including one of its founders, Jaako Hintikka, have thought about epistemic logic early in its history. Further, the analogy between the two fields will give us a way to defuse criticisms that see epistemic logic as unrealistic. For example, criticizing models of epistemic logic in which agents know all propositional tautologies as being unrealistic would be like criticizing frictionless planes in physics for being unrealistic. Each one would certainly be an unsuitable model for studying some kinds of phenomena, but is entirely appropriate for others. After outlining the analogy between epistemic and scientific models, we will discuss some ways in which idealizations are used by different research programs in epistemic logic. (shrink)

We show that (contrary to the parallel case of intuitionistic logic, see [7], [4]) there does not exist a translation fromS42 (the propositional modal systemS4 enriched with propositional quantifiers) intoS4 that preserves provability and reduces to identity for Boolean connectives and.

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.

It is shown that the expressive power of second-order propositional modal logic whose modalities are S4.2 or weaker is the same as that of second-order predicate logic.

In this paper we are discussing a version of propositional belief logic, denoted by LB, in which so-called axioms of introspection (B BB and B B B) are added to the usual ones. LB is proved to be sound and complete with respect to Boolean algebras equipped with proper filters (Theorem 5). Interpretations in classical theories (Theorem 4) are also considered. A few modifications of LB are further dealt with, one of which turns out to be S5.

We generalize the notion of a monadic algebra to that of a pseudomonadic algebra. In the same way as monadic algebras serve as algebraic models of epistemic modal system S5, pseudomonadic algebras serve as algebraic models of doxastic modal system KD45. The main results of the paper are: Characterization of subdirectly irreducible and simple pseudomonadic algebras, as well as Tokarz's proper filter algebras; Ordertopological representation of pseudomonadic algebras; Complete description of the lattice of subvarieties of the variety of pseudomonadic algebras.