Logic for Philosophy

[Pages:377]Logic for Philosophy

Theodore Sider

May ,

Preface

This book is an introduction to logic for students of contemporary philosophy. 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 symbol-mongerers. In short, it teaches the logic you need to know in order to be 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 nearly 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 in many cases only a single advanced logic course is required, which becomes the de facto sole exposure to advanced logic for many undergraduate philosophy majors and beginning graduate students. And this one course is often an intensive survey of metalogic (for example, one based on the excellent Boolos et al. ( ).) I do believe in the value of such a course, especially for students who take multiple logic courses or specialize in "technical" areas of philosophy. But for students taking only a single 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 ought to know. If there can be only one, let it be a crash course in logic literacy.

"Logic literacy" includes knowing what metalogic is all about. And you can't really learn about anything in logic without getting your hands dirty and doing it. So this book does contain some metalogic (e.g., soundness and completeness proofs in propositional logic and propositional modal logic). But it doesn't cover the central metalogical results one normally covers in a mathematical logic course: soundness and completeness in predicate logic, computability,

i

PREFACE

ii

G?del's incompleteness theorems, and so on.

I have decided to be very sloppy about use and mention. When such issues matter I draw attention to them; but where they do not I do not.

Solutions to exercises marked with a single asterisk (*) are included in Appendix A. Exercises marked with a double asterisk (**) tend to be more dif cult, and have hints in Appendix A.

I drew heavily from the following sources, which would be good for supplemental reading: Bencivenga ( ) (free logic); Boolos et al. ( , chapter

) (metalogic, second-order logic); Cresswell ( ) (two-dimensional modal logic); Davies and Humberstone ( ) (two-dimensional modal logic); Gamut ( a,b) (Descriptions, -abstraction, multi-valued, modal, and tense logic); Hilpinen ( ) (deontic logic); Hughes and Cresswell ( ) (modal logic--I borrowed particularly heavily here--and tense logic); Kripke ( ) (intuitionistic logic); Lemmon ( ) (sequents in propositional logic); Lewis ( a) (counterfactuals); Mendelson ( ) (propositional and predicate logic, metalogic); Meyer ( ) (epistemic logic); Priest ( ) (intuitionistic and paraconsistent logic); Stalnaker ( ) (-abstraction); Westerst?hl ( ) (generalized quanti ers).

Another important source, particularly for chapters 6 and 8, was Ed Gettier's modal logic class at the University of Massachusetts. The rst incarnation

of this work grew out of my notes from this course. I am grateful to Ed for his wonderful class, and for getting me interested in logic.

I am also deeply grateful for feedback from many students, colleagues, and referees. In particular, Marcello Antosh, Josh Armstrong, Dean Chapman, Tony Dardis, Justin Clarke-Doane, Mihailis Diamantis, Mike Fara, Gabe Greenberg, Angela Harper, John Hawthorne, Paul Hovda, Phil Kremer, Sami Laine, Gregory Lavers, Brandon Look, Stephen McLeod, Kevin Moore, Alex Morgan, Tore Fjetland Ogaard, Nick Riggle, Jeff Russell, Brock Sides, Jason Turner, Crystal Tychonievich, Jennifer Wang, Brian Weatherson, Evan Williams, Xing Taotao, Seth Yalcin, Zanja Yudell, Richard Zach, and especially Agust?n Rayo: thank you.

Contents

Preface

i

1 What is Logic? 1.1 Logical consequence and logical truth . . . . . . . . . . . . . . . 1.2 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Metalogic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 1.1?1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 The nature of logical consequence . . . . . . . . . . . . . . . . . . Exercise 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Logical constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Extensions, deviations, variations . . . . . . . . . . . . . . . . . . . 1.8 Set theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 1.4?1.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Propositional Logic 2.1 Grammar of PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The semantic approach to logic . . . . . . . . . . . . . . . . . . . . 2.3 Semantics of propositional logic . . . . . . . . . . . . . . . . . . . Exercise 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Validity and invalidity in PL . . . . . . . . . . . . . . . . . . . . . . Exercise 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Schemas, validity, and invalidity . . . . . . . . . . . . . . 2.5 Sequent proofs in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Sequents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.3 Sequent proofs . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.4 Example sequent proofs . . . . . . . . . . . . . . . . . . . Exercise 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

CONTENTS

iv

2.6 Axiomatic proofs in PL . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.7 Soundness of PL and proof by induction . . . . . . . . . . . . . . Exercises 2.5?2.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.8 PL proofs and the deduction theorem . . . . . . . . . . . . . . . Exercises 2.11?2.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.9 Completeness of PL . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9.1 Maximal consistent sets of wffs . . . . . . . . . . . . . . 2.9.2 Maximal consistent extensions . . . . . . . . . . . . . . . 2.9.3 Features of maximal consistent sets . . . . . . . . . . . . 2.9.4 The proof . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Beyond Standard Propositional Logic 3.1 Alternate connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Symbolizing truth functions in propositional logic . 3.1.2 Sheffer stroke . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Inadequate connective sets . . . . . . . . . . . . . . . . . Exercises 3.1?3.3 . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Polish notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Nonclassical propositional logics . . . . . . . . . . . . . . . . . . . 3.4 Three-valued logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Lukasiewicz's system . . . . . . . . . . . . . . . . . . . . . Exercises 3.5?3.6 . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Kleene's tables . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 3.7?3.9 . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Determinacy . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Priest's logic of paradox . . . . . . . . . . . . . . . . . . . Exercises 3.10?3.11 . . . . . . . . . . . . . . . . . . . . . . . 3.4.5 Supervaluationism . . . . . . . . . . . . . . . . . . . . . . . Exercises 3.12?3.16 . . . . . . . . . . . . . . . . . . . . . . . 3.5 Intuitionistic propositional logic: proof theory . . . . . . . . . . Exercise 3.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Predicate Logic 4.1 Grammar of predicate logic . . . . . . . . . . . . . . . . . . . . . . 4.2 Semantics of predicate logic . . . . . . . . . . . . . . . . . . . . . . Exercise 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CONTENTS

v

4.3 Establishing validity and invalidity . . . . . . . . . . . . . . . . . . Exercises 4.2?4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Axiomatic proofs in PC . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5 Metalogic of PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Beyond Standard Predicate Logic 5.1 Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

5.1.3 Symbolizations with the identity sign . . . . . . . . . . Exercises 5.1?5.2 . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Function symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Grammar for function symbols . . . . . . . . . . . . . .

5.2.2 Semantics for function symbols . . . . . . . . . . . . . . Exercise 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 De nite descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Grammar for . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Semantics for . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 5.5?5.6 . . . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Elimination of function symbols and descriptions . . Exercises 5.7?5.8 . . . . . . . . . . . . . . . . . . . . . . . .

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

5.4.1 Generalized monadic quanti ers . . . . . . . . . . . . . Exercise 5.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4.2 Generalized binary quanti ers . . . . . . . . . . . . . . . Exercise 5.10 . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4.3 Second-order logic . . . . . . . . . . . . . . . . . . . . . . Exercise 5.11 . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5 Complex Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 5.12?5.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.6 Free Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.6.1 Semantics for free logic . . . . . . . . . . . . . . . . . . . Exercises 5.14?5.15 . . . . . . . . . . . . . . . . . . . . . . .

5.6.2 Proof theory for free logic . . . . . . . . . . . . . . . . .

CONTENTS

vi

6 Propositional Modal Logic 6.1 Grammar of MPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

6.3.1 Kripke models . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3.2 Semantic validity proofs . . . . . . . . . . . . . . . . . . . Exercise 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3.3 Countermodels . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

6.4.1 System K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 6.4?6.5 . . . . . . . . . . . . . . . . . . . . . . . .

6.4.2 System D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.3 System T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.4 System B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.5 System S . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.6 System S . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.10 . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.7 Substitution of equivalents and modal reduction . . . Exercise 6.11 . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.5 Soundness in MPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 6.12?6.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5.1 Soundness of K . . . . . . . . . . . . . . . . . . . . . . . . .

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

6.5.3 Soundness of B . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 6.14?6.15 . . . . . . . . . . . . . . . . . . . . . . .

6.6 Completeness in MPL . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6.1 De nition of canonical models . . . . . . . . . . . . . .

6.6.2 Facts about maximal consistent sets . . . . . . . . . . . Exercise 6.16 . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6.3 "Mesh" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 6.17 . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6.4 Truth and membership in canonical models . . . . . .

CONTENTS

vii

6.6.5 Completeness of systems of MPL . . . . . . . . . . . . . Exercises 6.18?6.20 . . . . . . . . . . . . . . . . . . . . . . .

7 Beyond Standard MPL

7.1 Deontic logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 7.1?7.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2 Epistemic logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 7.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3 Propositional tense logic . . . . . . . . . . . . . . . . . . . . . . . .

7.3.1 The metaphysics of time . . . . . . . . . . . . . . . . . . .

7.3.2 Tense operators . . . . . . . . . . . . . . . . . . . . . . . . .

7.3.3 7.3.4

Kripke-style semantics for tense logic . . . . . . . . . .

Exercises 7.4?7.5 . . . . . . . . . . . . . . . . . . . . . . . . Formal constraints on . . . . . . . . . . . . . . . . . . . Exercise 7.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.4 Intuitionistic propositional logic: semantics . . . . . . . . . . . .

7.4.1 Proof stages . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 7.7?7.8 . . . . . . . . . . . . . . . . . . . . . . . .

7.4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 7.9?7.10 . . . . . . . . . . . . . . . . . . . . . . . .

7.4.3 Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises 7.11?7.13 . . . . . . . . . . . . . . . . . . . . . . .

8 Counterfactuals 8.1 Natural language counterfactuals . . . . . . . . . . . . . . . . . . . 8.1.1 Antecedents and consequents . . . . . . . . . . . . . . . 8.1.2 Can be contingent . . . . . . . . . . . . . . . . . . . . . . . 8.1.3 No augmentation . . . . . . . . . . . . . . . . . . . . . . . 8.1.4 No contraposition . . . . . . . . . . . . . . . . . . . . . . . 8.1.5 Some implications . . . . . . . . . . . . . . . . . . . . . . . 8.1.6 Context dependence . . . . . . . . . . . . . . . . . . . . . 8.2 The Lewis/Stalnaker theory . . . . . . . . . . . . . . . . . . . . . . 8.3 Stalnaker's system (SC) . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Syntax of SC . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Semantics of SC . . . . . . . . . . . . . . . . . . . . . . . . Exercise 8.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Validity proofs in SC . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercise 8.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

Google Online Preview   Download