WIXLIB

Notes on Discrete MathematicsJames Aspnes2020-12-31 18:58

iCopyright c 2004–2020 by James Aspnes. Distributed under a Creative Commons Attribution-ShareAlike 4.0 International license: https://creativecommons.org/licenses/by-sa/4.0/.

ContentsTable of contentsiiList of figuresxviiList of tablesxixList of algorithmsxxPrefacexxiResourcesxxii1 Introduction1.1 So why do I need to learn all this nasty mathematics?1.2 But isn’t math hard? . . . . . . . . . . . . . . . . . . .1.3 Thinking about math with your heart . . . . . . . . .1.4 What you should know about math . . . . . . . . . . .1.4.1 Foundations and logic . . . . . . . . . . . . . .1.4.2 Basic mathematics on the real numbers . . . .1.4.3 Fundamental mathematical objects . . . . . . .1.4.4 Modular arithmetic and polynomials . . . . . .1.4.5 Linear algebra . . . . . . . . . . . . . . . . . .1.4.6 Graphs . . . . . . . . . . . . . . . . . . . . . .1.4.7 Counting . . . . . . . . . . . . . . . . . . . . .1.4.8 Probability . . . . . . . . . . . . . . . . . . . .1.4.9 Tools . . . . . . . . . . . . . . . . . . . . . . .112334456667782 Mathematical logic2.1 The basic picture . . . . . . . . . . . . . . . . . . . . . . . . .2.1.1 Axioms, models, and inference rules . . . . . . . . . .999ii.

CONTENTS2.22.32.42.52.62.1.2 Consistency . . . . . . . . . . . . . . . . . . . . .2.1.3 What can go wrong . . . . . . . . . . . . . . . .2.1.4 The language of logic . . . . . . . . . . . . . . .2.1.5 Standard axiom systems and models . . . . . . .Propositional logic . . . . . . . . . . . . . . . . . . . . .2.2.1 Operations on propositions . . . . . . . . . . . .2.2.1.1 Precedence . . . . . . . . . . . . . . . .2.2.2 Truth tables . . . . . . . . . . . . . . . . . . . . .2.2.3 Tautologies and logical equivalence . . . . . . . .2.2.3.1 Inverses, converses, and contrapositives2.2.3.2 Equivalences involving true and false .Example . . . . . . . . . . . . . . . . . . .2.2.4 Normal forms . . . . . . . . . . . . . . . . . . . .Predicate logic . . . . . . . . . . . . . . . . . . . . . . .2.3.1 Variables and predicates . . . . . . . . . . . . . .2.3.2 Quantifiers . . . . . . . . . . . . . . . . . . . . .2.3.2.1 Universal quantifier . . . . . . . . . . .2.3.2.2 Existential quantifier . . . . . . . . . .2.3.2.3 Negation and quantifiers . . . . . . . .2.3.2.4 Restricting the scope of a quantifier . .2.3.2.5 Nested quantifiers . . . . . . . . . . . .2.3.2.6 Examples . . . . . . . . . . . . . . . . .2.3.3 Functions . . . . . . . . . . . . . . . . . . . . . .2.3.4 Equality . . . . . . . . . . . . . . . . . . . . . . .2.3.4.1 Uniqueness . . . . . . . . . . . . . . . .2.3.5 Models . . . . . . . . . . . . . . . . . . . . . . .2.3.5.1 Examples . . . . . . . . . . . . . . . . .Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.1 Inference Rules . . . . . . . . . . . . . . . . . . .2.4.2 Proofs, implication, and natural deduction . . . .2.4.2.1 The Deduction Theorem . . . . . . . .2.4.2.2 Natural deduction . . . . . . . . . . . .2.4.3 Inference rules for equality . . . . . . . . . . . .2.4.4 Inference rules for quantified statements . . . . .Proof techniques . . . . . . . . . . . . . . . . . . . . . .Examples of proofs . . . . . . . . . . . . . . . . . . . . .2.6.1 Axioms for even numbers . . . . . . . . . . . . .2.6.2 A theorem and its proof . . . . . . . . . . . . . .2.6.3 A more general theorem . . . . . . . . . . . . . .2.6.4 Something we can’t prove . . . . . . . . . . . . 23333343435363839404042434747485051

CONTENTSiv3 Set3.13.23.33.43.5theoryNaive set theory . . . . . . . . . . . . . . . . . . . . .Operations on sets . . . . . . . . . . . . . . . . . . . .Proving things about sets . . . . . . . . . . . . . . . .Axiomatic set theory . . . . . . . . . . . . . . . . . . .Cartesian products, relations, and functions . . . . . .3.5.1 Examples of functions . . . . . . . . . . . . . .3.5.2 Sequences . . . . . . . . . . . . . . . . . . . . .3.5.3 Functions of more (or less) than one argument3.5.4 Composition of functions . . . . . . . . . . . .3.5.5 Functions with special properties . . . . . . . .3.5.5.1 Surjections . . . . . . . . . . . . . . .3.5.5.2 Injections . . . . . . . . . . . . . . . .3.5.5.3 Bijections . . . . . . . . . . . . . . . .3.5.5.4 Bijections and counting . . . . . . . .3.6 Constructing the universe . . . . . . . . . . . . . . . .3.7 Sizes and arithmetic . . . . . . . . . . . . . . . . . . .3.7.1 Infinite sets . . . . . . . . . . . . . . . . . . . .3.7.2 Countable sets . . . . . . . . . . . . . . . . . .3.7.3 Uncountable sets . . . . . . . . . . . . . . . . .3.8 Further reading . . . . . . . . . . . . . . . . . . . . . .5252545557596161626262636363636466666868694 The real numbers4.1 Field axioms . . . . . . . . . . . . . . . . . . . . . . . . .4.1.1 Axioms for addition . . . . . . . . . . . . . . . . .4.1.2 Axioms for multiplication . . . . . . . . . . . . . .4.1.3 Axioms relating multiplication and addition . . . .4.1.4 Other algebras satisfying the field axioms . . . . .4.2 Order axioms . . . . . . . . . . . . . . . . . . . . . . . . .4.3 Least upper bounds . . . . . . . . . . . . . . . . . . . . .4.4 What’s missing: algebraic closure . . . . . . . . . . . . . .4.5 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . .4.6 Connection between the reals and other standard algebras4.7 Extracting information from reals . . . . . . . . . . . . . .707171727475767779798082.83838586865 Induction and recursion5.1 Simple induction . . . . .5.2 Alternative base cases . .5.3 Recursive definitions work5.4 Other ways to think about. . . . . . . . . . . . . . . .induction.

CONTENTS5.55.6Strong induction . . . . . . . . . . . . . .5.5.1 Examples . . . . . . . . . . . . . .Recursively-defined structures . . . . . . .5.6.1 Functions on recursive structures .5.6.2 Recursive definitions and induction5.6.3 Structural induction . . . . . . . .v.6 Summation notation6.1 Summations . . . . . . . . . . . . . . . . . . . .6.1.1 Formal definition . . . . . . . . . . . . .6.1.2 Scope . . . . . . . . . . . . . . . . . . .6.1.3 Summation identities . . . . . . . . . . .6.1.4 Choosing and replacing index variables .6.1.5 Sums over given index sets . . . . . . .6.1.6 Sums without explicit bounds . . . . . .6.1.7 Infinite sums . . . . . . . . . . . . . . .6.1.8 Double sums . . . . . . . . . . . . . . .6.2 Products . . . . . . . . . . . . . . . . . . . . . .6.3 Other big operators . . . . . . . . . . . . . . .6.4 Closed forms . . . . . . . . . . . . . . . . . . .6.4.1 Some standard sums . . . . . . . . . . .6.4.2 Guess but verify . . . . . . . . . . . . .6.4.3 Ansatzes . . . . . . . . . . . . . . . . . 37 Asymptotic notation7.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.2 Motivating the definitions . . . . . . . . . . . . . . . . . . . .7.3 Proving asymptotic bounds . . . . . . . . . . . . . . . . . . .7.4 General principles for dealing with asymptotic notation . . .7.4.1 Remember the difference between big-O, big-Ω, andbig-Θ . . . . . . . . . . . . . . . . . . . . . . . . . . .7.4.2 Simplify your asymptotic terms as much as possible .7.4.3 Use limits (may require calculus) . . . . . . . . . . . .7.5 Asymptotic notation and summations . . . . . . . . . . . . .7.5.1 Pull out constant factors . . . . . . . . . . . . . . . . .7.5.2 Bound using a known sum . . . . . . . . . . . . . . . .7.5.2.1 Geometric series . . . . . . . . . . . . . . . .7.5.2.2 Constant series . . . . . . . . . . . . . . . . .7.5.2.3 Arithmetic series . . . . . . . . . . . . . . . .7.5.2.4 Harmonic series . . . . . . . . . . . . . . . .105105105106107107108108109109109109110110110

CONTENTS.1111111111111121121121128 Number theory8.1 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . .8.2 The division algorithm . . . . . . . . . . . . . . . . . . . .8.3 Modular arithmetic and residue classes . . . . . . . . . . .8.3.1 Arithmetic on residue classes . . . . . . . . . . . .8.4 Greatest common divisors . . . . . . . . . . . . . . . . . .8.4.1 The Euclidean algorithm for computing gcd(m, n)8.4.2 The extended Euclidean algorithm . . . . . . . . .8.4.2.1 Example . . . . . . . . . . . . . . . . . .8.4.2.2 Applications . . . . . . . . . . . . . . . .8.5 The Fundamental Theorem of Arithmetic . . . . . . . . .8.5.1 Unique factorization and gcd . . . . . . . . . . . .8.6 More modular arithmetic . . . . . . . . . . . . . . . . . .8.6.1 Division in Zm . . . . . . . . . . . . . . . . . . . .8.6.2 The Chinese Remainder Theorem . . . . . . . . . .8.6.3 The size of Z m and Euler’s Theorem . . . . . . . .8.7 RSA encryption . . . . . . . . . . . . . . . . . . . . . . . 29.1321321321331341341351351361381381401407.67.5.3 Bound part of the sum .7.5.4 Integrate . . . . . . . .7.5.5 Grouping terms . . . . .7.5.6 An odd sum . . . . . . .7.5.7 Final notes . . . . . . .Variations in notation . . . . .7.6.1 Absolute values . . . . .7.6.2 Abusing the equals signvi9 Relations9.1 Representing relations . . . . .9.1.1 Directed graphs . . . . .9.1.2 Matrices . . . . . . . . .9.2 Operations on relations . . . .9.2.1 Composition . . . . . .9.2.2 Inverses . . . . . . . . .9.3 Classifying relations . . . . . .9.4 Equivalence relations . . . . . .9.4.1 Why we like equivalence9.5 Partial orders . . . . . . . . . .9.5.1 Drawing partial orders .9.5.2 Comparability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .relations . . . . . . . . . . . . . . . .

17217211 Counting11.1 Basic counting techniques . . . . . . . . . . . . . . .11.1.1 Equality: reducing to a previously-solved case11.1.2 Inequalities: showing A B and B A 11.1.3 Addition: the sum rule . . . . . . . . . . . . .11.1.3.1 For infinite sets . . . . . . . . . . .11.1.3.2 The Pigeonhole Principle . . . . . .11.1.4 Subtraction . . . . . . . . . . . . . . . . . . .11.1.4.1 Inclusion-exclusion for infinite sets .11.1.4.2 Combinatorial proof . . . . . . . . .11.1.5 Multiplication: the product rule . . . . . . .11.1.5.1 Examples . . . . . . . . . . . . . . .1741751751751761771771781781791791809.6Lattices . . . . . . . . . . . . .Minimal and maximal elementsTotal orders . . . . . . . . . . .9.5.5.1 Topological sort . . .9.5.6 Well orders . . . . . . . . . . .Closures . . . . . . . . . . . . . . . . .9.6.1 Examples . . . . . . . . . . . .10 Graphs10.1 Types of graphs . . . . . . . . . .10.1.1 Directed graphs . . . . . .10.1.2 Undirected graphs . . . .10.1.3 Hypergraphs . . . . . . .10.2 Examples of graphs . . . . . . . .10.3 Local structure of graphs . . . .10.4 Some standard graphs . . . . . .10.5 Subgraphs and minors . . . . . .10.6 Graph products . . . . . . . . . .10.7 Functions between graphs . . . .10.8 Paths and connectivity . . . . . .10.9 Cycles . . . . . . . . . . . . . . .10.10Proving things about graphs . . .10.10.1 Paths and simple paths .10.10.2 The Handshaking Lemma10.10.3 Characterizations of trees10.10.4 Spanning trees . . . . . .10.10.5 Eulerian cycles . . . . . .