Transcription

Lecture Notes on Discrete MathematicsDRAFTJuly 30, 2019

AFDRT2

Contents1 Basic Set Theory71.1Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71.2Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.3Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111.4Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .151.5Composition of functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .181.6Equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192 The Natural Number System25Peano Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252.2Other forms of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . .282.3Applications of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . .312.4Well Ordering Property of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . .332.5Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .342.6Construction of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .362.7Construction of Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40DRAFT2.13 Countable and Uncountable Sets433.1Finite and infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .433.2Families of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .463.3Constructing bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .493.4Cantor-Schröder-Bernstein Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . .513.5Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .554 Elementary Number Theory614.1Division algorithm and its applications . . . . . . . . . . . . . . . . . . . . . . . . . . .614.2Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .654.3Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .685 Combinatorics - I715.1Addition and multiplication rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .715.2Permutations and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .735.2.1Counting words made with elements of a set S . . . . . . . . . . . . . . . . . .735.2.2Counting words with distinct letters made with elements of a set S . . . . . . .745.2.3Counting words where letters may repeat . . . . . . . . . . . . . . . . . . . . .755.2.4Counting subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .765.2.5Pascal’s identity and its combinatorial proof . . . . . . . . . . . . . . . . . . . .773

4CONTENTS5.2.6Counting in two ways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .785.3Solutions in non-negative integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .805.4Binomial and multinomial theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . .835.5Circular arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .865.6Set partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .915.7Number partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .955.8Lattice paths and Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . .986 Combinatorics - II1036.1Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1036.2Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1076.3Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106.3.1Generating Functions and Partitions of n . . . . . . . . . . . . . . . . . . . . . 1166.4Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1196.5Generating Function from Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . 1247 Introduction to Logic133Logic of Statements (SL). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1337.2Formulas and truth values in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1347.3Equivalence and Normal forms in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1377.4Inferences in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1437.5Predicate logic (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1497.6Equivalences and Validity in PL7.7Inferences in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156T7.1DRAF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1538 Partially Ordered Sets, Lattices and Boolean Algebra1618.1Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1618.2Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1698.3Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1768.4Axiom of choice and its equivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1819 Graphs - I1919.1Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1919.2Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1979.3Isomorphism in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2009.4Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2029.5Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2089.6Hamiltonian graphs9.7Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2149.8Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2159.9Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21910 Graphs - II. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21022110.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22110.2 Matching in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22310.3 Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22610.4 Degree sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

5CONTENTS10.5 Representing graphs with matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22811 Polya Theory 11.1 Groups . . . . . . . . . . . . .11.2 Lagrange’s Theorem . . . . .11.3 Group action . . . . . . . . .11.4 The Cycle index polynomial .11.5 Polya’s inventory polynomial.258DRAFTIndex.231231240244248251

6DRAFTCONTENTS

Chapter 1Basic Set TheoryThe following notations will be followed throughout the book.1. The empty set, denoted , is the set that has no element.2. N : {1, 2, . . .}, the set of Natural numbers;3. W : {0, 1, 2, . . .}, the set of whole numbers4. Z : {0, 1, 1, 2, 2, . . .}, the set of Integers;5. Q : { pq : p, q Z, q 6 0}, the set of Rational numbers;6. R : the set of Real numbers; andAFT7. C : the set of Complex numbers.DRThis chapter will be devoted to understanding set theory, relations, functions. We start with the basicset theory.1.1SetsMathematicians over the last two centuries have been used to the idea of considering a collection ofobjects/numbers as a single entity. These entities are what are typically called sets. The technique ofusing the concept of a set to answer questions is hardly new. It has been in use since ancient times.However, the rigorous treatment of sets happened only in the 19-th century due to the German mathematician Georg Cantor. He was solely responsible in ensuring that sets had a home in mathematics.Cantor developed the concept of the set during his study of the trigonometric series, which is nowknown as the limit point or the derived set operator. He developed two types of transfinite numbers,namely, transfinite ordinals and transfinite cardinals. His new and path-breaking ideas were not wellreceived by his contemporaries. Further, from his definition of a set, a number of contradictions andparadoxes arose. One of the most famous paradoxes is the Russell’s Paradox, due to Bertrand Russellin 1918. This paradox amongst others, opened the stage for the development of axiomatic set theory.The interested reader may refer to Katz [8].In this book, we will consider the intuitive or naive view point of sets. The notion of a set is takenas a primitive and so we will not try to define it explicitly. We only give an informal description ofsets and then proceed to establish their properties.A “well-defined collection” of distinct objects can be considered to be a set. Thus, the principalproperty of a set is that of “membership” or “belonging”. Well-defined, in this context, would enableus to determine whether a particular object is a member of a set or not.7

8CHAPTER 1. BASIC SET THEORYMembers of the collection comprising the set are also referred to as elements of the set. Elementsof a set can be just about anything from real physical objects to abstract mathematical objects. Animportant feature of a set is that its elements are “distinct” or “uniquely identifiable.”A set is typically expressed by curly braces, { } enclosing its elements. If A is a set and a is anelement of it, we write a A. The fact that a is not an element of A is written as a 6 A. For instance,if A is the set {1, 4, 9, 2}, then 1 A, 4 A, 2 A and 9 A. But 7 6 A, π 6 A, the English word‘four’ is not in A, etc.Example 1.1.1.1. Let X {apple, tomato, orange}. Here, orange X, but potato 6 X.2. X {a1 , a2 , . . . , a10 }. Then, a100 6 X.3. Observe that the sets {1, 2, 3}, {3, 1, 2} and {digits in the number 12321} are the same as theorder in which the elements appear doesn’t matter.We now address the idea of distinctness of elements of a set, which comes with its own subtleties.Example 1.1.2.1. Consider the list of digits 1, 2, 1, 4, 2. Is it a set?2. Let X {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Then X is the set of first 10 natural numbers. Or equivalently,X is the set of integers between 0 and 11.Definition 1.1.3. The set S that contains no element is called the empty set or the null set andis denoted by { } or . A set that has only one element is called a singleton set.TOne has three main ways for specifying a set. They are:DRAF1. Listing all its elements (list notation), e.g., X {2, 4, 6, 8, 10}. Then X is the set of even integersbetween 0 and 12.2. Stating a property with notation (predicate notation), e.g.,(a) X {x : x is a prime number}. This is read as “X is the set of all x such that x is a primenumber”. Here, x is a variable and stands for any object that meets the criteria after thecolon.(b) The set X {2, 4, 6, 8, 10} in the predicate notation can be written asi. X {x : 0 x 10, x is an even integer }, orii. X {x : 1 x 11, x is an even integer }, oriii. x {x : 2 x 10, x is an even integer } etc.Note that the above expressions are certain rules that help in defining the elements of the setX. In general, one writes X {x : p(x)} or X {x p(x)} to denote the set of all elements x(variable) such that property p(x) holds. In the above, note that “colon” is sometimes replacedby “ ”.3. Defining a set of rules which generate its members (recursive notation), e.g., letX {x : x is an even integer greater than 3}.Then, X can also be specified by(a) 4 X,(b) whenever x X, then x 2 X, and(c) every element of X satisfies the above two rules.

91.2. OPERATIONS ON SETSIn the recursive definition of a set, the first rule is the basis of recursion, the second rule givesa method to generate new element(s) from the elements already determined and the third rulebinds or restricts the defined set to the elements generated by the first two rules. The third ruleshould always be there. But, in practice it is left implicit. At this stage, one should make itexplicit.Definition 1.1.4. Let X and Y be two sets.1. Suppose X is the set such that whenever x X, then x Y as well. Here, X is said to be asubset of the set Y , and is denoted by X Y . When there exists x X such that x 6 Y , thenwe say that X is not a subset of Y ; and we write X 6 Y .2. If X Y and Y X, then X and Y are said to be equal, and is denoted by X Y .3. If X Y and X 6 Y , then X is called a proper subset of Y .Thus, X is a proper subset of Y if and only if X Y and X 6 Y .Example 1.1.5.1. For any set X, we see that X X. Thus, . Also, X. Hence, theempty set is a subset of every set. It thus follows that there is only one empty set.2. We know that N W Z Q R C.3. Note that 6 .4. Let X {a, b, c}. Then a X but {a} X. Also, {{a}} 6 X.5. Notice that {{a}} 6 {a} and {a} 6 {{a}}; though {a} {a, {a}} and also {a} {a, {a}}.Operations on setsDR1.2AFTWe now mention some set operations that enable us in generating new sets from existing ones.Definition 1.2.1. Let X and Y be two sets.1. The union of X and Y , denoted by X Y , is the set that consists of all elements of X and alsoall elements of Y . More specifically, X Y {x x X or x Y }.2. The intersection of X and Y , denoted by X Y , is the set of all common elements of X andY . More specifically, X Y {x x X and x Y }.3. The sets X and Y are said to be disjoint if X Y .Example