Logic for Philosophy

Logic for Philosophy

Theodore Sider December 4, 2007

Preface

This book is an elementary introduction to the logic that students of contemporary philosophy ought to know. It covers i) basic approaches to logic, including proof theory and especially model theory, ii) extensions of standard logic (such as modal logic) that are important in philosophy, and iii) some elementary philosophy of logic. It prepares students to read the logically sophisticated articles in today's philosophy journals, and helps them resist bullying by symbolmongerers. In short, it teaches the logic necessary for being a contemporary philosopher.

For better or for worse (I think better), the last century-or-so's developments in logic are part of the shared knowledge base of philosophers, and inform, in varying degrees of directness, every area of philosophy. Logic is part of our shared language and inheritance. The standard philosophy curriculum therefore includes a healthy dose of logic. This is a good thing. But the advanced logic that is part of this curriculum is usually a course in "mathematical logic", which usually means an intensive course in metalogic (for example, a course based on the excellent Boolos and Jeffrey (1989).) I do believe in the value of such a course. But if advanced undergraduate philosophy majors or beginning graduate students are to have one advanced logic course, that course should not, I think, be a course in metalogic. The standard metalogic course is too mathematically demanding for the average philosophy student, and omits material that the average student needs to know. If there is to be only one advanced logic course, let it be a course designed to instill logical literacy.

I begin with a sketch of standard propositional and predicate logic (developed more formally than in a typical intro course.) I brie y discuss a few extensions and variations on each (e.g., three-valued logic, de nite descriptions). I then discuss modal logic and counterfactual conditionals in detail. I presuppose familiarity with the contents of a typical intro logic course: the meanings of the logical symbols of rst-order predicate logic without identity

i

PREFACE

ii

or function symbols; truth tables; translations from English into propositional and predicate logic; some proof system (e.g., natural deduction) in propositional and predicate logic.

I drew heavily from the following sources, which would be good for supplemental reading:

? Propositional logic: Mendelson (1987) ? Descriptions, multi-valued logic: Gamut (1991a) ? Sequents: Lemmon (1965)

? Further quanti ers: Glanzberg (2006); Sher (1991, chapter 2); Westerst?hl (1989); Boolos and Jeffrey (1989, chapter 18)

? Modal logic: Gamut (1991b); Cresswell and Hughes (1996) ? Semantics for intuitionism : Priest (2001)

? Counterfactuals: Lewis (1973)

? Two-dimensional modal logic: Davies and Humberstone (1980)

Another source was Ed Gettier's 1988 modal logic class at the University of Massachusetts.

I am also deeply grateful for feedback from colleagues, and from students in courses on this material. In particular, Marcello Antosh, Josh Armstrong, Gabe Greenberg, Angela Harper, Sami Laine, Gregory Lavers, Alex Morgan, Jeff Russell, Brock Sides, Jason Turner, Crystal Tychonievich, Jennifer Wang, Brian Weatherson, and Evan Williams: thank you.

Contents

Preface

i

1 Nature of Logic

1

1.1 Logical consequence and logical truth . . . . . . . . . . . . . . . . . 2

1.2 Form and abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Formal logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Correctness and application . . . . . . . . . . . . . . . . . . . . . . . 7

1.5 The nature of logical consequence . . . . . . . . . . . . . . . . . . . 8

1.6 Extensions, deviations, variations . . . . . . . . . . . . . . . . . . . . 10

1.6.1 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.6.2 Deviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.6.3 Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.7 Metalogic, metalanguages, and formalization . . . . . . . . . . . . 12

1.8 Set theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Propositional Logic

18

2.1 Grammar of PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2 The semantic approach to logic . . . . . . . . . . . . . . . . . . . . . 21

2.3 Semantics of PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4 Natural deduction in PL . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4.1 Sequents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.4.2 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4.3 Sequent proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4.4 Example sequent proofs . . . . . . . . . . . . . . . . . . . . . 35

2.5 Axiomatic proofs in PL . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.5.1 Example axiomatic proofs . . . . . . . . . . . . . . . . . . . . 42

2.5.2 The deduction theorem . . . . . . . . . . . . . . . . . . . . . 47

2.6 Soundness and completeness of PL . . . . . . . . . . . . . . . . . . 47

iii

CONTENTS

iv

3 Variations and Deviations from PL

52

3.1 Alternate connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.1.1 Symbolizing truth functions in propositional logic . . . 52

3.1.2 Inadequate connective sets . . . . . . . . . . . . . . . . . . . 56

3.1.3 Sheffer stroke . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.2 Polish notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.3 Multi-valued logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.3.1 Lukasiewicz's system . . . . . . . . . . . . . . . . . . . . . . . 60

3.3.2 Kleene's "strong" tables . . . . . . . . . . . . . . . . . . . . . 62

3.3.3 Kleene's "weak" tables (Bochvar's tables) . . . . . . . . . . 63

3.3.4 Supervaluationism . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.4 Intuitionism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4 Predicate Logic

71

4.1 Grammar of predicate logic . . . . . . . . . . . . . . . . . . . . . . . 71

4.2 Semantics of predicate logic . . . . . . . . . . . . . . . . . . . . . . . 72

4.3 Establishing validity and invalidity . . . . . . . . . . . . . . . . . . . 77

5 Extensions of Predicate Logic

80

5.1 Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.1.1 Grammar for the identity sign . . . . . . . . . . . . . . . . . 80

5.1.2 Semantics for the identity sign . . . . . . . . . . . . . . . . 81

5.1.3 Symbolizations with the identity sign . . . . . . . . . . . 81

5.2 Function symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.2.1 Grammar for function symbols . . . . . . . . . . . . . . . . 85

5.2.2 Semantics for function symbols . . . . . . . . . . . . . . . . 86

5.2.3 Symbolizations with function symbols: some examples 88

5.3 De nite descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

5.3.1 Grammar for . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.3.2 Semantics for . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

5.3.3 Eliminability of function symbols and de nite descriptions 92

5.4 Further quanti ers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.4.1 Generalized monadic quanti ers . . . . . . . . . . . . . . . 96

5.4.2 Generalized binary quanti ers . . . . . . . . . . . . . . . . . 98

5.4.3 Second-order logic . . . . . . . . . . . . . . . . . . . . . . . . 100

CONTENTS

v

6 Propositional Modal Logic

103

6.1 Grammar of MPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.2 Symbolizations in MPL . . . . . . . . . . . . . . . . . . . . . . . . . . 105

6.3 Semantics for MPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6.3.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

6.3.2 Kripke models . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

6.3.3 Semantic validity proofs . . . . . . . . . . . . . . . . . . . . . 115

6.3.4 Countermodels . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.3.5 Schemas, validity, and invalidity . . . . . . . . . . . . . . . . 135

6.4 Axiomatic systems of MPL . . . . . . . . . . . . . . . . . . . . . . . . 137

6.4.1 System K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.4.2 System D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

6.4.3 System T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

6.4.4 System B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

6.4.5 System S4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

6.4.6 System S5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

6.4.7 Substitution of equivalents and modal reduction . . . . . 153

6.5 Soundness in MPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

6.5.1 Soundness of K . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

6.5.2 Soundness of T . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

6.5.3 Soundness of B . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

6.6 Completeness of MPL . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

6.6.1 Canonical models . . . . . . . . . . . . . . . . . . . . . . . . . 160

6.6.2 Maximal consistent sets of wffs . . . . . . . . . . . . . . . . 161

6.6.3 De nition of canonical models . . . . . . . . . . . . . . . . 162

6.6.4 Features of maximal consistent sets . . . . . . . . . . . . . 163

6.6.5 Maximal consistent extensions . . . . . . . . . . . . . . . . . 164

6.6.6 "Mesh" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

6.6.7 The coincidence of truth and membership in canonical

models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

6.6.8 Completeness of systems of MPL . . . . . . . . . . . . . . 169

7 Variations on MPL

172

7.1 Propositional tense logic . . . . . . . . . . . . . . . . . . . . . . . . . . 172

7.1.1 The metaphysics of time . . . . . . . . . . . . . . . . . . . . 172

7.1.2 Tense operators . . . . . . . . . . . . . . . . . . . . . . . . . . 174

7.1.3 Syntax of tense logic . . . . . . . . . . . . . . . . . . . . . . . 176

7.1.4 Possible worlds semantics for tense logic . . . . . . . . . . 176

CONTENTS

vi

7.1.5 Formal constraints on . . . . . . . . . . . . . . . . . . . . . 178 7.2 Intuitionist propositional logic . . . . . . . . . . . . . . . . . . . . . . 180

7.2.1 Kripke semantics for intuitionist propositional logic . . 180 7.2.2 Examples and proofs . . . . . . . . . . . . . . . . . . . . . . . 183 7.2.3 Soundness and other facts about intuitionist validity . . 186

8 Counterfactuals

190

8.1 Natural language counterfactuals . . . . . . . . . . . . . . . . . . . . 191

8.1.1 Not truth-functional . . . . . . . . . . . . . . . . . . . . . . . 191

8.1.2 Can be contingent . . . . . . . . . . . . . . . . . . . . . . . . . 191

8.1.3 No augmentation . . . . . . . . . . . . . . . . . . . . . . . . . 192

8.1.4 No contraposition . . . . . . . . . . . . . . . . . . . . . . . . . 193

8.1.5 Some implications . . . . . . . . . . . . . . . . . . . . . . . . . 193

8.1.6 Context dependence . . . . . . . . . . . . . . . . . . . . . . . 194

8.2 The Lewis/Stalnaker approach . . . . . . . . . . . . . . . . . . . . . 196

8.3 Stalnaker's system (SC) . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

8.3.1 Syntax of SC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

8.3.2 Semantics of SC . . . . . . . . . . . . . . . . . . . . . . . . . . 197

8.4 Validity proofs in SC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

8.5 Countermodels in SC . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

8.6 Logical Features of SC . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

8.6.1 Not truth-functional . . . . . . . . . . . . . . . . . . . . . . . 211

8.6.2 Can be contingent . . . . . . . . . . . . . . . . . . . . . . . . . 211

8.6.3 No augmentation . . . . . . . . . . . . . . . . . . . . . . . . . 211

8.6.4 No contraposition . . . . . . . . . . . . . . . . . . . . . . . . . 211

8.6.5 Some implications . . . . . . . . . . . . . . . . . . . . . . . . . 212

8.6.6 No exportation . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

8.6.7 No importation . . . . . . . . . . . . . . . . . . . . . . . . . . 214

8.6.8 No hypothetical syllogism (transitivity) . . . . . . . . . . . 214

8.6.9 No transposition . . . . . . . . . . . . . . . . . . . . . . . . . . 215

8.7 Lewis's criticisms of Stalnaker's theory . . . . . . . . . . . . . . . . 216

8.8 Lewis's system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

8.9 The problem of disjunctive antecedents . . . . . . . . . . . . . . . 222

9 Quanti ed Modal Logic

224

9.1 Grammar of QML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

9.2 Symbolizations in QML . . . . . . . . . . . . . . . . . . . . . . . . . . 224

9.3 A simple semantics for QML . . . . . . . . . . . . . . . . . . . . . . . 226

CONTENTS

vii

9.4 Countermodels and validity proofs in SQML . . . . . . . . . . . . 228 9.5 Philosophical questions about SQML . . . . . . . . . . . . . . . . . 234

9.5.1 The necessity of identity . . . . . . . . . . . . . . . . . . . . 234 9.5.2 The necessity of existence . . . . . . . . . . . . . . . . . . . 236 9.5.3 Necessary existence defended . . . . . . . . . . . . . . . . . 241 9.6 Variable domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 9.6.1 Countermodels to the Barcan and related formulas . . . 246 9.6.2 Expanding, shrinking domains . . . . . . . . . . . . . . . . 248 9.6.3 Strong and weak necessity . . . . . . . . . . . . . . . . . . . 249

10 Two-dimensional modal logic

253

10.1 Actuality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

10.1.1 Kripke models with actual worlds . . . . . . . . . . . . . . 254

10.1.2 Semantics for @ . . . . . . . . . . . . . . . . . . . . . . . . . . 255

10.1.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

10.2 ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 10.2.1 Two-dimensional semantics for ? . . . . . . . . . . . . . . 258

10.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

10.3 Fixedly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

10.3.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 10.4 A philosophical application: necessity and a priority . . . . . . . . 265

References

272

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download