A First Course in Mathematical Logic and Set Theory

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.  

Table of Contents:
Preface xiii Acknowledgments xv List of Symbols xvii 1 Propositional Logic 1 1.1 Symbolic Logic 1 Propositions 2 Propositional Forms 5 Interpreting Propositional Forms 7 Valuations and Truth Tables 10 1.2 Inference 19 Semantics 21 Syntactics 23 1.3 Replacement 31 Semantics 31 Syntactics 34 1.4 Proof Methods 40 Deduction Theorem 40 Direct Proof 44 Indirect Proof 47 1.5 The Three Properties 51 Consistency 51 Soundness 55 Completeness 58 2 First-Order Logic 63 2.1 Languages 63 Predicates 63 Alphabets 67 Terms 70 Formulas 71 2.2 Substitution 75 Terms 75 Free Variables 76 Formulas 78 2.3 Syntactics 85 Quantifier Negation 85 Proofs with Universal Formulas 87 Proofs with Existential Formulas 90 2.4 Proof Methods 96 Universal Proofs 97 Existential Proofs 99 Multiple Quantifiers 100 Counterexamples 102 Direct Proof 103 Existence and Uniqueness 104 Indirect Proof 105 Biconditional Proof 107 Proof of Disunctions 111 Proof by Cases 112 3 Set Theory 117 3.1 Sets and Elements 117 Rosters 118 Famous Sets 119 Abstraction 121 3.2 Set Operations 126 Union and Intersection 126 Set Difference 127 Cartesian Products 130 Order of Operations 132 3.3 Sets within Sets 135 Subsets 135 Equality 137 3.4 Families of Sets 148 Power Set 151 Union and Intersection 151 Disjoint and Pairwise Disjoint 155 4 Relations and Functions 161 4.1 Relations 161 Composition 163 Inverses 165 4.2 Equivalence Relations 168 Equivalence Classes 171 Partitions 172 4.3 Partial Orders 177 Bounds 180 Comparable and Compatible Elements 181 Well-Ordered Sets 183 4.4 Functions 189 Equality 194 Composition 195 Restrictions and Extensions 196 Binary Operations 197 4.5 Injections and Surjections 203 Injections 205 Surjections 208 Bijections 211 Order Isomorphims 212 4.6 Images and Inverse Images 216 5 Axiomatic Set Theory 225 5.1 Axioms 225 Equality Axioms 226 Existence and Uniqueness Axioms 227 Construction Axioms 228 Replacement Axioms 229 Axiom of Choice 230 Axiom of Regularity 234 5.2 Natural Numbers 237 Order 239 Recursion 242 Arithmetic 243 5.3 Integers and Rational Numbers 249 Integers 250 Rational Numbers 253 Actual Numbers 256 5.4 Mathematical Induction 257 Combinatorics 260 Euclid’s Lemma 264 5.5 Strong Induction 268 Fibonacci Sequence 268 Unique Factorization 271 5.6 Real Numbers 274 Dedekind Cuts 275 Arithmetic 278 Complex Numbers 280 6 Ordinals and Cardinals 283 6.1 Ordinal Numbers 283 Ordinals 286 Classification 290 BuraliForti and Hartogs 292 Transfinite Recursion 293 6.2 Equinumerosity 298 Order 300 Diagonalization 303 6.3 Cardinal Numbers 307 Finite Sets 308 Countable Sets 310 Alephs 313 6.4 Arithmetic 316 Ordinals 316 Cardinals 322 6.5 Large Cardinals 327 Regular and Singular Cardinals 328 Inaccessible Cardinals 331 7 Models 333 7.1 First-Order Semantics 333 Satisfaction 335 Groups 340 Consequence 346 Coincidence 348 Rings 353 7.2 Substructures 361 Subgroups 363 Subrings 366 Ideals 368 7.3 Homomorphisms 374 Isomorphisms 380 Elementary Equivalence 384 Elementary Substructures 388 7.4 The Three Properties Revisited 394 Consistency 394 Soundness 397 Completeness 399 7.5 Models of Different Cardinalities 409 Peano Arithmetic 410 Compactness Theorem 414 Löwenheim–Skolem Theorems 415 The von Neumann Hierarchy 417 Appendix: Alphabets 427 References 429 Index 435