﻿ First-order Modal Logic | Melvin Fitting, Richard L. Mendelsohn | download
الرئيسية First-order Modal Logic

First-order Modal Logic



Categories: Mathematics\\Logic
السنة: 1998
الناشر: Springer
اللغة: english
الصفحات: 292 / 299
ISBN 10: 0792353358
ISBN 13: 9780792353355
ISBN: 079235334X
Series: Synthese Library 277
File: DJVU, 2.00 MB
تحميل (djvu, 2.00 MB)

Handbook of Philosophical Logic

السنة: 2003
اللغة: english
File: DJVU, 2.95 MB

Sets, logic, and numbers

السنة: 1969
اللغة: english
File: DJVU, 2.84 MB

SYNTHESE LIBRARY STUDIES IN EPISTEMOLOGY, LOGIC, METHODOLOGY, AND PHILOSOPHY OF SCIENCE Managing Editor: JAAKKO HINTIKKA, Boston University Editors: DIRK VAN DALEN, University of Utrecht, The Netherlands DONALD DAVIDSON, University of California, Berkeley THEO A.F. KUIPERS, University ofGroningen, The Netherlands PATRICK SUPPES, Stanford University, California JAN WOLENSKI, Jagiellonian University, Krakow, Poland VOLUME 277


A CLP. Catalogue record for this book is available from the Library of Congress. ISBN 978-0-7923-5335-5 ISBN 978-94-011-5292-1 (eBook) DOI 10.1007/978-94-011-5292-1 Printed on acid-free paper All Rights Reserved © 1998 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1998 Softcover reprint of the hardcover 1st edition 1998 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner

To Marsha, Robin, and Josh, with love RLM To Roma, who knows what I mean MF

CONTENTS PREFACE xi CHAPTER ONE / PROPOSITIONAL MODAL LOGIC 1 1.1 What is a Modal? 2 1.2 Can There Be a Modal Logic? 3 1.3 What Are The Formulas? 5 1.4 Aristotle's Modal Square 7 1.5 Informal Interpretations 8 1.6 What Are the Models? 11 1.7 Examples 14 1.8 Some Important Logics 18 1.9 Logical Consequence 21 1.10 Temporal Logic 24 1.11 Epistemic Logic 28 1.12 Historical Highlights 32 CHAPTER TWO / Tableau Proof Systems 46 2.1 What Is a Proof 46 2.2 Tableaus 47 2.3 More Tableau Systems 51 2.4 Logical Consequence and Tableaus 55 2.5 Tableaus Work 57 CHAPTER THREE / Axiom Systems 67 3.1 What Is an Axiomatic Proof 67 3.2 More Axiom Systems 71 3.3 Logical Consequence, Axiomatically 73 3.4 Axiom Systems Work Too 74 CHAPTER FOUR / Quantified Modal Logic 81 4.1 First-Order Formulas 81 4.2 An Informal Introduction 83 4.3 Necessity De Re and De Dicto 85 4.4 Is Quantified Modal Logic Possible? 89 vn

Vlll CONTENTS 4.5 What the Quantifiers Quantify Over 92 4.6 Constant Domain Models 95 4.7 Varying Domain Models 101 4.8 Different Media, Same Message 105 4.9 Barcan and Converse Barcan Formulas 108 CHAPTER FIVE / First-Order Tableaus 116 5.1 Constant Domain Tableaus 116 5.2 Varying Domain Tableaus 118 5.3 Tableaus Still Work 121 CHAPTER SIX / First-Order Axiom Systems 132 6.1 A Classical First-Order Axiom System 132 6.2 Varying Domain Modal Axiom Systems 135 6.3 Constant Domain Systems 136 6.4 Miscellany 138 CHAPTER SEVEN / Equality 140 7.1 Classical Background 140 7.2 Frege's Puzzle 142 7.3 The Indiscernibility of Identicals 145 7.4 The Formal Details 149 7.5 Tableau Equality Rules 150 7.6 Tableau Soundness and Completeness 152 7.7 An Example 159 CHAPTER EIGHT / Existence and Actualist Quantification 163 8.1 To Be 163 8.2 Tableau Proofs 165 8.3 The Paradox of NonBeing 167 8.4 Deflationists 169 8.5 Parmenides' Principle 172 8.6 Inflationists 175 8.7 Unactualized Possibles 178 8.8 Barcan and Converse Barcan, Again 180 8.9 Using Validities in Tableaus 182 8.10 On Symmetry 185 CHAPTER NINE / Terms and Predicate Abstraction 187 9.1 Why constants should not be constant 187 9.2 Scope 190

CONTENTS IX 9.3 Predicate Abstraction 194 9.4 Abstraction in the Concrete 195 9.5 Reading Predicate Abstracts 200 CHAPTER TEN / Abstraction Continued 204 10.1 Equality 204 10.2 Rigidity 210 10.3 A Dynamic Logic Example 216 10.4 Rigid Designators 217 10.5 Existence 220 10.6 Tableau Rules, Varying Domain 221 10.7 Tableau Rules, Constant Domain 227 CHAPTER ELEVEN / DESIGNATION 230 11.1 The Formal Machinery 231 11.2 Designation and Existence 233 11.3 Existence and Designation 235 11.4 Fiction 241 11.5 Tableau Rules 245 CHAPTER TWELVE / DEFINITE DESCRIPTIONS 248 12.1 Notation 248 12.2 Two Theories of Descriptions 249 12.3 The Semantics of Definite Descriptions 253 12.4 Some Examples 255 12.5 Hintikka's Schema and Variations 261 12.6 Varying Domain Tableaus 265 12.7 Russell's Approach 273 12.8 Possibilist Quantifiers 275 REFERENCES 277 INDEX 283

PREFACE After a rocky start in the first half of the twentieth century, modal logic hit its stride in the second half. The introduction of possible world semantics around the mid-century mark made the difference. Possible world semantics provided a technical device with intuitive appeal, and almost overnight the subject became something people felt they understood, rightly or wrongly. Today there are many books that deal with modal logic. But with very few exceptions, treatments are almost entirely of propositional modal logic. By now this is a well-worked area, and a standard part of philosophical training. First- order modal logic, on the other hand, is under-represented in the literature and under-developed in fact. This book aims at correcting the situation. To make our book self-contained, we begin with propositional modal logic, and our presentation here is typical of the entire book. Our basic approach is semantic, using possible world, or Kripke, models. Proof-theoretically, our machinery is semantic tableaus, which are easy and intuitive to use. (We also include a treatment of propositional axiom systems, though axiom systems do not continue throughout the book.) Philosophically, we discuss the issues that motivate formal modal logics, and consider what bearing technical developments have on well-known philosophical problems. This three-pronged approach, Kripke semantics, tableaus, philosophical discussion, reappears as each new topic is introduced. Classically, first-order issues like constant and function symbols, equality, quantification, and definite descriptions, have straightforward formal treatments that have been standard items for a long time. Modally, each of these items needs rethinking. First-order modal logic, most decidedly, is not just propositional modal logic plus classical quantifier machinery. The situation is much subtler than that. Indeed, many of the philosophical problems attending the development of modal logic have arisen because of the myopia of looking at it through classical lenses. For this reason we initially develop first-order modal logic without constants and functions. This arrangement separates the philosophical problems due to names and definite descriptions from those of quantifiers, and facilitates the development and understanding of first-order modal notions. Successive chapters are arranged along the following lines. First, as we said, we introduce the quantifiers, and address the difference between actualist quantification (where quantifiers range over what actually exists) and pos- sibilist quantification (where they range over what might exist). Semantically, XI

Xll PREFACE this is the difference between varying domain models and constant domain models. (If you don't know what this means, you will.) Next, we introduce equality. We discuss Frege's well-known morning star/evening star puzzle in this modal context, while presenting a formal treatment of equality. We then return to the matter of actualist and possibilist quantification and show how to embed possibilist quantification in an actualist framework and conversely. By this point in the exposition we are dealing both with a defined notion of existence as well as a primitive notion, and the time is ripe for a full-fledged discussion of the logical problems with existence and, in particular, of the idea that there are things that could exist but don't. Only after all of this has been examined are constants and function names introduced, along with the idea of predicate abstraction and rigidity. Predicate abstraction is perhaps the most central notion of our treatment. This is a syntactic mechanism for abstracting a predicate from a formula, in effect providing a scoping mechanism for constants and function symbols similar to that provided for variables by quantifiers. Using predicate abstraction we are able to deepen the understanding of singular terms and reference, enabling distinctions that were either not visible or only dimly visible classically. Since the variable binding of predicate abstracts behaves similarly to the variable binding of quantifiers, analogues to some of the issues involving Barcan and converse Barcan formulas crop up again. We continue our discussion of nonexistence by distinguishing it from nondesignation: we contrast terms that designate a nonexistent, e.g., "the golden mountain," and terms that fail to designate at all, e.g., "the round square." In the final chapter we present formal machinery for definite descriptions that borrows from both the Fregean and Russellian paradigms, and builds on the work in earlier chapters concerning these issues of existence and designation. A primary goal of this text is to present first-order modal logic in an intuitively appealing way, so as to make more widely available versatile machinery for a new perspective on issues in philosophy of language and in metaphysics. Among other things, modal logic is a logic of change. It is our hope that this text on first-order modal logic will be an agent of change, sweeping through philosophical discussions, bringing a freshness, liveliness, and new vigor to ancient issues. We wish to thank Graham Priest for very helpful comments on a draft of the manuscript for this book.

CHAPTER ONE PROPOSITIONAL MODAL LOGIC For analytic philosophy, formalization is a fundamental tool for clarifying language, leading to better understanding of thoughts expressed through language. Formalization involves abstraction and idealization. This is true in the sciences as well as in philosophy. Consider physics as a representative example. Newton's laws of motion formalize certain basic aspects of the physical universe. Mathematical abstractions are introduced that strip away irrelevant details of the real universe, but which lead to a better understanding of its "deep" structure. Later Einstein and others proposed better models than that of Newton, reflecting deeper understanding made possible by the experience gained through years of working with Newton's model. "Model" is the key word here. A mathematical model of the universe is not the universe. It is an aid to the understanding—an approximately correct, though partial, description of the universe. As the Newton/Einstein progression shows, such models can improve with time, thought, and investigation. What we present in this book is a mathematical model of the modal aspects of language. We apply formal techniques to clarify the interactions of modal issues with other important notions such as identity, names, and definite descriptions. We intersperse our formal mathematical presentation with discussions of the underlying philosophical problems that elucidate the basic issues. In order to present a logic formally, several separate items are necessary. We need a rigorously defined language of course, but by itself this is pure, uninterpreted syntax. To give meaning to formulas of a language, we need a semantics that lets us single out those formulas we are primarily interested in, the valid ones. We also want a notion of proof, so that we can write down compact verifications that certain formulas are valid. And finally, we must connect the notion of proof with the semantics, so we can be sure it is exactly the valid formulas that have proofs. We assume you are familiar with all this for classical propositional logic. There, truth tables provide the semantics—valid formulas are those for which every line evaluates to T (such formulas are generally called tautologies). You may have seen axiom systems for classical propositional logic, or tableau (tree) proof systems, or natural deduction systems. Since modal notions are more complex than propositional ones, one expects modal semantics and proof systems to be correspondingly more complex. Such expectations will be fulfilled shortly. 1

2 CHAPTER ONE In this chapter we present syntax and semantics for several propositional modal logics. Proof systems follow in Chapters 2 and 3. Our treatment is relatively terse because propositional logics are not the main topic of this book; first-order modal logic is. Our treatment of this begins in Chapter 4. For fuller presentations of propositional modal logic, see (Hughes and Cress- well, 1968), (Hughes and Cresswell, 1984), (Hughes and Cresswell, 1996), (Chellas, 1980) or (Fitting, 1983). With all this very general background, we still have not said what kinds of things modal notions are. It is time to begin. l.l. What is a Modal? A modal qualifies the truth of a judgment. Necessarily and possibly are the most important and best known modal qualifiers. They are called "alethic" modalities, from the Greek word for truth. In traditional terminology, Necessarily P is an "apodeictic judgment," Possibly P a "problematic judgment," and P, by itself, an "assertoric judgment." The most widely discussed modals apart from the alethic modalities are the temporal modalities, which deal with past, present, and future ("will be," "was," "has been," "will have been," etc.), the deontic modalities, which deal with obligation and permission ("may," "can," "must," etc.) and the epistemic or doxastic modalities, which deal with knowledge and belief ("certainly," "probably," "perhaps," "surely," etc.). Prior (1955), perhaps a bit tongue-in- cheek, quotes the 18th century logician Isaac Watts to show the variety of modals that are available: We might also describe several moral or civil Modes of connecting two Ideas together (viz.) Lawfulness and Unlawfulness, Conveniency and Inconveniency, etc. whence we may form such modal Propositions as these: ... It is lawful for Christians to eat Flesh in Lent.... There are several other Modes of speaking whereby a Predicate is connected with a Subject: Such as, it is certain, it is doubtful, it is probable, it is improbable, it is agreed, it is granted, it is said by the ancients, it is written etc. all which will form other Kinds of modal Propositions, (p. 215-216) The modals capture what traditional linguists have categorized as tense, mood and aspect, but which, in more modern treatments of grammar, are lumped together as adverbials, i.e., as modifiers of adjectives or verbs, and, derivatively, of nouns. In the sentence-frame, John is happy the blank space can be filled by any of the modals: necessarily, possibly, contingently, known by me to be, believed by you to be, permitted to be, now,

PROPOSITIONAL MODAL LOGIC 3 then. Alternatively, these qualifiers can be inserted into the sentence-frame It is true that John is happy and regarded as modifying the truth of the claim. Hence the two equivalent characterizations: the modal qualifies the predicate, or the modal qualifies the truth of a claim. Not all modals give rise to modal logics, however. Usually there must be two modal operators that conform to the logical principles embodied in the Modal Square of Opposition (Section 1.4, Figure 1). But this is to presuppose that a logic of the modals is even possible, a view that has been much debated in the philosophical literature. Before we introduce the Square of Opposition, then, we will discuss these issues. Exercises EXERCISE 1.1.1. Discuss the following. 1. Is 'probably' a modal? 2. Is 'truly' a modal? 3. Is 'needless to say' a modal? 4. Is 'not' a modal? 1.2. Can There Be a Modal Logic? Aristotle set the tone for the older tradition of logic—a tradition that stretched from antiquity, through the medieval period, as far as Leibniz—by including the study of modality in his book on the syllogism: Since there is a difference according as something belongs, necessarily belongs, or may belong to something else (for many things belong indeed, but not necessarily, others neither necessarily nor indeed at all, but it is possible for them to belong), it is clear that there will be different syllogisms to prove each of these relations, and syllogisms with differently related terms, one syllogism concluding from what is necessary, another from what is, a third from what is possible. Prior Analytics i. 8 (29*29 -35) in (Ross, 1928) The modal syllogism never attained the near universal acceptance of Aristotle's more familiar logic of categorical statements, partly because of serious confusions in his treatment (documented by Kneale and Kneale (1962)). The same problems infected the discussions of many who followed him. Indeed, Kneale (1962) quotes a medieval logician who warns students away

4 CHAPTER ONE from the study of modality if they are to retain their sanity! Modality was closely linked with theological speculation and the metaphysics of the schoolmen, both of which were largely repudiated by the Enlightenment. The combination of interminable confusions and discredited metaphysics has given sustenance to those who have urged that there cannot be a modal logic. The primary claim of the opposition is that modality has no place in the content of a judgment, so that the modal is inert with regard to the logical connections between that judgment and others. Kant (1781) is representative. Here is what he says about the category of the modals presented in his Table of Judgments in Book I of the Transcendental Analytic: The modality of judgments is a quite peculiar function. Its distinguishing characteristic is that it contributes nothing to the content of the judgment (for, besides quantity, quality, and relation, there is nothing that constitutes the content of a judgment), but concerns only the value of the copula in relation to thought in general, (p. 10) And Kant's assessment was echoed by Frege (1879): What distinguishes the apodeictic from the assertoric judgment is that it indicates the existence of general judgments from which the proposition may be inferred—an indication that is absent in the assertoric judgment. If I term a proposition 'necessary,' then I am giving a hint as to my grounds for judgment. But this does not affect the conceptual content of the judgment; and therefore the apodeictic form of a judgment has not for our purposes any significance, (p. 4) Frege (1879) laid the groundwork for the modern treatment of logic by providing a notation and a set of axioms and rules of inference for propositional, first-order, and higher-order logic. His decision to omit modality was an influential factor in delaying the contemporary development of modal logic. Frege's remarks above are found in a section where he explains which distinctions he will attempt to capture in his logical symbolism, and which he will not. His Begriffsschrift (literally, Concept Script) was designed to capture conceptual content, "that part of judgments which affects the possible inferences .... Whatever is needed for a valid inference is fully expressed; what is not needed is for the most part not indicated either ... ." (p. 3) Compare, for example, "The Greeks defeated the Persians at Plataea" and "The Persians were defeated by the Greeks at Plataea." The active and passive forms of a judgment, he argues, each have exactly the same inferential connections—any judgment that entails (or is entailed by) the first entails (or is entailed by) the second. The grammatical distinction may therefore be of psychological significance, but it is of no logical significance, so the active/passive distinction is not formally marked. By contrast, there is a clear logical distinction between "The Greeks defeated the Persians at Plataea and Thermopylae," on the one hand, and "The Greeks defeated the Persians at Plataea or Thermopylae," on

PROPOSITIONAL MODAL LOGIC 5 the other; and both conjunction and disjunction are therefore represented in his Begriffsschrift. It is true, as Frege says, that the content represented by P remains the same whether preceded by "necessarily," "possibly," or nothing at all. But it does not follow that the apodeictic, problematic and assertoric judgments all have the same conceptual content. Contrary to what Frege says, modal distinctions do affect possible inferences. Let us avail ourselves of modern notation: OP for It is necessary that P and 0^ for It is possible that P. Now, pdOp (i.e., Ifs actual, so ifs possible) is usually considered to be valid—Hughes and Cresswell (1968) call it the "Axiom of Possibility"—but its converse, OPd p (i.e., Ifs possible, so ifs actual) is not. By Frege's own criterion, P and OP differ in conceptual content. Frege's logic does not capture these formal inferences, but they are inferences nonetheless, and there is no compelling reason why logic should not be widened to accommodate them. Can there be a modal logic, then? There is no a priori reason why not. The most effective way of showing that there can be a modal logic is to actually construct one. We will construct several! 1.3. What Are The Formulas? Now it is time to be more specific about the formal language we will be using. The language of propositional modal logic extends that of classical propos- itional logic. Classically, formulas are built up from propositional letters (also called propositional variables). We use P, Q, R, etc. for these—they stand for unanalyzed propositions. (Sometimes one also allows propositional constants, T and _L, intended to represent truth and falsehood respectively. We generally will not. Propositional letters are combined into more elaborate formulas using propositional connectives such as -i (not), A (and), v (or), D (if, then), = (if, and only if), etc. The first, -% is unary, while the others are binary. There are other binary connectives besides these, so the list can be longer. On the other hand, it is possible to define some of these from others—both proof-theoretically and semantically—so the list can be shorter. We will sometimes take one approach, sometimes the other, depending on convenience. What is added to this syntax of classical logic are two new unary operators, □ (necessarily) and 0 (possibly). Again, it will turn out these are interdefin- able, so the list can be shorter. Also there are various multi-modal logics, so the list can be longer. We will say more about such variations later.

6 CHAPTER ONE DEFINITION 1.3.1. [Propositional Modal Formulas] The set of (proposi- tional modal) formulas is specified by the following rules. 1. Every propositional letter is a formula. 2. If X is a formula, so is ->X. 3. If X and Y are formulas, and o is a binary connective, (XoY) is a formula. 4. If X is a formula, so are DX and OX. Using this definition, for example, ((DP A 02) ^ 0(^ A Q)) is a formula. It can be read, "If P is necessary, and Q is possible, then it is possible that both P and g." Informally, we will generally omit the outer parentheses of a formula. Thus the formula we just gave may appear as (DP A 02) ^ 0(P A Q). We are using □ and 0 to symbolize modal operators. Some books, following a different tradition, use L and M instead—(Hughes and Cresswell, 1996) is an example. In addition, when considering issues of knowledge, X is often used in place of D. If more than one person's knowledge is concerned, Xa, Xt>, etc. may be used—this is an example of a multi-modal logic. Likewise, modal operators corresponding to actions can be considered. For example, the action might be that of going from New York to San Francisco. If □ is intended to denote this action, then if P is the proposition, "It is 1pm," and Q is the proposition "It is after 2pm," then P D DQ would be read, "If it is 1pm, then after I go from New York to San Francisco (no matter how I do so), it will be after 2pm." A modal logic intended for consideration of actions would also naturally be a multi-modal logic, since there are many different actions—generally the notation involves □ with action-denoting letters placed inside. In this book we confine our presentation to just □ and 0 since, if the formal aspects of these two are firmly understood, generalizations are fairly straightforward. Exercises EXERCISE 1.3.1. Using the definition verify that, in fact, ((DP A 02) D 0(P A g)) is a formula.

PROPOSITIONAL MODAL LOGIC 7 1.4. Aristotle's Modal Square A rough minimal requirement for a modal logic is that □ and 0 satisfy the Modal Square of Opposition given below in Figure 1. (Additional requirements have been suggested, but there is no generally accepted standard. See (Lukasiewicz, 1953; Bull and Segerberg, 1984; Koslow, 1992) for alternatives.) The Modal Square is due to Aristotle, who worked out the basic logical connections between necessity and possibility in his De Interpretations In Chapter 12, he argued that the negation of (1.1) It is possible that P is not "It is possible that not P," but rather "It is not possible that P." Similarly, he argued that the negation of "It is necessary that P" is not "It is necessary that not P," but rather "It is not necessary that P." In Chapter 13, he connected up the two modalities by identifying (1.2) It is not necessary that not P. as the equivalent of (1.1). Aristotle's claim that (1.1) is equivalent to (1.2) reflects the standard (first half) of the interdefinability of the two modal operators: OP = -CHP DP = -0-P. And we thereby get the Modal Square of Opposition given in Figure 1. It is necessary that P It is necessary that not P It is not possible that not P It is not possible that P \s /\ It is not necessary that not P It is not necessary that P It is possible that P It is possible that not P Figure 1. The Modal Square of Opposition The Modal Square of Opposition is analogous to the more familiar Square of Opposition for Categorical Statements given in Figure 2. In both cases the schemata across the top row are contraries (cannot both be true), the schemata across the bottom row are subcontraries (cannot both be false), the

8 CHAPTER ONE All F are G No Fare G Some F are G Some F are not G Figure 2. The Square of Opposition for Categorical Statements schemata in each column are subalternatives (the top implies the bottom), and the schemata across the diagonals are contradictories (cannot have the same truth value).1 1.5. Informal Interpretations In Section 1.1, we characterized a modal as an adverbial that fills the blank in a sentence frame like John is happy. The situation is actually somewhat more complicated. Adverbials differ in their favored placement. Necessarily must precede the adjective; now and then can occur either before or after the adjective; here and there must come after the adjective. These are peculiarities of English, and are independent of the underlying logical sense. In what follows, we will find it helpful to standardize the frame, with the modifier coming after the adjective, like this: John is happy , The modal we insert qualifies John's happiness, opening up a spectrum along which modifications of his happiness can be compared. Let us flesh out the adverbial position as John is happy under interpretation /. Think of an interpretation / as a particular assignment of truth values to the nonlogical particles in the proposition, with the logical particles understood as the usual boolean functions. On the simplest reading of □ and 0, a proposition is necessarily true if it comes out true for every interpretation—i.e., if it 1 This does assume the modal logic is sufficiently strong—at least D (to be introduced soon). Some of these properties do not hold for weaker logics.

PROPOSITIONAL MODAL LOGIC 9 is a logical truth—and a proposition is possibly true if it comes out true for at least one interpretation—i.e., if it is consistent. Our modal propositions □ John is happy 0 John is happy therefore correspond respectively to the quantified propositions (V/) (John is happy under interpretation /) (3/) (John is happy under interpretation /) "John is happy," without a modal operator, is understood as "John is happy under interpretation iq" where /q is the interpretation corresponding to the real world. It is more usual in modal logic to speak of a possible interpretation as a possible world or a possible state. The terminology and the idea that a necessary truth is true in all possible worlds is derived from Leibniz. Let us see how this reading works for DP D P. If P is true in every possible world, then it is true in the actual world. So, this is intuitively a valid claim. P D OP, on the other hand, is an invalid claim. Just because P is true in the actual world, it need not be true in every possible world. Modern modal logic employs a modification of Leibniz's notion by taking into consideration the way in which the modal relates the possible worlds. This is called an accessibility relation. We will have much to say about accessibility, so for now one example must suffice: temporal worlds are ordered by their place in time. Take a world A to be accessible from a world T if T occurs no later in the temporal order than A. A proposition is necessarily true if it is true at every accessible possible world; a proposition is possibly true if it is true at some accessible possible world. Let wt be a possible world, and let wq be the actual world. Let 31 be the accessibility relation: x!Ry is read y is accessible from x. Then □ John is happy corresponds to (yu>i)w0xwi (John is happy at wt) where we read the quantifier as, "for all wt in the relation 31 to w0" or less formally, as, "for all wt accessible from u;0." Consider OP D P again. Once accessibility relations are brought in, this says that if P is true at every accessible possible world, then it is true at the real world. For this to remain valid, the real world must be accessible to itself—which it is, according to the temporal definition just given. But we

10 CHAPTER ONE could have defined the accessibility relation differently, so that the real world is not accessible to itself. In such a setting this formula is not valid. The notion of accessibility, introduced by Kripke (1963a), makes it possible to model a rich variety of modal logics. If we consider interpretations or worlds connected by an accessibility relation, then various algebraic constraints on the relation turn out to correspond to specific modal principles. The formal connection between these algebraic constraints and modal principles is discussed in Section 1.8. Let us see informally how the accessibility relation enables us to extend our understanding of the modal operators. Consider, for example, (1.3) OP D OOP Let 0^ mean It is conceivable that P. Then (1.3) says that if there is a possible world we can conceive of from the actual one—i.e., an accessible (conceivable) world—in which P is true, then from every accessible (conceivable) world there is an accessible (conceivable) world in which P is true. Is this so? If P is conceivable, is it inconceivable that it is inconceivable that PI It is reasonable to suppose that from the standpoint of a Greek disciple of Euclid, it is inconceivable that parallel lines meet; but this is certainly not inconceivable to us. So, from our perspective, it is conceivable that parallel lines meet, making the antecedent of (1.3) true; but there is at least one conceivable situation (putting ourselves in the sandals of an ancient Greek) from which it is inconceivable that parallel lines meet, making the consequent of (1.3) false. Presumably we can put ourselves into the Greek's sandals but he cannot put himself into our shoes, because we know something about the past, but he knows nothing about the future. This means that, in the case of conceivability, the accessibility relation is not symmetric and so (1.3) does not hold. Once accessibility among worlds has been highlighted as the preeminent characteristic of modal logics, we can interpret the modal operators far afield from their originally intended meanings. Harel (1984) gives the flavor of Dynamic Logic. Suppose we are speaking about all possible execution states relevant to some computer program a, and we define an accessibility relation s3iat such that t is a possible next state of a with current state s. We obtain a multi-modal logic with 0P read as, "Every possible execution of a leads to a situation in which P is true," and $P read as, "It is possible to execute a reaching a situation in which P is true." Hence one can generalize the subject called modal logic: it is an attempt to characterize talk of deformations or transitions or alternatives.

PROPOSITIONAL MODAL LOGIC 11 Exercises EXERCISE 1.5.1. There are four truth-table definable functions of a single input. 1. Show that we can define a truth-functional operator □ for which DP D P is a thesis but for which P D DP is not. 2. Show that if we also require that -^DP not be a thesis, no truth-functional operator will do. EXERCISE 1.5.2. Suppose every world is accessible to every other. Would (1.3) then be valid? Discuss informally. 1.6. What Are the Models? Although several formal semantics have been created for modal logics, possible world semantics has become the standard. It was introduced in the 1960's, by Kripke, in (Kripke, 1963b; Kripke, 1963a; Kripke, 1965), and independently by Hintikka, in (Hintikka, 1961; Hintikka, 1962). It provides an elegant mathematical treatment that is intuitively meaningful. Indeed, we have already used it informally in our discussions of the previous section. The notion of possible world is of a piece with standard model-theoretic interpretations of classical logic. As Kripke (1980) says: The main and original motivation for the 'possible world analysis'—and the way it clarified modal logic—was that it enabled modal logic to be treated by the same set theoretic techniques of model theory that proved so successful when applied to extensional logic, (p 19) A valid formula (i.e., logical truth) of classical propositional logic is one that comes out true for every possible assignment of truth values to the statement letters. This notion of alternative interpretations should not pose any more of a philosophical problem in modal logic than it does in classical logic. Put a slightly different way, in so far as there are philosophical difficulties with the notion of possible world, these are difficulties that are already to be found in understanding multiple interpretations for statements of classical logic. The difficulty is exacerbated by the fact that we say in modal logic, "There is a possible world such that... ," and so we quantify over possible worlds. According to a criterion of ontological commitment put forward by Quine (1948), this means that we are committed to the existence of such things. But some of these are intended to be mere possibilities, not actualities, and so we appear to be committed to the existence of things we would not otherwise

12 CHAPTER ONE want to be committed to. It looks as though we have all of a sudden increased our store of existents. Not only do we have the way things are, but also the way things might be. Once again, however, we must underscore that the very same difficulty crops up in the classical case, for we speak there of alternative interpretations, and we consider all possibilities—all truth-table lines—and these are possibilities that cannot all hold simultaneously. Since the notion of possible world is useful and coherent, it is quite clear that the problem is not with the notion of possible world but with the philosophical theories about them. DEFINITION 1.6.1. [Frame] A frame consists of a non-empty set, $, whose members are generally called possible worlds, and a binary relation, «K,on^, generally called the accessibility relation. Since a frame consists of two parts, we follow general mathematical practice and say a frame is a pair, ($, 31), so we have a single object to talk about. Understand that, while possible world is suggestive terminology, it commits us to nothing. In the mathematical treatment of frames, possible worlds are any objects whatsoever—numbers, sets, goldfish, etc. We will generally use T, A, etc. to denote possible worlds. If T and A are in the relation 31, we will write T31/S., and read this as A is accessible from r, or A is an alternative world to T. DEFINITION 1.6.2. [Model] A frame is turned into a modal model by specifying which propositional letters are true at which worlds. We use the following notation for this. A propositional modal model, or model for short, is a triple ($, 31, lh), where ($, Si) is a frame and lh is a relation between possible worlds and propositional letters. If T lh P holds, we say P is true at the world T. If T lh P does not hold we symbolize this by T \f P, and say P is false at T. Incidentally, lh is often read as "forces," a usage which comes from proving the independence results of set theory. In (Smullyan and Fitting, 1996) modal logic is, in fact, used quite directly for this purpose, illustrating how close the connection is. Keep classical propositional logic in mind as partial motivation. There, each line of a truth table is, in effect, a model. And a truth table line is specified completely by saying which propositional letters are assigned T and which are assigned F. Modal models are more complex in that a. family of such truth assignments is involved, one for each member of %, and there is some relationship between these assignments (represented by 31, though we have not seen its uses yet). Now in the classical case, once truth values have

PROPOSITIONAL MODAL LOGIC 13 been specified at the propositional letter level, they can be calculated for more complicated formulas. The modal analog of this is to calculate the truth value of non-atomic formulas at each possible world. The notational mechanism we use is to extend the relation Ih beyond the propositional letter level. DEFINITION 1.6.3. [Truth in a Model] Let (£, R, Ih) be a model. The relation lh is extended to arbitrary formulas as follows. For each r e $>: i. r ih -x ^=^ r \y- x. 2. r lh (X A Y) ^=^ r lh X and T Ih Y. 3. T Ih DX ^=* for every A e £, if r# A then A Ih X. 4. T Ih OX «=> for some AgJ, T^A and A Ih X. We will give concrete examples in the next section, but first a few remarks. The first two clauses of Definition 1.6.3 say that, at each world, the propositional connectives A and -i behave in the usual truth table way. The last two clauses are what is special. The first says necessary truth is equivalent to truth in all possible worlds, but limited to those that are accessible from the one you are dealing with. The second says possible truth is equivalent to truth in some accessible possible world. Suppose we think of v as a defined connective in the usual way: (X v Y) abbreviates -*(-iX A -*Y). Then, using various of the conditions above, r ih (x v y) ^=> r ih -(-x a -y> <=> r i/ (-x a -*y) ^=> r f -x or r f -y ^=> r ih x or r ih y Alternatively we could take v as primitive, and add to the definition of truth in a model the additional condition: r ih (x v y) ^=* r ih x or r ih y Either way leads to the same thing. Thus there are two possible approaches to the various binary connectives not mentioned in Definition 1.6.3. Whether defined or primitive, we want the condition for v above, as well as the following. r ih (x d Y) ^=> r i/ x or r ih y ^=> ifrihXthenTlhy rih(X = y) ^=> TlhXifandonlyifrihy

14 CHAPTER ONE Incidentally, just as we could take various propositional connectives as either primitive or defined, the same is the case with the modal operators. Check for yourselves that if we took OX as an abbreviation for -CHX, the result would be equivalent to the characterization in Definition 1.6.3. The notation we are using, T lh X, does not mention the model, only a possible world and a formula. This is fine if it is understood which model we are working with, but if more than one model is involved, the notation can be ambiguous. In such cases we will write M, V lh X, where M = ($, Si, lh) is a model. We take this to mean: X is true at the world T of the collection $ of possible worlds of the model M. We will suppress explicit mention of M whenever possible, though, in the interests of a simpler notation. Exercises EXERCISE 1.6.1. Show that, at each possible world T of a modal model, T lh (DX = -0-X) and V lh (OX = -D-X). EXERCISE 1.6.2. Show that if a world V of a model has no worlds accessible to it, then at T every formula is necessary, but none are possible. 1.7. Examples In order to give a feeling for the behavior of modal models, we give several examples, and a few exercises. The pattern of presentation we follow is this. Models are given using diagrams, with boxes representing possible worlds. For two worlds of such a model, T and A, if r«??A, we indicate this by drawing an arrow from T to A. We say explicitly which propositional letters are true at particular worlds. If we do not mention some propositional letter, it is taken to be false. We begin with examples showing certain formulas are not true at worlds in a particular model, then move on to examples showing certain other formulas are true at worlds of models, under very broad assumptions about the models. EXAMPLE 1.7.1. Here is the first of our specific models.

PROPOSITIONAL MODAL LOGIC 15 0 Ih P n Mi- G In this model, A Ih P v Q since A Ih P. Likewise, Q\\- P v Q. Since A and Q are the only possible worlds in this model that are accessible from T, and Fvgis true at both of them, V Ih D(P v Q). On the other hand, we do not have T Ih DP, for if we did, since Q is accessible from T, we would have Q\\- P, and we do not. Similarly we do not have r Ih DQ either, and so we do not have T Ih DP v Dg. Consequently D(P v Q) D (DP v DQ) is not true at I\ You might try showing (OP A 02) D 0(P A Q) is also not true at I\ EXAMPLE 1.7.2. This time, T f UP D DDP. e A It" P a r Ih DP since A Ih P, and A is the only world accessible from T. If we had T Ih DDP, it would follow that A Ih DP, from which it would follow that Q Ih P, which is not the case. Consequently r If DP D DDF. EXAMPLE 1.7.3. Show for yourself that, in the following model, V If OP D DO P. e A IH P

16 CHAPTER ONE EXAMPLE 1.7.4. Again, show for yourself that in the following model, T If 0 □ □ I I EXAMPLE 1.7.5. This is a counter-example to lots of interesting formulas. A lh P Since P is true at A, and A is the only world accessible from A, DP is true at A. But then again, since DP is true at A, it follows that DDP is also true there, and likewise DDDP, and so on. Now, since A is the only world accessible from T, and P is true at A, DP is true at I\ Likewise, since DP is true at A, DDP is true at T, as is DDDP, and so on. On the other hand, P itself is not true at I\ Thus at T, all of the following formulas are false: DP 2> P, DDP D P, DDDP D P, and so on. Next we turn to examples showing certain formulas must be true at worlds, under very general circumstances. EXAMPLE 1.7.6. In Example 1.7.1 we showed D(P vg)D (DP v Dg) could be false at a world under the right circumstances, so we cannot assume □ distributes over v. Now we show □ does distribute over A, that is, D(P A g) d (DP A Dg) is true at every possible world of every model. This time we draw no pictures, since it is not a particular model we are dealing with, but the class of all models. Suppose ($, fR, lh) is a model, and Teg,. Also suppose T lh D(P A g); we show it follows that T lh DP A Dg.

PROPOSITIONAL MODAL LOGIC 17 Let A be an arbitrary member of % that is accessible from T, that is, YSi A. Since Y Ih D(P A Q), it follows that A Ih P A Q, and hence A Ih P and also A Ih Q. Since A was arbitrary, at every possible world accessible from T, both P and Q are true, hence at Y both DP and OQ are true. But then, nt-DPAD<2. In a similar way, it can be shown that the converse, (DP a D<2) d D(P a (2) is true at every world, as is D(P D Q) D (DP d Dg). We leave these to you. Sometimes binary relations satisfy special conditions, and many of these have standard names. Here are a few of them. A relation Si on $ is reflexive if YSiY holds for every Teg,, that is, if every world is accessible from itself. Also SI is transitive if YSiA and ASiQ always imply YSiQ\ Si is symmetric if Y Si A always implies A^T. EXAMPLE 1.7.7. Suppose {%, Si, Ih) is a model in which Si is transitive. Then Y Ih DP D DDP, for each r e #. We show this as follows. Suppose T Ih DP; we must show T Ih DDP. And to show Y Ih DDP, let A be any member of % such that YSi A and show A Ih DP. And to show this, let Q be any member of % such that ASiQ and show Q Ih P. But, YSi A and A<??£2, and Si is transitive, so YSiQ. Also, we began by supposing that T Ih DP, so it follows that Q Ih P, which is what we needed. EXAMPLE 1.7.8. Suppose (#, <«, Ih) is a model. 1. If <?? is reflexive, DP D P is true at every member of $. 2. If Si is symmetric, P D D<)P is true at every member of $. 3. If Si is both symmetric and transitive, OP D DOP is true at every member of $. We leave the verification of these items to you as exercises. Exercises EXERCISE 1.7.1. Continue Example 1.7.1 and show that (OP A 02) ^ 0(P A Q) is not true at Y. EXERCISE 1.7.2. Complete Example 1.7.3 by showing that Y f OP D □OP. EXERCISE 1.7.3. Complete Example 1.7.4 by showing that Y f (OOP A ODfi)DOn(PAQ).

18 CHAPTER ONE EXERCISE 1.7.4. Show the following are true at every possible world of every model. i. (DPAn<2)DD(PA<2) 2. D(PD Q)D(DPD\JQ) EXERCISE 1.7.5. Show the three parts of Example 1.7.8. 1.8. Some Important Logics During the course of the twentieth century, a large number of modal logics have been created and investigated. Partly this was because of different intended applications, and partly it was because our intuitions about necessary truth are not fully developed. While everyone (probably) agrees that, whatever "necessity" might mean, necessary truths have necessary consequences, opinions differ about whether necessary truths are so by necessity, or contingently. And probably few indeed have thought much about whether a proposition whose necessity is possibly necessary is necessarily true, or even possible. Once iterated modalities arise, intuition and experience begin to be inadequate. In part, different formal modal logics have arisen in an attempt to capture differences in the behavior of iterated modalities. There is no point here in trying to choose between them. We simply present a few of the more famous systems that have arisen, and leave it at that. The main purpose of this book is the treatment of first-order modal issues and for this, variations between modal logics at the propositional level have minor significance. Originally, different modal logics were characterized by giving different sets of axioms for them. One of the early successes of possible world semantics was the characterization of most standard modal logics by placing simple mathematical conditions on frames. We want to emphasize this: conditions are placed on frames. Although models are what we deal with most often, frames play a central role. We will see the importance of frames throughout this book. In this section we discuss a handful of the best-known modal logics: K, D, T, K4, B, S4, and S5, and we use possible world semantics for their definition. Think of these logics as just a sampling of what can be obtained using this approach. DEFINITION 1.8.1. [L-Valid] We say the model (#, <ft, lh> is based on the frame ($, Si). A formula X is valid in a model ($, 31, lh) if it is true at every world of $. A formula X is valid in a frame if it is valid in every model based on that frame. Finally, if L is a collection of frames, X is L-valid if X is valid in every frame in L.

PROPOSITIONAL MODAL LOGIC 19 Different modal logics are characterized semantically as the L-valid formulas, for particular classes L of frames. To give a simple example, the logic called T is characterized by the class of frames having the property that each world is accessible from itself. To make things easier to state, we recall some standard terminology that was briefly introduced earlier. DEFINITION 1.8.2. Let (#, <R) be a frame. We say it is: 1. reflexive if TRY, for every Teg,; 2. symmetric if TSi A implies A^r, for all r, A e $; 3. transitive if T^A and A^fi together imply V31Q, for all T, A, Q e #; 4. serial if, for each Teg, there is some A e $> such that YSl A. The logic T, mentioned above, is characterized by the class of reflexive frames. From now on we, ambiguously, use T to denote both the class of reflexive frames, and the logic determined by that class. This should cause no real difficulties—context will always determine which is meant when it matters. The chart in Figure 3 supplies standard names for several more frame collections, and their corresponding logics. We use these names in what follows. Logic Frame Conditions K no conditions D serial T reflexive B reflexive, symmetric K4 transitive 54 reflexive, transitive 55 reflexive, symmetric, transitive Figure 3. Some Standard Modal Logics We saw in the previous section, in Example 1.7.6, that D(PaQ) d (DPa D<2) is true at every world of every model. In other words, it is K-valid. In that same Example, (DP A Dg) D D(P A Q) and D(P D Q) D (DP D DQ) were also said to be K-valid, and verification was left as an exercise. Likewise in Example 1.7.7 it was shown that DP D DDP is valid in any model whose frame is transitive. It follows that this formula is K4-valid, and also S4- and S5-valid as well, since these include transitivity among their frame conditions. Example 1.7.8 shows that DP D P is T-valid, that P D OOP is B-valid, and that 0^ D D()P is S5-valid. If a formula X is K4-valid it is true in all transitive frames, and so in all transitive and reflexive frames, and hence it is also S4-valid. Thus K4 is

20 CHAPTER ONE a sublogic of S4. In a similar way, B is a sublogic of S5. Trivially, K is a sublogic of all the others. Finally, every reflexive relation is automatically serial (why?) so D is a sublogic of T. All this is summarized in the following diagram. Every frame in T is also a frame in D, but the converse is not true. Still it is conceivable that, as logics, D and T are the same. That is, it is conceivable that the same formulas are valid in the two classes of frames. (In fact, there are well-known examples of two distinct classes of frames that determine the same logic.) However, this is not the case here. Example 1.7.8 shows that DP d P is T-valid. But the model in Example 1.7.5 is based on a D-frame, and OP D P is not valid in it. Thus as logics D and T are different. As a matter of fact, the inclusions among logics that are shown in the diagram above are the only ones that hold among these logics. Exercises EXERCISE 1.8.1. Show DP D OP is valid in all serial models. EXERCISE 1.8.2. Prove that a frame ($, 31) is transitive if and only if every formula of the form DP D DDP is valid in it. EXERCISE 1.8.3. There is a modal logic, sometimes called S4.3 (due to Dummett and Lemmon) which is characterized semantically by the class of frames ($, Si) for which Si is reflexive, transitive, and linear, that is, for all r, A e #, either TSiA or ASir. 1. Show that D(DP D DQ) v D(D<2 D DP) is valid in all S4.3 frames.

PROPOSITIONAL MODAL LOGIC 21 2. Show that P D H()P can be falsified in some S4.3 frame. 3. Show that 0D(P D Q) D (OOP D <>□(?) is valid in all S4.3 frames. EXERCISE 1.8.4. This exercise has many parts, but each one is not difficult. Show the inclusions between logics that are given in the diagram above are the only ones that hold. 1.9. Logical Consequence In classical logic the notion of follows from is fundamental. Loosely speaking, one says a formula X follows from a set of formulas S provided X must be true whenever the members of S are true. More formally, one says X is a logical consequence of S (in classical propositional logic) provided that for every assignment of truth values to propositional letters, if every member of S evaluates to T, then X also evaluates to T. This is often symbolized by S |= X. Many important facts about classical propositional logic are quite easily stated using the notion of logical consequence. For instance the compactness property says, if S |= X then for some finite subset So c S we have So |= X. Tarski instituted the general study of consequence relations, and their fundamental role has been accepted ever since. Not surprisingly, things are more complex for modal logics. We want to keep the intuition that X is a logical consequence of S if X is true whenever the members of S are true. But a modal model can contain many possible worlds. Do we want to take X to be a consequence of S if X is true at each world at which the members of S are true, or do we want to take it as meaning X is valid in every model in which the members of S are valid? No such dichotomy is available classically, but the choice presents itself modally, and the two notions are most decidedly not equivalent. This has caused a certain amount of confusion from time to time. As it happens, both versions are important, so we briefly sketch a treatment of them using notation from (Fitting, 1983). We omit proofs of basic facts here; it is enough if one understands the kind of complications modal notions bring. Proofs can be found in (Fitting, 1983) and in (Fitting, 1993). DEFINITION 1.9.1. [Consequence] Let L be one of the frame collections given in Figure 3 of Section 1.8. Also let S and U be sets of formulas, and let X be a single formula. We say X is a consequence in L of S as global and U as local assumptions, and write S (=l U -> X, provided: for every frame ($, 31) in the collection L, for every model ($, Si, lh) based on this frame in which all members of S are valid, and for every world T e % at which all members of U are true, we have r lh X.

22 CHAPTER ONE Thus S (=l U -> X means X is true at those worlds of L models where the members of U are true, provided the members of S are true throughout the model, i.e., at every world. Admittedly, this is a more complex notion than classical consequence. Local and global assumptions play quite different roles, as the following examples make clear. EXAMPLE 1.9.2. We take L to be K, the collection of all frames, S to be empty, so there are no global assumptions, U to contain only UP D P, and X to be DDP d DP. The following model shows 0 |=K {DP D P} -> DDP D DP does not hold. f P In this model, r If DP since T^A and A f P. Consequently T Ih (DP D P), so the only member of {DP d P} is true at T. On the other hand, A lh DP since there are no worlds alternate to A at which P fails. Since A is the only world accessible from T, it follows that T lh DDP. We have already seen that T f DP, so T f (DDP d DP). We thus have a counterexample to 0 \=K {OP D P] -> DDP D DP fails. Every global assumption is valid in the model since there are none. But at T all local assumptions are true and DDP D DP is not. Comparison of this example with the following will make clear the difference in behavior between local and global assumptions. EXAMPLE 1.9.3. This time we show that {DP D P} \=K 0 -> DDP D DP does hold. Let (#, 31, lh) be a K model in which DP D P is valid. Let T be an arbitrary member of % (at which all the local assumptions hold, since there are none). We show T lh DDP D DP. Suppose T lh DDP. Let A be an arbitrary member of % such that T^A. Then A lh DP. Since DP D P is valid in the model, A lh (DP d P), and so also A lh P. Since A was arbitrary, Y lh DP. Many of the general properties of classical consequence carry over to modal consequence. For instance, classical consequence obeys a monoton- icity condition: if X is a consequence of a set, it is also a consequence of any extension of that set. A similar result holds modally.

PROPOSITIONAL MODAL LOGIC 23 PROPOSITION 1.9.4. Suppose S |=L U -> X, and 5 c S' and £/ c [/'. Then S' |=L £/' -> X. Classical consequence has the compactness property, as we noted at the beginning of this section. This too carries over to a modal setting. PROPOSITION 1.9.5. Suppose S |=L U -► X. Then there are finite sets S0£ SandUo^U such that S0 |=L C/0 -► X. One of the most used features of classical consequence is that it obeys the deduction theorem. Classically, this says that S U {Y} |= X if and only if S |= (7 D X). It is often used to replace the proof of an implication, Y D X, by a derivation of a simpler formula, X, from a premise, 7. But modal consequence differs significantly here. More precisely, there are two versions of the deduction theorem, depending on whether Y is taken as a local or as a global assumption. PROPOSITION 1.9.6. [Local Deduction] S |=L U U {Y} -> X if and only ifS|=L£/-> (7 DX). PROPOSITION 1.9.7. [Global Deduction] S U {Y} |=L [/ -► X if and only if 5 |=L c/ u {y, ny, nny, nnny,...} -► x. The Local Deduction Proposition is essentially the same as the classical version. In a sense, it is the peculiar form of the Global Deduction Proposition that is at the heart of the complexities of modal consequence. In subsequent chapters we will need the notion of modal consequence from time to time, but it will almost always be with an empty set of local assumptions. Different books on modal logic often make special assumptions about whether local or global assumptions are fundamental, and so the very definition of modal deduction differs significantly from book to book. DEFINITION 1.9.8. We abbreviate S |=L 0 -► X by S |=L X. Exercises EXERCISE 1.9.1. Show that 0 |=K {DP D P} -► DDP D P does not hold, but {DP d P}\=K0-> DDP D P does. EXERCISE 1.9.2. Prove Proposition 1.9.4.

24 CHAPTER ONE EXERCISE 1.9.3. Let DT denote □□ ... DY9 where we have written a string of n occurrences of □. Use the various facts given above concerning modal consequence and show the following version of the deduction theorem: S U {Y} (=L U -> X if and only if, for some n, S |=L U -> (D°y aD!Fa ...aD7) Dl l.io. Temporal Logic The temporal interpretations of □ and 0 are as old as the study of modality itself. In the present century, it was the temporal semantics developed over a number of years by A. N. Prior that provided the clearest understanding of modal logic, until general possible world semantics was created. We have stronger intuitions about temporal worlds than we do about the more abstract and austere alethically possible worlds, and frequently we will find ourselves using the temporal interpretation to aid in the understanding of modal concepts. For Frege, a complete thought, a Gedanke, is an eternal, nonlinguistic object whose truth value never changes. Quine has a corresponding notion of an eternal sentence. The sentence (1.4) John is happy is not an eternal sentence; it does not, by itself, express a complete thought. For, unless John is very unusual, there are periods in history in which it is true and periods in history in which it is false: it is not, by itself, timelessly true or false. If we were to add a time determination to the sentence, we would stabilize its truth value. Let us, then, qualify when John is happy. The sentence frame is effectively filled with a time index t, (1.5) John is happy at time f, where t occupies a position that can be bound by a quantifier. We suppose there to be a range of times at some of which, perhaps, John is happy, and at others, not. Suppose that John bought the latest model computer in November of 1994. Then, it is reasonable to suppose that the sentence, (1.6) John is happy in November 1994 is true. Suppose, as always happens, that a more powerful computer is introduced some months later and the one he bought has dropped significantly in price. Then, it is reasonable to suppose that the sentence, (1.7) John is happy in February 1995

PROPOSITIONAL MODAL LOGIC 25 is false. We can existentially generalize on the true (1.6) to get the true (30 John is happy at time t. Given the falsity of (1.7), we have the falsity also of its universal generalization (Vf) John is happy at time t. Treating (1.4) as (1.5), in effect, is to regard that John is happy not as a proposition, but as a property of times. On this reading, (1.5) is an open sentence. When t is inside the scope of a quantifier, it is bound by the quantifier; when outside the scope of a quantifier, it acts as an indexical now denoting the designated (actual) time. This gives us our first example of a modal logic with a temporal interpretation. EXAMPLE 1.10.1. This simplest temporal interpretation of DP and 0^, which parallels our alethic treatment of necessarily and possibly, takes □ John is happy 0 John is happy to correspond, respectively, to (it) John is happy at time t (30 John is happy at time t As with the alethic interpretation, P D §P turns out true and §P D P turns out false; similarly, DP D P turns out true and P D DP turns out false. Let us complicate our temporal interpretation by introducing the following future and past tense operators: FP : It will sometime be the case that P PP : It was sometime the case that P where the verb in P is now untensed. It is common to define two more tense operators, GP (= - F-P) and HP (= - P-P): GP : It will always be the case that P HP : It has always been the case that P We can, using these tense operators, capture a considerable number of natural language tenses. Let P be "John wins the election." Then we have the following ways of interpreting natural language tenses:

26 CHAPTER ONE (a) P John wins the election (b) FP John will win the election (c) PP John won the election (d) PPP John had won the election (e) FPP John will have won the election (/) PFP John would win the election We will explain the iterated operators in (d)-(f) shortly. We can develop two different modal logics from these operators by taking DP and OP, respectively, to be GP and FP, or equally well, to be HP and PP. (The reader can verify that the Modal Square of Opposition is satisfied either way.) These modal operators can be nested, and the complications thus introduced are nontrivial. We have, to this point, made no provisions for iterations of temporal operators. This is clear from our quantificational representation. If OP says "There will be a time t such that John wins the election at f," then putting another temporal operator in front will appear to have no effect since there is no free variable left to bind. Yet, from the intuitive reading we give to the modal operators above, there are obvious distinctions: (e) is distinct from (/), for example, and (c) is distinct from (d). How are we to handle these cases? Let the present time be t. Then corresponding to the modal claims F John wins the election, P John wins the election, G John wins the election, H John wins the election, we have, respectively, (3tf)(tf > t A John wins the election aU;), (3t')(tf < t A John wins the election atf'), (Vt')(t' > t A John wins the election atf'), (Vf')(f' < t A John wins the election atf')- Then (e) and (/) become, respectively, (3t")(t" > t A (3f')0' < t" A John wins the election au')) and (3f")(f" < t A (Bt')(t' > t" A John wins the election au'))

PROPOSITIONAL MODAL LOGIC 27 (We leave (d) as an exercise for the reader.) So, (e) says that there will be a time in the future before which John wins the election: he will have won the election; and (/) says that there is a time in the past after which John wins the election: he would win the election. Thus we have our second, more elaborate, temporal interpretation of the modal operators. EXAMPLE 1.10.2. Taking □ and 0 to be G and F, respectively, gives us a different logic from the one in Example 1.10.1 even though the Modal Square of Opposition is still satisfied. For example, the thesis DP D P, fails. Just because it will always be true that P, it does not follow that P is true now. On the other hand, OP D OP holds: if it will always be true that P, then there will be at least one (future) occasion at which P is true (assuming that time does not end). Other differences emerge when we consider iterations of the modal operators. Consider: P D DO P. This fails because from the fact that P is true, it does not follow that it will always be the case that there will be some further time at which it is true. On the other hand, DP D DDP, holds because the temporal order is clearly transitive: if P holds at every future time, then at every future time P will hold at every (yet) future time. EXAMPLE 1.10.3. We can get yet another modal logic by defining □ and 0 as follows: OP = P vFP DP = P aGP Thus DP means P is and will remain the case; OP means P is now or will at sometime be the case. (Prior (1957) claims that Possibly and Necessarily were used in this sense by the Megarian logician Diodorus.) In this system, OP D DOP will fail. Suppose it either is or will be the case that P. Must this now and forever in the future be so? No. We might go too far into the future, to the point when P is a completed process. For instance, let P be "Scientists discover a cure for the common cold." We hope that OP is the case—someday a cure will be discovered. But once discovered, it cannot be discovered again, so DOP is not the case. There is an ordering relation that is imposed by time in temporal logic: later than. The temporal ordering is transitive, but it is neither reflexive nor symmetric. So, if we take DP to be GP, a proposition is necessarily true if it holds at all future worlds: a world, or state, is accessible if it is later in the temporal ordering. If, on the other hand, we take DP to be P A GP, then a proposition is necessarily true if it holds now and forever later. DPdP fails for the former reading, but it holds for the latter one.

28 CHAPTER ONE Exercises EXERCISE 1.10.1. What is the corresponding quantifier translation of item (d) PPP? Use our treatment of items (e) and (/) as models. l.n. Epistemic Logic We can also interpret the usual modal symbols to create a logic of knowledge. Hintikka (1962) introduces the following readings for □ and 0 respectively: XaP: a knows that P tPaP:ll is possible, for all that a knows, that P This is a multi-modal logic: each subscript identifies an individual. There is a similar vocabulary for belief: £aP\ a believes that P CaP:It is compatible with everything a believes that P In each case, we have the usual interdefinability of the modal operators: XaP = ^<Pa^P Bap = ^ea^p The theorems of (Hintikka, 1962) include all tautologies plus (1.8) Xa(PDQ)D(XaPDXaQ) (1.9) XaP D P (1.10) XaP D XaXaP and the two rules of inference, Modus Ponens (Y follows from X and X D Y) and Necessitation (XaX follows from X). Formula (1.8) will be our K axiom in Chapter 3, corresponding to frame condition K in Figure 3. Likewise (1.9) will be our T axiom; and (1.10) will be our 4 axiom. With T and 4 on top of K, we have what is called an S4 system. Xa P is perhaps better read as It follows from what a knows that P, or perhaps as a is entitled to know that P. For, in this system, one knows all the logical consequences of anything one knows: if P D Q is logically true, and if Ka P, then XaQ.In this logic, then, the knower is treated as logically omniscient. This feature of the system is made even more puzzling because of (1.10), which is called the Principle of Positive Introspection: one cannot know something and yet fail to know that one knows it. Suppose, for example, that Goldbach's Conjecture is provable (although we have no proof as yet).

PROPOSITIONAL MODAL LOGIC 29 Then, anyone who knows that the Peano Axioms are true—most likely, any reader of this book—knows, by logical omniscience, that Goldbach's Conjecture is true, and knows, by (1.10), that he knows that Goldbach's Conjecture is true. Yet it is unlikely that any reader of this book is in possession of a proof of Goldbach's conjecture, so it is unlikely that any reader of this book knows that Goldbach's Conjecture is true, and even more unlikely that any reader of this book knows that he knows that Goldbach's Conjecture is true. Formula (1.10) is justified, despite its title, not because knowing that P carries with it a certain mental feeling which one knows one has by introspection. Hintikka is working with the view that knowledge is justified, true belief.2 So (1.10) is justified because, if one knows that P, one must be justified in believing that P, and one cannot be justified without being aware of being justified. It is not just that if one knows that P, there are reasons justifying P\ rather, if one knows that P, these justifying reasons must be your reasons, and so you cannot help but be aware of them. Logical Omniscience simply tells us that if Q follows from P on logical grounds, every knower is aware of these grounds. This is a very strong condition on knowledge, and it is why we prefer reading Xa P as a is entitled to know that P, rather than as a knows that P. Of course, there are some constraints on knowledge. It is interesting, in this regard, to note that by contrast with (1.10), the Principle of Negative Introspection, (1.11) ^XaP D Xa^XaP is not a theorem of this system. Again, this has nothing to do with introspection. The reasons are a bit more mundane: you might not know that P and yet believe that you do know it. (1.11), however, requires that if you don't know that P, then you know, and so believe, you don't know it. The following also fails to be a theorem: (1.12) PD Xa<PaP And this seems appropriate. For, a statement P might be true and yet one need not know that it is compatible with everything one believes. The following all do hold in Hintikka's system: (1.13) XaXhP D XaP (1.14) XaPDPaP (1.15) XaP = XaXaP 2 "Believe it, for you know it." Merry Wives of Windsor, William Shakespeare.

30 CHAPTER ONE (1.13) expresses the transmissibility of knowledge? (1.14) essentially tells us that every world has an alternative, which we know from the reflexivity expressed in axiom (1.9). It can also be shown that JCaP D XaQ follows from P D Q. This is a form of logical omniscience: one knows all the logical consequences of anything one knows. It is a controversial feature of the system. In some sense, we are talking about an idealized version of knowledge, and not knowledge as people generally use the term. A logic of belief is more problematic than a logic of knowledge because we are not entirely consistent in our belief sets. In any event, Hintikka (1962) suggests that (1.16) £aP D£a£aP is true. In defense of (1.16), Hintikka argues that the two formulas, £aP and 3$a(P ^ -^3$aP) are inconsistent. On the other hand, he suggests that none of the following are true: £a£aPD£aP BaBbP D£aP £$aP ^ J^a^BaP The semantics of Hintikka (1962) is in terms of what he calls model sets, and his proof procedure is a precursor of what has since become known as tableau rules. On the usual semantics for classical logic, a model consists of an assignment of a truth value to every propositional symbol and an interpretation of the logical connectives as boolean functions on these truth values, so that each complex sentence of the language is assured a unique truth value. Hintikka, by contrast, takes a model to be a model set, that is, a collection of sentences (deemed to be true) which might be thought of as a partial description of the world. A model set /x is governed by the following rules: (C.-O If P e [i then not -./> e /x (C.a) If P aQ e /J, then PG/iandQG/i (C.v) IfPvQe/ji then P g /x or Q e fi (or both) (C.-.-.) If -.-./> e /x then P e /x (C.-v\) If-"(P A Q) e fi then -Pe/ior-Qe/i (or both) (C.-v) If -•(/> v Q) g ix then -./> e fi and -.0 G /x 3 We do not have the corresponding principle for belief, i.e. Ba^bP D &aP>

PROPOSITIONAL MODAL LOGIC 31 These are just the classical conditions. For modal logic we need the notion of a model system—a collection of model sets plus an alternativeness relation (actually, one for each knower a). The following additional rules govern the modal operators: (C.P*) IfJ^/*€//, and if /x belongs to a model system £2, then there is in Q at least one alternative /x* to /jl (with respect to a) such that P e /x* (C.KK*) If Ka Q G fi and if /x* is any alternative to /jl (with respect to a) in model system £2, then XaQ £ /jl* (C.K) If JCaP e I* then P e /x (C-- K) lf~-XaP e /x, then Pa-^P e fi (C- P) \f--PaP e /x, then JCa~-P e n The proof procedure is by reductio: if the assumption that -»X belongs to a model set leads to an inconsistency, then X must belong to every model set, i.e., it must be true in all models, which is to say that it is valid. EXAMPLE 1.11.1. Show: (JCaP A XaQ) D JCa(P A Q) 1 2 3 4 5 6 7 8 9 10 11 JCaP A XaQ -JCa{P A Q) Pa^P A Q) -(/» AQ)€, JCaP 6 /X JCaQSfl XaP € M* JC.ee m* Pen* Q 6/x* -P 6/X* X 12 €fl en € /J, a* X Assumption Assumption (C.-K),2 (C.P*), 3 (C.A), 1 (C.A), 1 (C.KK*), 5 (C.KK*), 6 (C.K), 7 (C.K), 8 In line 4, /x* is an alternative model set to /x. Also lines 11 and 12 are the two alternatives deriving from line 4. One alternative is impossible, because of 9 and 11; the other is impossible, because of 10 and 12. Epistemic logics continue to be of interest to philosophers. Nozick (1981) has raised some interesting problems with (1.8), JCa(P D Q) D (JCaP D Xa <2), in regard to skepticism. Let E be some experiential statement, e.g., "I see a human hand before me." Let 5 be the crucial skeptical statement that I

32 CHAPTER ONE am unable to disprove, e.g., "I am dreaming" (or, alternatively, "I am a brain in a vat"). Now, it is quite clear that if E is true, i.e., if I do see a human hand before me (and not just something that appears to be a human hand), then S must be false, i.e., it cannot be the case that I am now dreaming. So, we have (1.17) ED^S and also, as just pointed out, we know this to be the case. (1.18) JCa(ED^S) Now, the skeptical position is just that I am unable to rule out the possibility that I am dreaming or that I am a brain in a vat. That is, (1.19) ^Xa^S An instance of (1.8) is (1.20) Xa(E D -5) D (XaE D Xa^S) From this, contraposing the consequent, we have the following. (1.21) Xa(E D-S) D (^Xa-S D-XaE) From (1.18) and (1.19), applying Modus Ponens twice, we derive (1.22) ^XaE. In effect, then, I have no experiential knowledge. Nozick (1981) suggests that we should reject (1.8). On the other hand, (1.22) could be correct. This interplay of philosophy and modal logic is a good example of how the sharpening provided by logic formalization enables us to grasp a philosophical puzzle. Exercises EXERCISE 1.11.1. Proveeachof (1.13), (1.14) and (1.15) using Hintikka's model sets. 1.12. Historical Highlights Now, armed with some formal machinery, it is time for a (highly selective) glance back in history at some well-known problems involving modal reasoning.

PROPOSITIONAL MODAL LOGIC 33 Aristotle's Development of the Square Aristotle had to fight hard to work out The Modal Square of Opposition we presented earlier in Figure 1; confusions constantly threatened to obliterate the gains. Aristotle opens De Interpretatione 13 with a somewhat different square of opposition, and which we reproduce as Figure 4. In this figure, the It is necessary that P It is necessary that not P It is not possible that not P It is not possible that P \s i/\ It is not necessary that P It is not necessary that not P It is possible that P It is possible that not P Figure 4. The Modal Square of Opposition in De. Int. 13 apodeictic forms have been transposed on the bottom row: It is possible that P is alternately expressed as It is not necessary that P, and It is possible that not P is alternately expressed as It is not necessary that not P. Aristotle had not clearly separated two readings of "possible" in De Interpretatione 13: on the one hand, he takes it to mean not impossible; on the other hand, he takes it to mean contingent. As Ackrill (1963) points out, the top half of the table appears to be driven by the first notion of "possible" while the bottom half appears to be driven by the second notion, i.e., of "contingent."4 The intention in a Square of Opposition is that the forms in the left column are to be subalternatives, with the top implying the bottom. But while It is necessary that P implies It is possible that P, it cannot imply the supposedly equivalent formulation It is not necessary that P. Aristotle saw the problem and sorted things out, eventually winning his way through to the square we gave in Figure 1. He broke apart the two forms in the lower left hand corner. But his argument reveals a typical modal confusion that spills over to infect the relatively good grasp he had of nonmodal distinctions. At De Interpretatione 22^ 10, he says: For the necessary to be is possible to be. (Otherwise the negation will follow, since it is necessary either to affirm or to deny it; and then, if it is not possible to be, it is impossible to be; so the necessary to be is impossible to be—which is absurd.) (Ackrill, 1963), p. 63 Not quite, however. It is contingent that P is equivalent to the conjunction It is possible that P but not necessary that P, not to It is not necessary that P alone.

34 CHAPTER ONE Aristotle's conclusion, which we might express so, (1.23) DP D OP is readily acceptable in any of the modal logics discussed that are at least as powerful as D. But the reasoning Aristotle put forward to justify (1.23) is faulty. To be sure, as he says, "it is necessary either to affirm or to deny it," that is Either (1.23) or not-( 1.23). But not-(L23) ought to be -(DP D OP) Aristotle, however, concludes: DP D-OP. Ackrill (1963) regards this as a misapplication of the Law of Excluded Middle; but it is perhaps better viewed as a scope error. Aristotle confused the negation of the conditional with the negation of the consequent. Exercises EXERCISE 1.12.1. Can a Square of Opposition be constructed when 0 is interpreted to mean "It is contingent that," where contingent means true but not necessary? EXERCISE 1.12.2. Informally, we take DP D OP to be valid for the following reason: If P is necessary, then P is true; and if P is true, then P is certainly possible. D, however, is usually thought of as a Deontic logic (which is why it is called D); it is a logic of obligations and permissions. DP D P is not valid in D. One can readily understand why: just because an action is obligatory, it does not follow that it is performed. The exercise comes in three parts: 1. Verify that DP d P is not valid in D. 2. Verify that DP d OP is valid in D. 3. Verify that DP D OP is not valid in K.

PROPOSITIONAL MODAL LOGIC 35 Aristotle's Future Sea Battle The ancient Greek philosophers were much concerned with the relation between necessity and determinism. Events do not appear to occur haphazardly, but regularly, with earlier events affecting the course of later events. If an event B has its roots in an earlier event A, then it would seem that, given A, B could not help but occur; and if the earlier event A could not be altered, then it would be necessary, so we have not merely the relative necessity of B given A, but the absolute necessity of B. Everything, then, would seem to be occurring of necessity. Aristotle meant by necessity "the unalterability of whatever has already happened." (Ackrill, 1963, p. 113) Now, unalterability appears to identify a fundamental asymmetry between past and future: the past is unalterable in a way the future is not. In one of the most famous arguments from antiquity, found in De Interpretation 9, Aristotle suppressed issues of causation and faced the problem of determinism in terms of truth, truth at a given time and necessity. One cannot undo what has already been done. But if it is true now that there will be a sea battle tomorrow, the future also appears determined and unalterable, and the asymmetry collapses: Again, if it is white now it was true to say earlier that it would be white; so that it was always true to say of anything that has happened that it would be so. But if it was always true to say that it was so, or would be so, it could not not be so, or not be going to be so. But if something cannot not happen it is impossible for it not to happen; and if it is impossible for something not to happen it is necessary for it to happen. Everything that will be, therefore, happens necessarily. So nothing will come about as chance has it or by chance; for if by chance, not of necessity. (18^9 ff) in (Ackrill, 1963), pp 50-51. This is the famous problem of future contingents. Aristotle clearly rejects the fatalistic or deterministic conclusion. "Absurdities," he calls them: if "everything is and happens of necessity ... there would be no need to deliberate ... ." (18^26ff) And he offers the following solution beginning at 19° 23: What is, necessarily is, when it is; and what is not, necessarily is not, when it is not. But not everything that is, necessarily is; and not everything that is not, necessarily is not. For to say that everything that is, is of necessity, when it is, is not the same as saying unconditionally that it is of necessity. Similarly with what is not. And the same account holds for contradictories: everything necessarily is or is not, and will be or will not be; but one cannot divide and say that one or the other is necessary. I mean, for example: it is necessary for there to be or not to be a sea-battle tomorrow; but it is not necessary for a sea-battle to take place tomorrow, nor for one not to take place—though it is necessary for one to take place or not to take place. So, since statements are true according to how the actual things are, it is clear that wherever

36 CHAPTER ONE these are such as to allow of contraries as chance has it, the same necessarily holds for the contradictories also. This happens with things that are not always so or are not always not so. With these it is necessary for one or the other of the contradictories to be true or false—not however, this one or that one, but as chance has it; or for one to be true rather than the other, yet not already true or false. (Ackrill, 1963), pp 52-53. Aristotle denies that events in the future are already determined. His response to the argument is to deny that statements about the future are in some sense already true or false. But there is considerable disagreement among commentators about what he meant by this. The text has subtle complexities that provide an interesting and instructive modal story. Aristotle's claim, "Everything necessarily is or is not," introduces a possible source of confusion. For simplicity, we will take this to be a variant of the Law of Excluded Middle: P v -»P. Depending upon the scope we assign to "necessarily," we get two different claims. On the one hand, it might mean that the claim that P is true or ->P is true is necessarily true: (1.24) D(Pv-P) On the other hand, it might mean that P is necessarily true or -»P is necessarily true: (1.25) DPvD-P Clearly, (1.24) is correct and (1.25) is problematic. If we maintain (1.25), then, together with Excluded Middle, the modality collapses, i.e., P = DP: Whatever is true is necessarily true; whatever is false is necessarily false. To be more precise, the modality collapses in T. It does not collapse in K. (We leave this as an exercise.) It collapses in T by the following reasoning. (1.25) says DP v D-»P. By classical logic, Xv7is equivalent to —Y D X. So, (1.25) gives us -CHP d DP. But in T, P d -■□-•P, so we have P D DP. And since DP D P is valid in T, we have P = DP. It is not clear which of (1.24) or (1.25) Aristotle holds. In the passage quoted above, Aristotle appears to be clearly endorsing (1.24) but it is not as clear that he is rejecting (1.25). For, as Ackrill (1963) notes, the claim that "one cannot divide" might be understood to rule out either of the following inferences: D(Pv^P) D(Pv^P) So, DP So, D--P This is not yet (1.25). Nonetheless, passages like this sustain one interpretation of the chapter, on which the deterministic conclusion is presumed to follow because of scope confusion. This interpretation, which Ackrill (1963) calls "the preferred interpretation," sees Aristotle as arguing that the clearly

PROPOSITIONAL MODAL LOGIC 37 and unproblematically true (1.24) is confused with the dubious (1.25), leading the unsuspecting modal novice to believe that since he is committed to (1.24), he is thereby committed to the fatalistic position. This interpretation, however, does not place any special premium on statements about the future, and this appears to be the point Aristotle stresses in his solution. On a second interpretation, as Ackrill (1963) puts it, "Aristotle holds that a statement with a truth-value automatically has a necessity-value (if true, necessary; if false, impossible), but he claims that a statement may lack a truth-value and acquire one later." (p. 140) There are two ways of understanding Aristotle's solution on this second interpretation. On the one hand, it could be that Aristotle accepts the following argument. (a) Pv-P (b) P D DP (c) --P D D--P SO DPvD-P But what he objects to is substituting FP (i.e., It will be the case that P—see the discussion in Section 1.5) for P in step (b). Unfortunately this interpretation is clouded by Aristotle's remarks in the quotation above in which he appears to sanction the substitution of FP for P in D(P V--P). An alternative view is that the argument requires the intermediate steps of ascriptions of truth to statements. Let True P mean It is true that P. Then, on this view, the argument goes (a) Pv^P (b) P d True P (c) -.P D True -.P (d) True P D DP (e) True-P D D-P SO DPvD-P Kneale and Kneale (1962) favor this latter reading, and they see Aristotle as rejecting steps (b) and (c): they distinguish the Law of Excluded Middle, i.e., P v -»P, from the Principle of Bivalence, i. e., True P v True -»P, and they assert that Aristotle rejected the latter but not the former. Statements about future contingents lack truth values. More precisely, for Kneale and Kneale (1962), Aristotle holds that although It is true that there either will be or won't be a sea battle tomorrow, one cannot infer that either it is true that there will be a sea battle tomorrow or it is true that there won't be a sea battle tomorrow.

38 CHAPTER ONE A related view was held by some of the ancients. They took Aristotle's true to be determinately or definitely true. It is now definitely or determinately true that there either will be a sea battle tomorrow or not. But it is not now definitely true or determinately true that there will be a sea battle tomorrow nor is it now definitely true or determinately true that there won't be a sea battle tomorrow. The future contingent is not now determinately or definitely true (or false), so that the future is still open.5 Exercises EXERCISE 1.12.3. Show that 0^ 3 UP is not valid in K. EXERCISE 1.12.4. We showed that the modality collapses in T if DP v D-»P. Show that the argument must break down for K. The Master Argument ofDiodorus Cronus Two schools of logic were distinguished in antiquity: the Peripatetic School, which followed the teaching of Aristotle, and the Stoic School, which was founded by Zeno. The most famous logical practitioner among the Stoics was Chrysippus, who was deeply influenced by the Megarians Diodorus Cronus and Philo (Kneale and Kneale, 1962; Mates, 1961). Diodorus is responsible for one of the most famous of the Stoic arguments, the so-called "Master Argument." It is a matter of speculation as to who is the Master referred to—Diodorus or Fate. (Kneale and Kneale, 1962, p. 119) records the description from Epictetus: The Master Argument seems to have been formulated with some such starting points as these. There is an incompatibility between the three following propositions, "Everything that is past and true is necessary," "The impossible does not follow from the possible," and "What neither is nor will be is possible." Seeing this incompatibility, Diodorus used the convincingness of the first two propositions to establish the thesis that nothing is possible which neither is nor will be true. Sorabji (1980) notes that the first two premises can both be found in Aristotle, but not the conclusion: Aristotle believed that something could happen even though it never does—this cloak could be cut up even though it never is. There is good reason to think that Diodorus's argument is a sharpened version of the fatalistic argument Aristotle had considered in De Interpretatione 9. We will now try to reconstruct Diodorus's argument using the tools of modal logic. 5 This notion of definite truth has a formal representation using the notion of supervaluations. For a good discussion of supervaluations, see (Fraassen, 1966).

PROPOSITIONAL MODAL LOGIC 39 Let us symbolize Diodorus's first premise, Everything that is past and true is necessary, as (1.26) PP D DPP, where PP is the tense-logical representation introduced in Section 1.5 for It was the case that P. There are a number of ways in which to interpret his second premise, The impossible does not follow from the possible. We shall take it as the Rule of Inference:6 (1 27) PDQ We shall also need one more assumption that is not explicit in the argument, namely, that time is discrete.7 Then we can show that the specifically Diodorian claim follows: What neither is nor will be is impossible, i.e. (1.28) (-.P A-.FP) D-OP. (FP is the tense-logical representation for It will be the case that P). To be concrete, let P be "There is a sea battle taking place." Now, suppose there is no sea battle taking place and never will be, i.e., (1.29) -Pa-FP If no sea battle is taking place and none will, then—and right here is where the assumption of the discreteness of time comes in—there was a time (for example, the moment just before the present) after which no sea battle would take place, i.e., (1.30) (-.P A-.FP) DP-FP It follows by modus ponens from (1.29) and (1.30) that there was a time in the past when it was true that no sea battle would later take place, i.e., (1.31) P-FP, So, by modus ponens and the first of Diodorus's premises, (1.26), (1.32) DP-FP 6 Note that (1.27) is quite different from (P D Q) D (OP D 0Q): to infer OP D 0Q by the rule, we require not merely that P D Q be true, but that it be logically true. 7 Prior (1967), whose reconstruction is similar to ours, also makes this very same assumption.

40 CHAPTER ONE which is to say that it is not possible that it not have been the case that it would be true that no sea battle will ever take place,8 i.e., (1.33) -0-P-FP. So, -»P-»FP is impossible. But if the sea battle were taking place, it would not have been the case that no sea battle would ever take place, i.e., (1.34) P d -P-FP, This is a logical truth based on the meaning of the tense operators. So, by our Rule of Inference (1.27), (1.35) OP D 0-P-FP, And since we have the negation of the consequent in (1.33), an application of Modus Tollens yields (1.36) -0^. On the assumption of (1.29) we have derived (1.36) using the Diodorian premises (1.26) and (1.27). Thus we have the Diodorian conclusion (1.28). Diodorus's definition The possible is that which either is or will be [true] was apparently widely known throughout the ancient world (Mates, 1961; Prior, 1957).9 And widely debated. It is none other than the Principle of Plenitude: every possibility is realized (at some time). 8 This is a good example of the virtues of symbolization: it is highly unlikely that we would have been able to come up with this English rendering so readily without the symbolic formulation. 9 His definitions of the remaining modals are entirely consistent: The impossible is that which, being false, will not be true The necessary is that which, being true, will not be false The nonnecessary is that which either is or will be false Formally, these turn out as follows: OP = PvFP -•OP = -PaG-P DP = PaGP -DP = iPvF-i?

PROPOSITIONAL MODAL LOGIC 41 The Once and Future Conditional Some modern logicians read Ifp, then q as the material conditional: i.e., it is false if the antecedent is true and consequent false; otherwise it is true. Some logicians have also called it \ht philonean conditional, after the Stoic logician Philo, who argued for this reading. Just as necessity was a source of heated dispute among the ancients, so too was the conditional. Mates (1961) reports that Diodorus disputed Philo's reading of the conditional, preferring to regard a conditional as true only when it is impossible for the antecedent to be true and consequent false—of course, in his special temporal sense of impossible, viz., that at no time is the antecedent true and consequent false. So, as Mates (1961) (p. 45) puts it, "A conditional holds in the Diodorean sense if and only if it holds at all times in the Philonean sense." How appropriate that the modern reintroduction of modal logic should turn on this very same issue. Lewis (1918) is largely responsible for bringing modal logic back into the mainstream of logic.10 As with Diodorus, Lewis found the material conditional wanting as a formalization of If p, then q, especially insofar as it entailed the so-called Paradoxes of the Material Conditional. These are, first, that a false statement (materially) implies anything, i.e., -~»P D (P D Q), and, second, that a true statement is (materially) implied by anything, i.e., Q D (P D Q)- Lewis sought to tighten up the connection between antecedent and consequent, and he introduced a new connective, symbolized by -3 (known as "the fishhook"). P -3 Q, expresses that P strictly implies Q, and is definable in terms of □ as follows: ^-3 G =&/□(/» =>G). We might very well term this the diodorean conditional, for to say that P strictly implies Q is to say that the material (i.e., philonean) conditional holds necessarily. It is equivalent to ->0(P A -»Q): it is impossible for P to be true and Q to be false. Lewis's introduction of -3 was, however, flawed by use/mention confusion. In P strictly implies Q, we appear to be speaking about propositions, not using them, and so necessity appears to be a predicate of sentences, not a propositional operator, as we have treated it in our formulation of modal logic. Lewis, unfortunately, was not particularly careful in this regard. For example, he says in (Lewis and Langford, 1959) ... the relation of strict implication expresses precisely that relation which holds when valid deduction is possible, and fails to hold when valid deduction is not possible. In that sense, the system of Strict Implication may be said to provide that canon 10 Lewis eventually introduced five distinct formulations for modal logic, of which S4 and S5 are the most well known.

42 CHAPTER ONE and critique of deductive inference which is the desideratum of logical investigation, (p. 247) Note the two-fold confusion in this passage. First, the expression "valid deduction" combines semantical and syntactical notions without clearly distinguishing them. Second, whether syntactical or semantical, the relation is one that holds between sentences: that the relation holds is a fact about sentences, and so the variables on either side of -3 are to be replaced by names of sentences (since one is speaking about them) rather than by sentences themselves. These confusions were seized upon by foes of formalized modal logic, and Lewis's achievements were overshadowed in the subsequent controversy, a controversy which has its roots deep in the history of the subject, as we shall now see. The Reality of Necessity In order to understand the continuing controversy about modal logic, we must return to our discussion in Section 1.2 about whether the modal is part of the content of a judgment. The cognitive content of a sentence, the proposition it expresses, is commonly thought of as encapsulated by its truth conditions, i.e., the features of the reality it purports to describe that make it true. The proposition that John is a man, for example, is true if and only if the individual John has the property of being a man. But the proposition thai John is necessarily a man will require more for its truth than just that the individual John has the property of being a man—there will also have to be something in reality corresponding to his necessarily being a man. The something more is usually thought of as a real essence—a property an individual has necessarily, i.e., a property that is part of his essential nature so that he could not exist if he lacked the property. Real essences, natural kinds, natural laws, and related notions were characteristic of the scholastic thinking that derived from Aristotelian metaphysics. This prevalent way of thinking admitted necessary connections in reality, between an individual and some of its properties (real essences), between a group of individuals and some of their common properties (natural kinds), between an individual or group doing something and another (possibly the same) individual or group's doing something (natural laws). From the Realist standpoint, a modal is comfortably conceived of in much the same way as any other part of a proposition, namely, as representing a feature of reality that determines the truth of the proposition. One can readily understand, then, how a healthy skepticism about these necessities in nature will nudge one towards the Kant/Frege position described in Section 1.2 which denies that the modals belong to the content of a claim. The treatment of causality in (Hume, 1888) captures this view.

PROPOSITIONAL MODAL LOGIC 43 A proposition saying that events of type A cause events of type B is widely thought to make a claim about the way things must be. Whenever events of type A occur, events of type B must occur. Hume, however, denies that there are necessary connections in nature. And if there are no necessary connections in nature, then no part of a proposition can represent them as anything that determines the truth of the proposition. So the "must" in the causal claim is not part of the proposition at all. Its role must be assigned elsewhere. Hume (1888) locates the seeming necessary connection between cause and effect in the habitual connection of our ideas of these causes and effects: the invocation of the idea of the cause immediately invokes the idea of the effect. Despite their widely divergent views, Kant and Frege appear, like Hume, to have located necessity in the realm of ideas. Kneale and Kneale (1962) say Kant holds "that a modal adverb such as "possibly" represents only a way of thinking the thought enunciated by the rest of the sentence in which it occurs." (p. 36) Frege (1879), in a similar vein, says: "If a proposition is presented as possible, then either the speaker is refraining from judgment... or else he is saying that in general the negation of the proposition is false." (p. 5) Both believe that the apodeictic and problematic indicators form no part of the content of the judgment. But the role they are supposed to play is a bit uncertain. One reading is that the modal introduces the speaker's attitude toward the content, clearly locating it in non-cognitive psychology; another reading is that the modal connects the content with other judgments, moving it back into the realm of logic. On the first reading, a judgment of possibility is a possible judgment. Appending "possibly" to a content indicates that one is merely entertaining it but not committing oneself to it. Or, it might have the force of "perhaps." But this view seems correct only if one looks at assertions of modal claims. For, if a modal claim is not itself asserted, but forms part of a larger claim, occurring, for instance, as antecedent or consequent of a conditional like (P D <)P), this view no longer looks plausible. It is quite possible that Frege (1879) came to believe that there is no difference between the assertoric and apodeictic judgments because he fell prey to a well-known modal error. Given the modal inference rule of Necessitation characteristic of normal modal logics, (1.37) If hPthenhDP (h symbolizes it is asserted thai) and the "Axiom of Necessity," as Hughes and Cresswell (1996) call it, (1.38) DP D P

44 CHAPTER ONE we obtain the derived rule:11 (1.39) h P if, and only if h DP And (1.39) makes it look as though there really is no logical difference in content between the assertoric and the apodeictic judgments. But, of course, this is not so. DP and P differ in content. The true (1.39) must be distinguished from the (usually) false (1.40) P = DP The collapse of the modality effected by (1.40) is avoided: although (1.38) (i.e., If necessarily true, then true) is true, its converse, (1.41) P DDP, (i.e., If true, then necessarily true), is (usually) not. On the second reading, the modal relates this content to other contents. As Frege said, to claim that a content is necessary is to say that "it follows only from universal judgments." The necessity of a content appears to be a function of its justification. And this brings us back to the position of Lewis. It should be quite clear to the reader how the philosophical issues concerning modality have polarized. The Realist about necessity has no problem taking a modal as part of the proposition. The Anti-Realist about necessity takes the modal out of the proposition and raises it up a level, either as a comment about the propositional representation or, noncognitively, as an expression of one's attitude about the propositional representation. The Anti- Realist about necessity in the twentieth century has been most comfortable regarding modal claims, if cognitive at all, as explicitly about sentences, and so as metalinguistic claims, a level at which the development of any interesting modal logics is seriously restricted. In a very famous comment, Marcus (1992) characterized the most serious contemporary foe of quantified modal logic, W. V. O. Quine, as believing "that it was conceived in sin: the sin of confusing use and mention."(p. 5) But the real evil of quantified modal logic for Quine is its apparent commitment to "the metaphysical jungle of Aristotelian essentialism." Quine, and his fellow critics of quantified modal logic, instead of arguing the merits, even the coherence of essentialism, have drawn battle lines around the coherence of modal logic itself. And this criticism ha