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(s): Richard W. Kaye
Edition: 1
Publisher: Cambridge University Press
Year: 2007
Language: English
Pages: 217
Tags: Математика;Математическая логика;
Contents......Page 6
Preface......Page 8
How to read this book......Page 13
1.1 Two ways of looking at mathematics......Page 14
1.2 Examples and exercises......Page 19
1.3 Konig’s Lemma and reverse mathematics* ......Page 22
2.1 Introduction to order......Page 24
2.2 Examples and exercises Exercise 2.21......Page 30
2.3 Zorn’s Lemma and the Axiom of Choice*......Page 33
3.1 Formal systems......Page 37
3.2 Examples and exercises......Page 46
3.3 Post systems and computability*......Page 48
4.1 Proving statements about a poset......Page 51
4.2 Examples and exercises......Page 60
4.3 Linearly ordering algebraic structures*......Page 62
5.1 Boolean algebras......Page 68
5.3 Boolean algebra and the algebra of Boole*......Page 74
6.1 A system for proof about propositions......Page 77
6.2 Examples and exercises Exercise 6.17......Page 88
6.3 Decidability of propositional logic*......Page 90
7.1 Semantics for propositional logic......Page 93
7.2 Examples and exercises......Page 103
7.3 The complexity of satis.ability*......Page 108
8.1 Algebraic theory of boolean algebras......Page 113
8.2 Examples and exercises Exercise 8.18......Page 120
8.3 Tychonov’s Theorem*......Page 121
8.4 The Stone Representation Theorem*......Page 123
9.1 First-order languages......Page 129
9.2 Examples and exercises......Page 147
9.3 Secondand higher-order logic*......Page 150
10.1 Proof of completeness and compactness......Page 153
10.2 Examples and exercises......Page 159
10.3 The Compactness Theorem and topology*......Page 162
10.4 The Omitting Types Theorem*......Page 165
11.1 Countable models and beyond......Page 173
11.2 Examples and exercises Exercise 11.36......Page 186
11.3 Cardinal arithmetic*......Page 189
12.1 In.nitesimal numbers......Page 195
12.2 Examples and exercises Exercise 12.3......Page 199
12.3 Overspill and applications*......Page 200
References......Page 212
Index......Page 213
