You are here

Propositional and Predicate Calculus: A Model of Argument

Derek Goldrei
Springer Verlag
Publication Date: 
Number of Pages: 
[Reviewed by
Paul E. Cohen
, on

As its title promises, this textbook presents an introduction to the propositional calculus and to the predicate calculus. It is written in a clear but conversational manner that should make this subject readily accessible to any mathematically mature reader. The clear writing and good motivation should be appreciated by students using it as a text in a course as well as readers using it for independent study.

While the focus of Goldrei’s book is on the formalism of logic, he draws examples from mathematics to motivate and to enrich this material. This appears to be the greatest strength of his treatment of the subject. Examples come from algebra, number theory, geometry and topology, but the examples are explored without much risk of scaring away a student who lacks a good background in a few of these areas.

A second strength of this textbook is that it introduces the reader to a broad swath of concepts at the heart of the foundations of mathematics. After working through the book, the student should have a good understanding of semantics for both the propositional and predicate calculus, though paradoxically the author does not appear to introduce either of these specific terms. Still, the student of this text will come away with an understanding of models, some techniques for constructing them, and an appreciation for the existence of countable and non-standard models. At the same time the student will come away with some understanding of decidable theories and an appreciation for purely syntactical arguments.

However, the student will not be exposed to recursive functions or to Gödel’s incompleteness theorem. Perhaps Goldrei should consider writing a second volume to accompany this fine introduction.

Paul Cohen received his Ph.D. from the University of Illinois, was appointed as a Member of the Institute for Advanced Study by Kurt Gödel, and has taught at the University of Tennessee and at Lehigh University. He currently lives in Maine and is teaching at Colby College.

1 Introduction 1

1.1 Outline of the book 1

1.2 Assumed knowledge 6

2 Propositions and truth assignments 17

2.1 Introduction 17

2.2 The construction of propositional formulas 19

2.3 The interpretation of propositional formulas 31

2.4 Logical equivalence 48

2.5 The expressive power of connectives 63

2.6 Logical consequence 74

3 Formal propositional calculus 85

3.1 Introduction 85

3.2 A formal system for propositional calculus 87

3.3 Soundness and completeness 100

3.4 Independence of axioms and alternative systems 119

4 Predicates and models 133

4.1 Introduction: basic ideas 133

4.2 First-order languages and their interpretation 140

4.3 Universally valid formulas and logical equivalence 163

4.4 Some axiom systems and their consequences 185

4.5 Substructures and Isomorphisms 208

5 Formal predicate calculus 217

5.1 Introduction 217

5.2 A formal system for predicate calculus 221

5.3 The soundness theorem 242

5.4 The equality axioms and non-normal structures 247

5.5 The completeness theorem 252

6 Some uses of compactness 265

6.1 Introduction: the compactness theorem 265

6.2 Finite axiomatizability 266

6.3 Some non-axiomatizable theories 272

6.4 The L¨owenheim–Skolem theorems 277

6.5 New models from old ones 289

6.6 Decidable theories 298

Bibliography 309

Index 311