A First Course in Mathematical Logic and Set Theory

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