Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000010179331 | QA9 K39 2007 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
This undergraduate textbook covers the key material for a typical first course in logic, in particular presenting a full mathematical account of the most important result in logic, the Completeness Theorem for first-order logic. Looking at a series of interesting systems, increasing in complexity, then proving and discussing the Completeness Theorem for each, the author ensures that the number of new concepts to be absorbed at each stage is manageable, whilst providing lively mathematical applications throughout. Unfamiliar terminology is kept to a minimum, no background in formal set-theory is required, and the book contains proofs of all the required set theoretical results. The reader is taken on a journey starting with König's Lemma, and progressing via order relations, Zorn's Lemma, Boolean algebras, and propositional logic, to completeness and compactness of first-order logic. As applications of the work on first-order logic, two final chapters provide introductions to model theory and nonstandard analysis.
Author Notes
Richard Kaye is Senior Lecturer in Pure Mathematics at the University of Birmingham.
Table of Contents
| Preface | p. vii |
| How to read this book | p. xii |
| 1 Konig's Lemma | p. 1 |
| 1.1 Two ways of looking at mathematics | p. 1 |
| 1.2 Examples and exercises | p. 6 |
| 1.3 Konig's Lemma and reverse mathematics | p. 9 |
| 2 Posets and maximal elements | p. 11 |
| 2.1 Introduction to order | p. 11 |
| 2.2 Examples and exercises | p. 17 |
| 2.3 Zorn's Lemma and the Axiom of Choice | p. 20 |
| 3 Formal systems | p. 24 |
| 3.1 Formal systems | p. 24 |
| 3.2 Examples and exercises | p. 33 |
| 3.3 Post systems and computability | p. 35 |
| 4 Deductions in posets | p. 38 |
| 4.1 Proving statements about a poset | p. 38 |
| 4.2 Examples and exercises | p. 47 |
| 4.3 Linearly ordering algebraic structures | p. 49 |
| 5 Boolean algebras | p. 55 |
| 5.1 Boolean algebras | p. 55 |
| 5.2 Examples and exercises | p. 61 |
| 5.3 Boolean algebra and the algebra of Boole | p. 61 |
| 6 Prepositional logic | p. 64 |
| 6.1 A system for proof about propositions | p. 64 |
| 6.2 Examples and exercises | p. 75 |
| 6.3 Decidability of propositional logic | p. 77 |
| 7 Valuations | p. 80 |
| 7.1 Semantics for propositional logic | p. 80 |
| 7.2 Examples and exercises | p. 90 |
| 7.3 The complexity of satisfiability | p. 95 |
| 8 Filters and ideals | p. 100 |
| 8.1 Algebraic theory of boolean algebras | p. 100 |
| 8.2 Examples and exercises | p. 107 |
| 8.3 Tychonov's Theorem | p. 108 |
| 8.4 The Stone Representation Theorem | p. 110 |
| 9 First-order logic | p. 116 |
| 9.1 First-order languages | p. 116 |
| 9.2 Examples and exercises | p. 134 |
| 9.3 Second- and higher-order logic | p. 137 |
| 10 Completeness and compactness | p. 140 |
| 10.1 Proof of completeness and compactness | p. 140 |
| 10.2 Examples and exercises | p. 146 |
| 10.3 The Compactness Theorem and topology | p. 149 |
| 10.4 The Omitting Types Theorem | p. 152 |
| 11 Model theory | p. 160 |
| 11.1 Countable models and beyond | p. 160 |
| 11.2 Examples and exercises | p. 173 |
| 11.3 Cardinal arithmetic | p. 176 |
| 12 Nonstandard analysis | p. 182 |
| 12.1 Infinitesimal numbers | p. 182 |
| 12.2 Examples and exercises | p. 186 |
| 12.3 Overspill and applications | p. 187 |
| References | p. 199 |
| Index | p. 200 |
