Notes on Discrete Mathematics

1 Notes on Discrete Mathematics James Aspnes 2018-06-26 19:31. i Copyright c 2004 2017 by James Aspnes. Distributed under a Creative Com- mons Attribution-ShareAlike International license: https://creativecommons. org/licenses/by- Contents Table of contents ii List of figures xvii List of tables xix List of algorithms xx Preface xxi Syllabus xxii Resources xxvi Internet resources xxvii Lecture schedule xxviii 1 Introduction 1. So why do I need to learn all this nasty Mathematics ? .. 1. But isn't math hard? .. 2. Thinking about math with your heart .. 3. What you should know about math.

2 3. Foundations and logic .. 4. Basic Mathematics on the real numbers .. 4. Fundamental mathematical objects .. 5. Modular arithmetic and polynomials .. 6. Linear algebra .. 6. Graphs .. 6. Counting .. 7. Probability .. 7. ii CONTENTS iii Tools .. 8. 2 Mathematical logic 9. The basic picture .. 9. Axioms, models, and inference rules .. 9. Consistency .. 10. What can go wrong .. 10. The language of logic .. 11. Standard axiom systems and models .. 11. Propositional logic .. 12. Operations on propositions .. 13. Precedence .. 15. Truth tables .. 16. Tautologies and logical equivalence.

3 17. Inverses, converses, and contrapositives .. 21. Equivalences involving true and false .. 21. Example .. 22. Normal forms .. 23. Predicate logic .. 25. Variables and predicates .. 26. Quantifiers .. 27. Universal quantifier .. 27. Existential quantifier .. 27. Negation and quantifiers .. 28. Restricting the scope of a quantifier .. 28. Nested quantifiers .. 29. Examples .. 31. Functions .. 32. Equality .. 33. Uniqueness .. 33. Models .. 34. Examples .. 34. Proofs .. 35. Inference Rules .. 36. Proofs, implication, and natural deduction .. 38. The Deduction Theorem.

4 39. Natural deduction .. 40. Inference rules for equality .. 40. Inference rules for quantified statements .. 42. Proof techniques .. 43. CONTENTS iv Examples of proofs .. 47. Axioms for even numbers .. 47. A theorem and its proof .. 48. A more general theorem .. 50. Something we can't prove .. 51. 3 Set theory 52. Naive set theory .. 52. Operations on sets .. 54. Proving things about sets .. 55. Axiomatic set theory .. 57. Cartesian products, relations, and functions .. 59. Examples of functions .. 61. Sequences .. 61. Functions of more (or less) than one argument.

5 62. Composition of functions .. 62. Functions with special properties .. 62. Surjections .. 63. Injections .. 63. Bijections .. 63. Bijections and counting .. 63. Constructing the universe .. 64. Sizes and arithmetic .. 66. Infinite sets .. 66. Countable sets .. 68. Uncountable sets .. 68. Further reading .. 69. 4 The real numbers 70. Field axioms .. 71. Axioms for addition .. 71. Axioms for multiplication .. 72. Axioms relating multiplication and addition .. 74. Other algebras satisfying the field axioms .. 75. Order axioms .. 76. Least upper bounds .. 77. What's missing: algebraic closure.

6 79. Arithmetic .. 79. Connection between the reals and other standard algebras .. 80. Extracting information from reals .. 82. CONTENTS v 5 Induction and recursion 83. Simple induction .. 83. Alternative base cases .. 85. Recursive definitions work .. 86. Other ways to think about induction .. 86. Strong induction .. 87. Examples .. 88. Recursively-defined structures .. 89. Functions on recursive structures .. 90. Recursive definitions and induction .. 90. Structural induction .. 91. 6 Summation notation 92. Summations .. 92. Formal definition .. 93. Scope .. 94. Summation identities.

7 95. Choosing and replacing index variables .. 96. Sums over given index sets .. 97. Sums without explicit bounds .. 98. Infinite sums .. 98. Double sums .. 99. Products .. 99. Other big operators .. 100. Closed forms .. 101. Some standard sums .. 101. Guess but verify .. 103. Ansatzes .. 103. 7 Asymptotic notation 105. Definitions .. 105. Motivating the definitions .. 105. Proving asymptotic bounds .. 106. General principles for dealing with asymptotic notation .. 107. Remember the difference between big-O, big- , and big- .. 107. Simplify your asymptotic terms as much as possible.

8 108. Use limits (may require calculus) .. 108. Asymptotic notation and summations .. 109. Pull out constant factors .. 109. CONTENTS vi Bound using a known sum .. 109. Geometric series .. 109. Constant series .. 110. Arithmetic series .. 110. Harmonic series .. 110. Bound part of the sum .. 111. Integrate .. 111. Grouping terms .. 111. An odd sum .. 111. Final Notes .. 112. Variations in notation .. 112. Absolute values .. 112. Abusing the equals sign .. 112. 8 Number theory 114. Divisibility .. 115. The division algorithm .. 115. Modular arithmetic and residue classes.

9 117. Arithmetic on residue classes .. 117. Greatest common divisors .. 119. The Euclidean algorithm for computing gcd(m, n) .. 120. The extended Euclidean algorithm .. 120. Example .. 121. Applications .. 121. The Fundamental Theorem of Arithmetic .. 123. Unique factorization and gcd .. 124. More modular arithmetic .. 124. Division in Zm .. 124. The Chinese Remainder Theorem .. 126. The size of Z m and Euler's Theorem .. 128. RSA encryption .. 129. 9 Relations 132. Representing relations .. 132. Directed graphs .. 132. Matrices .. 133. Operations on relations .. 134.

10 Composition .. 134. Inverses .. 135. Classifying relations .. 135. CONTENTS vii Equivalence relations .. 136. Why we like equivalence relations .. 138. Partial orders .. 138. Drawing partial orders .. 140. Comparability .. 140. Lattices .. 141. Minimal and maximal elements .. 142. Total orders .. 143. Topological sort .. 143. Well orders .. 146. Closures .. 148. Examples .. 150. 10 Graphs 152. Types of graphs .. 153. Directed graphs .. 153. Undirected graphs .. 153. Hypergraphs .. 154. Examples of graphs .. 155. Local structure of graphs .. 156. Some standard graphs.