First Course in Mathematical Logic and Set Theory

Michael L. O'Leary, PhD, is Professor of Mathematics at the College of DuPage in Glen Ellyn, Illinois. He received his doctoral degree in mathematics from the University of California, Irvine in 1994 and is the author of Revolutions of Geometry, also published by Wiley.

• Preface xiiiAcknowledgments xvList of Symbols xvii1 Propositional Logic 11.1 Symbolic Logic 1Propositions 2Propositional Forms 5Interpreting Propositional Forms 7Valuations and Truth Tables 101.2 Inference 19Semantics 21Syntactics 231.3 Replacement 31Semantics 31Syntactics 341.4 Proof Methods 40Deduction Theorem 40Direct Proof 44Indirect Proof 471.5 The Three Properties 51Consistency 51Soundness 55Completeness 582 First-Order Logic 632.1 Languages 63Predicates 63Alphabets 67Terms 70Formulas 712.2 Substitution 75Terms 75Free Variables 76Formulas 782.3 Syntactics 85Quantifier Negation 85Proofs with Universal Formulas 87Proofs with Existential Formulas 902.4 Proof Methods 96Universal Proofs 97Existential Proofs 99Multiple Quantifiers 100Counterexamples 102Direct Proof 103Existence and Uniqueness 104Indirect Proof 105Biconditional Proof 107Proof of Disunctions 111Proof by Cases 1123 Set Theory 1173.1 Sets and Elements 117Rosters 118Famous Sets 119Abstraction 1213.2 Set Operations 126Union and Intersection 126Set Difference 127Cartesian Products 130Order of Operations 1323.3 Sets within Sets 135Subsets 135Equality 1373.4 Families of Sets 148Power Set 151Union and Intersection 151Disjoint and Pairwise Disjoint 1554 Relations and Functions 1614.1 Relations 161Composition 163Inverses 1654.2 Equivalence Relations 168Equivalence Classes 171Partitions 1724.3 Partial Orders 177Bounds 180Comparable and Compatible Elements 181Well-OrderedSets 1834.4 Functions 189Equality 194Composition 195Restrictions and Extensions 196Binary Operations 1974.5 Injections and Surjections 203Injections 205Surjections 208Bijections 211Order Isomorphims 2124.6 Images and Inverse Images 2165 Axiomatic Set Theory 2255.1 Axioms 225Equality Axioms 226Existence and Uniqueness Axioms 227Construction Axioms 228Replacement Axioms 229Axiom of Choice 230Axiom of Regularity 2345.2 Natural Numbers 237Order 239Recursion 242Arithmetic 2435.3 Integers and Rational Numbers 249Integers 250Rational Numbers 253Actual Numbers 2565.4 Mathematical Induction 257Combinatorics 260Euclid’s Lemma 2645.5 Strong Induction 268Fibonacci Sequence 268Unique Factorization 2715.6 Real Numbers 274Dedekind Cuts 275Arithmetic 278Complex Numbers 2806 Ordinals and Cardinals 2836.1 Ordinal Numbers 283Ordinals 286Classification 290BuraliForti and Hartogs 292Transfinite Recursion 2936.2 Equinumerosity 298Order 300Diagonalization 3036.3 Cardinal Numbers 307Finite Sets 308Countable Sets 310Alephs 3136.4 Arithmetic 316Ordinals 316Cardinals 3226.5 Large Cardinals 327Regular and Singular Cardinals 328Inaccessible Cardinals 3317 Models 3337.1 First-Order Semantics 333Satisfaction 335Groups 340Consequence 346Coincidence 348Rings 3537.2 Substructures 361Subgroups 363Subrings 366Ideals 3687.3 Homomorphisms 374Isomorphisms 380Elementary Equivalence 384Elementary Substructures 3887.4 The Three Properties Revisited 394Consistency 394Soundness 397Completeness 3997.5 Models of Different Cardinalities 409Peano Arithmetic 410Compactness Theorem 414Löwenheim–Skolem Theorems 415The von Neumann Hierarchy 417Appendix: Alphabets 427References 429Index 435