Notes on Discrete Mathematics James Aspnes 2017-10-01 23:53 i Copyright(cid:13)c 2004–2017byJamesAspnes. DistributedunderaCreativeCom- monsAttribution-ShareAlike4.0Internationallicense: https://creativecommons. org/licenses/by-sa/4.0/. Contents Table of contents ii List of figures xvi List of tables xvii List of algorithms xviii Preface xix Syllabus xx Resources xxiv Internet resources xxv Lecture schedule xxvi 1 Introduction 1 1.1 So why do I need to learn all this nasty mathematics? . . . . 1 1.2 But isn’t math hard? . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Thinking about math with your heart . . . . . . . . . . . . . 3 1.4 What you should know about math . . . . . . . . . . . . . . . 3 1.4.1 Foundations and logic . . . . . . . . . . . . . . . . . . 4 1.4.2 Basic mathematics on the real numbers . . . . . . . . 4 1.4.3 Fundamental mathematical objects . . . . . . . . . . . 5 1.4.4 Modular arithmetic and polynomials . . . . . . . . . . 6 1.4.5 Linear algebra . . . . . . . . . . . . . . . . . . . . . . 6 1.4.6 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4.7 Counting . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4.8 Probability . . . . . . . . . . . . . . . . . . . . . . . . 7 ii CONTENTS iii 1.4.9 Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Mathematical logic 9 2.1 The basic picture . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Axioms, models, and inference rules . . . . . . . . . . 9 2.1.2 Consistency . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.3 What can go wrong . . . . . . . . . . . . . . . . . . . 10 2.1.4 The language of logic . . . . . . . . . . . . . . . . . . 11 2.1.5 Standard axiom systems and models . . . . . . . . . . 11 2.2 Propositional logic . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Operations on propositions . . . . . . . . . . . . . . . 13 2.2.1.1 Precedence . . . . . . . . . . . . . . . . . . . 15 2.2.2 Truth tables. . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.3 Tautologies and logical equivalence . . . . . . . . . . . 17 2.2.3.1 Inverses, converses, and contrapositives . . . 19 2.2.3.2 Equivalences involving true and false . . . . 21 Example . . . . . . . . . . . . . . . . . . . . . . 22 2.2.4 Normal forms . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Predicate logic . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.1 Variables and predicates . . . . . . . . . . . . . . . . . 25 2.3.2 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.2.1 Universal quantifier . . . . . . . . . . . . . . 26 2.3.2.2 Existential quantifier . . . . . . . . . . . . . 27 2.3.2.3 Negation and quantifiers . . . . . . . . . . . 27 2.3.2.4 Restricting the scope of a quantifier . . . . . 28 2.3.2.5 Nested quantifiers . . . . . . . . . . . . . . . 29 2.3.2.6 Examples . . . . . . . . . . . . . . . . . . . . 31 2.3.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.4 Equality . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.4.1 Uniqueness . . . . . . . . . . . . . . . . . . . 33 2.3.5 Models . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.5.1 Examples . . . . . . . . . . . . . . . . . . . . 34 2.4 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.1 Inference Rules . . . . . . . . . . . . . . . . . . . . . . 36 2.4.2 Proofs, implication, and natural deduction . . . . . . . 38 2.4.2.1 The Deduction Theorem . . . . . . . . . . . 39 2.4.2.2 Natural deduction . . . . . . . . . . . . . . . 39 2.4.3 Inference rules for equality . . . . . . . . . . . . . . . 40 2.4.4 Inference rules for quantified statements . . . . . . . . 42 2.5 Proof techniques . . . . . . . . . . . . . . . . . . . . . . . . . 44 CONTENTS iv 2.6 Examples of proofs . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6.1 Axioms for even numbers . . . . . . . . . . . . . . . . 47 2.6.2 A theorem and its proof . . . . . . . . . . . . . . . . . 48 2.6.3 A more general theorem . . . . . . . . . . . . . . . . . 50 2.6.4 Something we can’t prove . . . . . . . . . . . . . . . . 51 3 Set theory 52 3.1 Naive set theory . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3 Proving things about sets . . . . . . . . . . . . . . . . . . . . 55 3.4 Axiomatic set theory . . . . . . . . . . . . . . . . . . . . . . . 57 3.5 Cartesian products, relations, and functions . . . . . . . . . . 59 3.5.1 Examples of functions . . . . . . . . . . . . . . . . . . 61 3.5.2 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.5.3 Functions of more (or less) than one argument . . . . 62 3.5.4 Composition of functions . . . . . . . . . . . . . . . . 62 3.5.5 Functions with special properties . . . . . . . . . . . . 62 3.5.5.1 Surjections . . . . . . . . . . . . . . . . . . . 63 3.5.5.2 Injections . . . . . . . . . . . . . . . . . . . . 63 3.5.5.3 Bijections . . . . . . . . . . . . . . . . . . . . 63 3.5.5.4 Bijections and counting . . . . . . . . . . . . 64 3.6 Constructing the universe . . . . . . . . . . . . . . . . . . . . 64 3.7 Sizes and arithmetic . . . . . . . . . . . . . . . . . . . . . . . 66 3.7.1 Infinite sets . . . . . . . . . . . . . . . . . . . . . . . . 66 3.7.2 Countable sets . . . . . . . . . . . . . . . . . . . . . . 68 3.7.3 Uncountable sets . . . . . . . . . . . . . . . . . . . . . 68 3.8 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4 The real numbers 70 4.1 Field axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.1.1 Axioms for addition . . . . . . . . . . . . . . . . . . . 71 4.1.2 Axioms for multiplication . . . . . . . . . . . . . . . . 72 4.1.3 Axioms relating multiplication and addition . . . . . . 74 4.1.4 Other algebras satisfying the field axioms . . . . . . . 75 4.2 Order axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.3 Least upper bounds . . . . . . . . . . . . . . . . . . . . . . . 77 4.4 What’s missing: algebraic closure . . . . . . . . . . . . . . . . 79 4.5 Arithmetic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.6 Connection between the reals and other standard algebras . . 80 4.7 Extracting information from reals . . . . . . . . . . . . . . . . 82 CONTENTS v 5 Induction and recursion 83 5.1 Simple induction . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2 Alternative base cases . . . . . . . . . . . . . . . . . . . . . . 85 5.3 Recursive definitions work . . . . . . . . . . . . . . . . . . . . 86 5.4 Other ways to think about induction . . . . . . . . . . . . . . 86 5.5 Strong induction . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.5.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.6 Recursively-defined structures . . . . . . . . . . . . . . . . . . 89 5.6.1 Functions on recursive structures . . . . . . . . . . . . 90 5.6.2 Recursive definitions and induction . . . . . . . . . . . 90 5.6.3 Structural induction . . . . . . . . . . . . . . . . . . . 91 6 Summation notation 92 6.1 Summations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.1.1 Formal definition . . . . . . . . . . . . . . . . . . . . . 93 6.1.2 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.1.3 Summation identities. . . . . . . . . . . . . . . . . . . 93 6.1.4 Choosing and replacing index variables. . . . . . . . . 95 6.1.5 Sums over given index sets . . . . . . . . . . . . . . . 95 6.1.6 Sums without explicit bounds . . . . . . . . . . . . . . 97 6.1.7 Infinite sums . . . . . . . . . . . . . . . . . . . . . . . 97 6.1.8 Double sums . . . . . . . . . . . . . . . . . . . . . . . 97 6.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.3 Other big operators . . . . . . . . . . . . . . . . . . . . . . . 98 6.4 Closed forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.4.1 Some standard sums . . . . . . . . . . . . . . . . . . . 100 6.4.2 Guess but verify . . . . . . . . . . . . . . . . . . . . . 101 6.4.3 Ansatzes. . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.4.4 Strategies for asymptotic estimates . . . . . . . . . . . 103 6.4.4.1 Pull out constant factors . . . . . . . . . . . 103 6.4.4.2 Bound using a known sum . . . . . . . . . . 103 Geometric series . . . . . . . . . . . . . . . . . 104 Constant series . . . . . . . . . . . . . . . . . . 104 Arithmetic series . . . . . . . . . . . . . . . . . 104 Harmonic series . . . . . . . . . . . . . . . . . . 104 6.4.4.3 Bound part of the sum . . . . . . . . . . . . 104 6.4.4.4 Integrate . . . . . . . . . . . . . . . . . . . . 104 6.4.4.5 Grouping terms . . . . . . . . . . . . . . . . 105 6.4.4.6 Oddities. . . . . . . . . . . . . . . . . . . . . 105 6.4.4.7 Final notes . . . . . . . . . . . . . . . . . . . 105 CONTENTS vi 7 Asymptotic notation 106 7.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.2 Motivating the definitions . . . . . . . . . . . . . . . . . . . . 106 7.3 Proving asymptotic bounds . . . . . . . . . . . . . . . . . . . 107 7.4 Asymptotic notation hints . . . . . . . . . . . . . . . . . . . . 108 7.4.1 Remember the difference between big-O, big-Ω, and big-Θ . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 7.4.2 Simplify your asymptotic terms as much as possible . 109 7.4.3 Remember the limit trick . . . . . . . . . . . . . . . . 109 7.5 Variations in notation . . . . . . . . . . . . . . . . . . . . . . 109 7.5.1 Absolute values . . . . . . . . . . . . . . . . . . . . . . 110 7.5.2 Abusing the equals sign . . . . . . . . . . . . . . . . . 110 8 Number theory 112 8.1 Divisibility and division . . . . . . . . . . . . . . . . . . . . . 112 8.2 Greatest common divisors . . . . . . . . . . . . . . . . . . . . 114 8.2.1 The Euclidean algorithm for computing gcd(m,n) . . 114 8.2.2 The extended Euclidean algorithm . . . . . . . . . . . 115 8.2.2.1 Example . . . . . . . . . . . . . . . . . . . . 115 8.2.2.2 Applications . . . . . . . . . . . . . . . . . . 115 8.3 The Fundamental Theorem of Arithmetic . . . . . . . . . . . 118 8.3.1 Applications . . . . . . . . . . . . . . . . . . . . . . . 118 8.4 Modular arithmetic and residue classes . . . . . . . . . . . . . 119 8.4.1 Arithmetic on residue classes . . . . . . . . . . . . . . 120 8.4.2 Division in Z . . . . . . . . . . . . . . . . . . . . . . 121 m 8.4.3 The Chinese Remainder Theorem . . . . . . . . . . . . 122 8.4.4 The size of Z∗ and Euler’s Theorem . . . . . . . . . . 125 m 8.5 RSA encryption . . . . . . . . . . . . . . . . . . . . . . . . . . 125 9 Relations 128 9.1 Representing relations . . . . . . . . . . . . . . . . . . . . . . 128 9.1.1 Directed graphs . . . . . . . . . . . . . . . . . . . . . . 128 9.1.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 129 9.2 Operations on relations . . . . . . . . . . . . . . . . . . . . . 130 9.2.1 Composition . . . . . . . . . . . . . . . . . . . . . . . 130 9.2.2 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . 131 9.3 Classifying relations . . . . . . . . . . . . . . . . . . . . . . . 131 9.4 Equivalence relations . . . . . . . . . . . . . . . . . . . . . . . 131 9.4.1 Why we like equivalence relations . . . . . . . . . . . . 134 9.5 Partial orders . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 CONTENTS vii 9.5.1 Drawing partial orders . . . . . . . . . . . . . . . . . . 136 9.5.2 Comparability . . . . . . . . . . . . . . . . . . . . . . 136 9.5.3 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9.5.4 Minimal and maximal elements . . . . . . . . . . . . . 137 9.5.5 Total orders . . . . . . . . . . . . . . . . . . . . . . . . 138 9.5.5.1 Topological sort . . . . . . . . . . . . . . . . 138 9.5.6 Well orders . . . . . . . . . . . . . . . . . . . . . . . . 141 9.6 Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 9.6.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 144 10 Graphs 146 10.1 Types of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 147 10.1.1 Directed graphs . . . . . . . . . . . . . . . . . . . . . . 147 10.1.2 Undirected graphs . . . . . . . . . . . . . . . . . . . . 147 10.1.3 Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 148 10.2 Examples of graphs . . . . . . . . . . . . . . . . . . . . . . . . 149 10.3 Local structure of graphs . . . . . . . . . . . . . . . . . . . . 150 10.4 Some standard graphs . . . . . . . . . . . . . . . . . . . . . . 150 10.5 Subgraphs and minors . . . . . . . . . . . . . . . . . . . . . . 155 10.6 Graph products . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.6.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . 157 10.7 Paths and connectivity . . . . . . . . . . . . . . . . . . . . . . 158 10.8 Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 10.9 Proving things about graphs . . . . . . . . . . . . . . . . . . . 161 10.9.1 Paths and simple paths . . . . . . . . . . . . . . . . . 162 10.9.2 The Handshaking Lemma . . . . . . . . . . . . . . . . 162 10.9.3 Characterizations of trees . . . . . . . . . . . . . . . . 163 10.9.4 Spanning trees . . . . . . . . . . . . . . . . . . . . . . 166 10.9.5 Eulerian cycles . . . . . . . . . . . . . . . . . . . . . . 167 11 Counting 168 11.1 Basic counting techniques . . . . . . . . . . . . . . . . . . . . 169 11.1.1 Equality: reducing to a previously-solved case . . . . . 169 11.1.2 Inequalities: showing |A| ≤ |B| and |B| ≤ |A| . . . . . 169 11.1.3 Addition: the sum rule . . . . . . . . . . . . . . . . . . 170 11.1.3.1 For infinite sets . . . . . . . . . . . . . . . . 171 11.1.3.2 The Pigeonhole Principle . . . . . . . . . . . 171 11.1.4 Subtraction . . . . . . . . . . . . . . . . . . . . . . . . 172 11.1.4.1 Inclusion-exclusion for infinite sets . . . . . . 172 11.1.4.2 Combinatorial proof . . . . . . . . . . . . . . 172 CONTENTS viii 11.1.5 Multiplication: the product rule . . . . . . . . . . . . 173 11.1.5.1 Examples . . . . . . . . . . . . . . . . . . . . 174 11.1.5.2 For infinite sets . . . . . . . . . . . . . . . . 174 11.1.6 Exponentiation: the exponent rule . . . . . . . . . . . 174 11.1.6.1 Counting injections . . . . . . . . . . . . . . 175 11.1.7 Division: counting the same thing in two different ways176 11.1.8 Applying the rules . . . . . . . . . . . . . . . . . . . . 178 11.1.9 An elaborate counting problem . . . . . . . . . . . . . 180 11.1.10Further reading . . . . . . . . . . . . . . . . . . . . . . 182 11.2 Binomial coefficients . . . . . . . . . . . . . . . . . . . . . . . 182 11.2.1 Recursive definition . . . . . . . . . . . . . . . . . . . 183 11.2.1.1 Pascal’s identity: algebraic proof . . . . . . . 184 11.2.2 Vandermonde’s identity . . . . . . . . . . . . . . . . . 185 11.2.2.1 Combinatorial proof . . . . . . . . . . . . . . 185 11.2.2.2 Algebraic proof . . . . . . . . . . . . . . . . . 186 11.2.3 Sums of binomial coefficients . . . . . . . . . . . . . . 186 11.2.4 The general inclusion-exclusion formula . . . . . . . . 187 11.2.5 Negative binomial coefficients . . . . . . . . . . . . . . 188 11.2.6 Fractional binomial coefficients . . . . . . . . . . . . . 189 11.2.7 Further reading . . . . . . . . . . . . . . . . . . . . . . 189 11.3 Generating functions . . . . . . . . . . . . . . . . . . . . . . . 189 11.3.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 11.3.1.1 A simple example . . . . . . . . . . . . . . . 189 11.3.1.2 Why this works . . . . . . . . . . . . . . . . 190 11.3.1.3 Formal definition . . . . . . . . . . . . . . . . 191 11.3.2 Some standard generating functions . . . . . . . . . . 194 11.3.3 More operations on formal power series and generating functions . . . . . . . . . . . . . . . . . . . . . . . . . 194 11.3.4 Counting with generating functions . . . . . . . . . . . 195 11.3.4.1 Disjoint union . . . . . . . . . . . . . . . . . 195 11.3.4.2 Cartesian product . . . . . . . . . . . . . . . 196 11.3.4.3 Repetition . . . . . . . . . . . . . . . . . . . 196 Example: (0|11)∗ . . . . . . . . . . . . . . . . . 196 Example: sequences of positive integers . . . . 196 11.3.4.4 Pointing . . . . . . . . . . . . . . . . . . . . 198 11.3.4.5 Substitution . . . . . . . . . . . . . . . . . . 198 Example: bit-strings with primes . . . . . . . . 199 Example: (0|11)* again . . . . . . . . . . . . . 199 11.3.5 Generating functions and recurrences . . . . . . . . . 199 11.3.5.1 Example: A Fibonacci-like recurrence . . . . 200 CONTENTS ix 11.3.6 Recovering coefficients from generating functions . . . 200 11.3.6.1 Partial fraction expansion and Heaviside’s cover-up method . . . . . . . . . . . . . . . . 202 Example: A simple recurrence . . . . . . . . . . 202 Example: Coughing cows . . . . . . . . . . . . 203 Example: A messy recurrence . . . . . . . . . . 204 11.3.6.2 Partial fraction expansion with repeated roots206 Solving for the PFE directly . . . . . . . . . . . 206 SolvingforthePFEusingtheextendedcover-up method . . . . . . . . . . . . . . . . 208 11.3.7 Asymptotic estimates . . . . . . . . . . . . . . . . . . 209 11.3.8 Recovering the sum of all coefficients . . . . . . . . . . 210 11.3.8.1 Example . . . . . . . . . . . . . . . . . . . . 210 11.3.9 A recursive generating function . . . . . . . . . . . . . 211 11.3.10Summary of operations on generating functions . . . . 214 11.3.11Variants . . . . . . . . . . . . . . . . . . . . . . . . . . 215 11.3.12Further reading . . . . . . . . . . . . . . . . . . . . . . 215 12 Probability theory 216 12.1 Events and probabilities . . . . . . . . . . . . . . . . . . . . . 217 12.1.1 Probability axioms . . . . . . . . . . . . . . . . . . . . 217 12.1.1.1 The Kolmogorov axioms. . . . . . . . . . . . 218 12.1.1.2 Examples of probability spaces . . . . . . . . 219 12.1.2 Probability as counting . . . . . . . . . . . . . . . . . 219 12.1.2.1 Examples . . . . . . . . . . . . . . . . . . . . 220 12.1.3 Independence and the intersection of two events . . . 220 12.1.3.1 Examples . . . . . . . . . . . . . . . . . . . . 221 12.1.4 Union of events . . . . . . . . . . . . . . . . . . . . . . 222 12.1.4.1 Examples . . . . . . . . . . . . . . . . . . . . 222 12.1.5 Conditional probability . . . . . . . . . . . . . . . . . 223 12.1.5.1 Conditional probabilities and intersections of non-independent events . . . . . . . . . . . . 223 12.1.5.2 The law of total probability . . . . . . . . . . 224 12.1.5.3 Bayes’s formula . . . . . . . . . . . . . . . . 224 12.2 Random variables . . . . . . . . . . . . . . . . . . . . . . . . . 225 12.2.1 Examples of random variables . . . . . . . . . . . . . . 225 12.2.2 The distribution of a random variable . . . . . . . . . 226 12.2.2.1 Some standard distributions . . . . . . . . . 226 12.2.2.2 Joint distributions . . . . . . . . . . . . . . . 228 Examples . . . . . . . . . . . . . . . . . . . . . 228