Tiêu đề Mathematical Foundations 2e.pdf ✅

Mathematical Foundations Justin Lariviere

Contents 1 Mathematical Proofs in The Real Numbers 5 1.1 The Definition of the Real Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Universal Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4 Proving Implications by Direct Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.5 Existential Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.6 Proving Implications by Contraposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.7 Proving Implications by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.8 Proof by Exhaustion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.9 Existential Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 1.10 Universal Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 1.11 The Archimedean Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 1.12 The Lattice Structure of Maxima and Minima (Optional) . . . . . . . . . . . . . . . . . . . . 63 2 Mathematical Proofs in The Integers 71 2.1 The Definition of the Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.2 The Well-Ordering Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 2.3 Proofs Using the Well-Ordering Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 2.4 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 2.5 Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 2.6 Inductive Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 2.7 The Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 2.8 Proofs Using the Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . 105 2.9 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 2.10 The Principle of Complete Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 2.11 Proofs Using the Principle of Complete Induction . . . . . . . . . . . . . . . . . . . . . . . . . 129 2.12 The Embedding of Z in R (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 2.13 The Lattice Structure of Common Multiples (Optional) . . . . . . . . . . . . . . . . . . . . . 142 3 Sets 161 3.1 Subsets and Set Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 3.2 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 3.3 The Lattice Structure of Intersections and Unions . . . . . . . . . . . . . . . . . . . . . . . . 179 3.4 Extended Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 3.5 Families of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 3.6 Operations on Families of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 3.7 The Structure of Real Intervals (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 3.8 The Algebraic Structure of Integer Ideals (Optional) . . . . . . . . . . . . . . . . . . . . . . . 220 3.9 The Lattice Structure of Integer Ideals (Optional) . . . . . . . . . . . . . . . . . . . . . . . . 231 3
4 CONTENTS 4 Relations 245 4.1 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 4.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 4.3 Order Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 4.4 The Lattice Structure of Suprema and Infima (Optional) . . . . . . . . . . . . . . . . . . . . . 283 4.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 4.6 Algebra of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 4.7 Injective and Surjective Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 4.8 The Image and Pre-Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 A Quantifiers 315 B Negation 325 C Boolean Algebra 333 D Set Notation 347