A First Course in Mathematical Logic and Set Theory
Books
- Published: 16 October 2015
- ISBN: 9780470905883
- Author(s): Michael L. O'Leary
- View full details
- Buy the book
A mathematical introduction to the theory and applications of logic and set theory with an emphasis on writing proofs
Highlighting the applications and notations of basic mathematical concepts within the framework of logic and set theory, A First Course in Mathematical Logic and Set Theory introduces how logic is used to prepare and structure proofs and solve more complex problems.
The book begins with propositional logic, including two-column proofs and truth table applications, followed by first-order logic, which provides the structure for writing mathematical proofs. Set theory is then introduced and serves as the basis for defining relations, functions, numbers, mathematical induction, ordinals, and cardinals. The book concludes with a primer on basic model theory with applications to abstract algebra. A First Course in Mathematical Logic and Set Theory also includes:
- Section exercises designed to show the interactions between topics and reinforce the presented ideas and concepts
- Numerous examples that illustrate theorems and employ basic concepts such as Euclid’s lemma, the Fibonacci sequence, and unique factorization
- Coverage of important theorems including the well-ordering theorem, completeness theorem, compactness theorem, as well as the theorems of Löwenheim–Skolem, Burali-Forti, Hartogs, Cantor–Schröder–Bernstein, and König
An excellent textbook for students studying the foundations of mathematics and mathematical proofs, A First Course in Mathematical Logic and Set Theory is also appropriate for readers preparing for careers in mathematics education or computer science. In addition, the book is ideal for introductory courses on mathematical logic and/or set theory and appropriate for upper-undergraduate transition courses with rigorous mathematical reasoning involving algebra, number theory, or analysis.
Preface xiii
Acknowledgments xv
List of Symbols xvii
1 Propositional Logic 1
1.1 Symbolic Logic 1
Propositions 2
Propositional Forms 6
Interpreting Propositional Forms 8
Valuations and Truth Tables 11
1.2 Inference 20
Semantics 22
Syntactics 24
1.3 Replacement 32
Semantics 32
Syntactics 35
1.4 Proof Methods 41
Deduction Theorem 41
Direct Proof 46
Indirect Proof 48
1.5 The Three Properties 53
Consistency 53
Soundness 57
Completeness 60
2 FirstOrder
Logic 65
2.1 Languages 65
Predicates 65
Alphabets 69
Terms 72
Formulas 73
2.2 Substitution 77
Terms 77
Free Variables 79
Formulas 80
2.3 Syntactics 87
Quantifier Negation 87
Proofs with Universal Formulas 89
Proofs with Existential Formulas 93
2.4 Proof Methods 98
Universal Proofs 100
Existential Proofs 101
Multiple Quantifiers 103
Counterexamples 104
Direct Proof 105
Existence and Uniqueness 107
Indirect Proof 108
Biconditional Proof 110
Proof of Disunctions 114
Proof by Cases 114
3 Set Theory 119
3.1 Sets and Elements 119
Rosters 120
Famous Sets 121
Abstraction 123
3.2 Set Operations 128
Union and Intersection 128
Set Difference 129
Cartesian Products 132
Order of Operations 134
3.3 Sets within Sets 137
Subsets 137
Equality 139
3.4 Families of Sets 150
Power Set 153
Union and Intersection 154
Disjoint and Pairwise Disjoint 157
4 Relations and Functions 163
4.1 Relations 163
Composition 165
Inverses 167
4.2 Equivalence Relations 170
Equivalence Classes 173
Partitions 175
4.3 Partial Orders 179
Bounds 183
Comparable and Compatible Elements 184
WellOrdered Sets 186
4.4 Functions 192
Equality 197
Composition 198
Restrictions and Extensions 200
Binary Operations 200
4.5 Injections and Surjections 207
Injections 208
Surjections 211
Bijections 214
Order Isomorphims 215
4.6 Images and Inverse Images 220
5 Axiomatic Set Theory 227
5.1 Axioms 227
Equality Axioms 228
Existence and Uniqueness Axioms 229
Construction Axioms 230
Replacement Axioms 231
Axiom of Choice 232
Axiom of Regularity 236
5.2 Natural Numbers 239
Order 241
Recursion 244
Arithmetic 245
5.3 Integers and Rational Numbers 251
Integers 252
Rational Numbers 255
Actual Numbers 258
5.4 Mathematical Induction 259
Combinatorics 263
Euclid?s Lemma 267
5.5 Strong Induction 270
Fibonacci Sequence 271
Unique Factorization 273
5.6 Real Numbers 277
Dedekind Cuts 278
Arithmetic 280
Complex Numbers 283
6 Ordinals and Cardinals 285
6.1 Ordinal Numbers 285
Ordinals 288
Classification 292
BuraliForti and Hartogs 294
Transfinite Recursion 295
6.2 Equinumerosity 300
Order 302
Diagonalization 305
6.3 Cardinal Numbers 309
Finite Sets 310
Countable Sets 312
Alephs 315
6.4 Arithmetic 318
Ordinals 318
Cardinals 324
6.5 Large Cardinals 330
Regular and Singular Cardinals 331
Inaccessible Cardinals 334
7 Models 337
7.1 FirstOrder
Semantics 337
Satisfaction 339
Groups 344
Consequence 350
Coincidence 352
Rings 357
7.2 Substructures 365
Subgroups 367
Subrings 370
Ideals 372
7.3 Homomorphisms 379
Isomorphisms 384
Elementary Equivalence 388
Elementary Substructures 393
7.4 The Three Properties Revisited 399
Consistency 399
Soundness 402
Completeness 404
7.5 Models of Different Cardinalities 414
Peano Arithmetic 415
Compactness Theorem 419
Löwenheim?Skolem Theorems 420
The von Neumann Hierarchy 422
Appendix: Alphabets 433
References 435
Index 441
Connect: