Discrete Mathematics (Set Theory) PDF

Discrete Mathematics (Set Theory) Prof. M.P. Bidve Dept. of Comp. Sci. & Engg. M.S.Bidve Engineering College, Latur (M.S.) Contact: +91 – 9421657997 [email protected] For Second Year (B. Tech.) program in Computer Science & Engineering ...

Discrete Mathematics (Set Theory) Prof. M.P. Bidve Dept. of Comp. Sci. & Engg. M.S.Bidve Engineering College, Latur (M.S.) Contact: +91 – 9421657997 [email protected] For Second Year (B. Tech.) program in Computer Science & Engineering  Sets: Venn Diagrams  Sets can be represented graphically using Venn diagrams (named after the English mathematician John Venn, who introduced their use in 1881).  In Venn diagrams the universal set U, which contains all the objects under consideration, is represented by a rectangle.  Note that the universal set varies depending on which objects are of interest.  Inside this rectangle, usually circles are used to represent sets.  Sometimes points are used to represent the particular elements of the set.  Venn diagrams are often used to indicate the relationships between sets.  Figure 1 shows a Venn diagram of a set V = {a, e, i, o, u} (i.e. 2 Set of Vowels.)  More Set Terminologies  Empty Set: A set with no element is called as empty set ( i.e. 𝜙 or { } )  Singleton Set: A set with one element is called a singleton set. ◦ Example: S = {a} , M = {{x}}, A = {} , all these S, M, A are singleton sets.  Subset: The set A is said to be a subset of set B if and only if every element of set A is also an element of set B. ◦ We use the notation A ⊆ B to indicate that A is a subset of the set B. ◦ Example: Let A = {2, 4, 6, 8, 10} , and B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}  Here A ⊆ B , as every element of set A is also an element of set B.  But B ⊈ A , as not every element of set B is also an element 3  Important Properties of Subsets 1. Two sets are called equal if both are subsets of each other. ◦ Example: Let A = {a, b, c}, and B = {b, a, c} ; here we see A ⊆ B and B ⊆ A, it means A = B. Proper Subset: If a set A is a subset of the set B, but A ≠ B, we write A ⊂ B and say that A is a proper subset of B. 2. 3. Note:- For every non-empty set S; (i) 𝜙 ⊆ S and (ii) S ⊆ S ; is 𝜙 and - i.e. for any non empty set there exists at least 2 subsets; one other is the set itself. Set may have other sets as its members. ◦ For example, we have the set A = { 𝜙, {a} , {b} , {a, b} } 4. ◦ Also B = {x | x is a subset of the set {a , b} } ◦ In above sets A & B, the members are again other sets. i.e A is a set of sets as members. Similarly B also is a set of sets as members. ◦ Note that these above two sets A and B are equal, i.e., A = B. 4  Sets: Venn Diagrams Exercise 1. Use a Venn diagram to illustrate the subset of odd integers in the set of all positive integers not exceeding 10. 5  Sets: Venn Diagrams Exercise 2. Use a Venn diagram to illustrate the set of all months of the year whose names do not contain the letter R in the set of all months of the year. Use a Venn diagram to illustrate the relationship A⊆B & B⊆C. Use a Venn diagram to illustrate the relationships A ⊂ B and B ⊂ 3. 4. C. Ans: The dots in certain regions indicate that those regions are not empty. 6  Exercise Set  Determine whether each of these statements is True or False.  Solution: a) False , as even 0 can’t be a member of Empty set. b) False , in this 0 is member of RHS set but not 𝜙 , the subset of 𝜙 is always itself only i.e. 𝜙, hence {0} can’t be a proper subset of 𝜙 c) False , as 𝜙 is a one of the subset of all sets, hence 𝜙 is also a subset of set {0} d) True e) False , not {0} but just 0 is a member of {0} f) False , {0} is a subset of {0} because of S ⊆ S 7  Exercise Set  Determine whether each of these statements is True or False.  Solution: a) True , as 𝜙 is a member of right side set {𝜙} b) True , as 𝜙 is a member of right side set {𝜙, {𝜙}} , as 𝜙 is a member of right side set {𝜙}, and not {𝜙} c) False d) True , as {𝜙} is a member of right side set {{𝜙}} e) True , if we list all the subsets of right side set, we get one subset as like left side set. f) True , same like above. 8  Exercise Set  Determine whether each of these statements is True or False.  Solution: a) True , as x is a member of right side set {x} b) True , as {x } is possible subset of right side set {x } c) False , as {x } is not a member of right side set {x }, but just x is. d) True , as {x} is a member of right side set {{x}} e) True , as 𝜙 is always one possible subset of any set f) False , as 𝜙 is not a member of {x}same like above. 9  Finite Sets and Cardinality of Set  Finite Set: Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set. ◦ Example: S = {1,2, 3, 4, 5} , A = {a, b, c, … , z} , S = { x∈Z+| x < 5 Crore }  Infinite Set: The set which is not finite is called as infinite set. ◦ Example: A set of positive integers.  Cardinality of Set: The total number of unique / distinct elements present is a set is called as Cardinality of that set. ◦ EXAMPLE: Let A be the set of odd positive integers less than 10. Then |A| = 5. ◦ EXAMPLE: Let S be the set of letters in the English alphabet. Then |S| = 26. |𝜙| = 0. ◦ EXAMPLE: Because the null set has no elements, it follows that 10  Cardinality of Set : Exercise  Solution: a) |{a}| = 1 b) |{{a}}| = 1 c) |{a, {a}}| = 2 d) |{ a, {a}, {a,{a}} }| = 3  Solution: a) |𝜙| = 0 b) |{𝜙}| = 1 c) |{𝜙, {𝜙}}| = 2 d) |{𝜙, {𝜙}, {𝜙, {𝜙}} }| = 3 11  Power Set P(S)  Power set answers the question, “How many and which subsets are there of set a {1, 2} ?”  Power Set: Given a set S, the power set of S is the set of all subsets of the set S.  The power set of S is denoted by P(S).  Note: If a set has n elements, then its power set has 2n elements.  Example: The power set of the set S = {a, b} is the set of all subsets of {a , b} P(S) = P({a, b}) = { 𝜙 , {a} , {b} , {a, b} }  Exercise: What is the power set of {0, 1, 2}?  Solution: The power set P({ 0, 1 ,2 }) is the set of all subsets of { 0, 1, 2 }. Hence, P({0, 1, 2}) = { 𝜙, {0} , {1} , {2} , {0, 1} , {0, 2} , {1, 2} , {0, 1, 2 } }  Application: Many problems involve testing all combinations of elements of a set to see if they satisfy some property. To consider all such combinations of elements of a set S, we build a new set that has all the subsets of S as its members. 12  Power Set - Exercise Solution: a) P({a}) = { 𝜙, {a} } b) P({a, b}) = { 𝜙, {a}, {b}, {a, b} } c) P({𝜙 , {𝜙}) = {𝜙 , {𝜙} , {{𝜙}} , {𝜙 , {𝜙}}} (Note: If a set has n elements, then its power set has 2n elements.) 13 Solution: a) |P({a, b,{a, b}})| = 2n = 23 = 8 here n=3  Power Set - Exercise  Determine whether each of these sets is the power set of a set, where a and b are distinct elements. a) 𝜙 b) {𝜙, {a}} c) {𝜙, {a}, {𝜙, a}} d) {𝜙, {a}, {b}, {a, b}} Solution: set 𝜙 is a subset of every set. a) Every set S contains at least one subset, because the empty For every set S, the power set of it then contains at least one element, and thus the power set can never be the empty set 𝜙. Hence No, 𝜙 is not a power set. b) Yes, as we found {𝜙, {a}} is a power set of set {a}. c) No, {𝜙, {a}, {𝜙, a}} can’t be a power set, because cardinality of a power set is always in 2n, i.e. either 1 or 2 or 4 or 8 or 16 ….. likewise. But here in the given power set the cardinality is 3, which voids the above cardinality observation about power set. Hence {𝜙, {a}, {𝜙, a}} is not a power set. 14  Ordered n-tuple  Because sets are unordered, sometimes the order of elements in a collection is also important in certain applications.  Hence a different structure is needed to represent ordered collections. This is provided by ordered n-tuples.  Definition: The ordered n-tuple (a1, a2, …, an) is the ordered collection that has a1as its first element, a2 as its second element, … , and an as its nth element.  Note: Ordered n-tuple or Ordered collection is always enclosed with ( ), unlike Set which encloses its collection with { }.  In particular, 2-tuples are called ordered pairs.  The ordered pairs (a , b) and (c, d) are equal if and only if a = c and b = d.  In general; we say that two ordered n -tuples are equal if and only if each corresponding pair of their elements is equal. ◦ In other words, (a1, a2 ,... , an ) = (b1, b2,... , bn) if and only if ai = bi , for i = 1 , 2,... , n. 15  Cartesian Product of Sets  Cartesian product of sets (named after Rene Descartes, renowned French Mathematician and Philosopher).  Example: Let A = {1 , 2} and B = {a , b, c} be two sets; Then the Cartesian product of A and B is; A x B = {(1, a), (1, b), (1, c), (2, a), (2, b) , (2, c)}. Whereas B x A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1) , (c, 2)}.  Conclusion: The Cartesian products A x B and B x A are not equal, unless A = B or A = 𝜙 or B = 𝜙 (so that A x B = 𝜙) 16  Cartesian Product of Sets Exercise: Solution: Note: Based on above examples we conclude that, the Cardinality of Cartesian Product of two sets is equal to the multiplication of cardinalities of those two Sets. 17  Cartesian Product of Sets - Exercise  What is the Cartesian product A x B x C, where A is the set of all airlines and B and C are both the set of all cities in the United States?  Solution: The set of triples (a, b, c), where a is an airline and b and c are cities.  What is the Cartesian product A x B , where A is the set of courses offered by the mathematics department at a university and B is the set of mathematics professors at this university?  Solution: 18  Cartesian Product of Sets - Exercise  Exercise: Let A be a set. Show that 𝜙 x A = A x 𝜙 = 𝜙 ,  We know 𝜙 x A = {(x , y) | x ∈ 𝜙 and y ∈ A} = 𝜙 = {(x , y) | x ∈ A and y ∈ 𝜙} = 𝜙  Exercise: Suppose that A x B = 𝜙, where A and B are sets. What can you conclude?   Exercise: Let A = {a, b, c}, B = {x, y}, and C 19  Cartesian Product of Sets - Exercise  Exercise: How many different elements does A x B have if A has m elements and B has n elements?  mn  Exercise: Explain why A x B x C and (A x B) x C are not the same.   Exercise: Explain why (A x B) x (C x D) and A x (B x C) x D are not the same.  Here first Cartesian product (A x B) x (C x D) is a set of ordered pairs (i.e. 2-tuple), whose both the coordinates are again ordered pairs. But in second Cartesian product is a set of ordered triples (i.e. 3- tuple), whose second coordinate is again ordered pair. 20  Set Operations  Two sets can be combined in many different ways.  EXAMPLE: The union of the sets { 1 , 3 , 5 } and { 1 , 2, 3 } is; { 1 , 3 , 5 } U { 1 , 2, 3 } = { 1 , 2, 3 , 5 }. 21  Set Operations  EXAMPLE: The intersection of the sets { 1 , 3 , 5 } and { 1 , 2, 3 } is; { 1 , 3 , 5 } ∩ { 1 , 2, 3 } = { 1, 3 }. 22  Set Operations U A B Venn diagram of two disjoint set A and B. EXAMPLE: The difference of {1, 3, 5} and {1, 2, 3} is {1, 3, 5} - {1, 2, 3} = {5}. This is different from the difference of {1, 2, 3} - {1, 3, 5} , which is the set {2}. 23  Set Operations  Once the universal set U has been specified, the complement of a set can be defined.  Set Operations  Example: The symmetric difference of { I, 3, 5 } and { I, 2, 3 } is given by { I, 3, 5 } ⊕ { I, 2, 3 } = { 2, 5 }  Venn diagram for the symmetric difference of the sets A and B is given below.  Observations on Symmetric difference:  Set Identities  Following is the list the most important set identities/ facts.  How to show that sets or combination of sets are equal ?  There are different ways to show that sets are equal: 1. One way to show that two sets are equal is to show that each set is subset of other. ◦ to show that one set is a subset of a second set, we can show that if an element belongs to the first set, then it must also belong to the second set. 2. Using set builder notation and logical equivalences (using available / existing set identities). 3. Using Membership Tables.  How to show that sets or combination of sets are equal ? 1. One way to show that two sets are equal is to show that each set is subset of other. ◦ to show that one set is a subset of a second set, we can show that if an element belongs to the first set, then it must also belong to the second set.  Prove that = ∪.  Solution: To show that = ∪ , we will show that ⊆ ∪ and that ∪ ⊆ ; First, we will show that ⊆ ∪. So suppose that x ∈. By the definition of complement, x ∉ (). i.e. by the definition of intersection, ¬((x ∈ A) ˄ (x ∈ B)) is true. Applying De Morgan's law (from logic), we see ¬ (x ∈ A) ˅ ¬ (x ∈ B). Hence, by the definition of negation, x ∉ or x ∉. By the definition of complement, x ∈ or x ∈. It follows by the definition of union that x ∈ ∪.  How to show that sets or combination of sets are equal ?  Next, we will show that ∪ ⊆. Now suppose that x ∈ ∪. By the definition of union, x ∈ or x ∈. Using the definition of complement, we see that x ∉ or x ∉. Consequently, ¬(x ∈ A) ˅ ¬(x ∈ B) is true. By De Morgan's law (from logic), we conclude that ¬((x∈A)˄(x∈B)) is true. By the definition of intersection, it follows that ¬(x ∈ A ∩ B) holds. We use the definition of complement to conclude that x ∈. This shows that ∪ ⊆. Because we have shown that each set is a subset of the other (i.e.  How to show that sets or combination of sets are equal ? Proof: We will prove this identity by showing that each side is a subset of the other side.  How to show that sets or combination of sets are equal ? 2. Using set builder notation and logical equivalences (using available / existing set identities), show that set are equal. Example:  How to show that sets or combination of sets are equal ? 2. Using set builder notation and logical equivalences (using available / existing set identities). Example:  Exercise on Set Equality (Homework) 1. 2. 3. 4. 5.  Exercise on Set Operations Solution: a) The set of students who live within one mile of school and who walk to classes b) The set of students who live within one mile of school or who walk to classes (or who do both) c) The set of students who live within one mile of school but do not walk to classes d) The set of students who walk to classes but live more than one mile away from school Solution:  Exercise on Set Operations Solution: a) {4, 6} b) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} c) {4, 5, 6, 8, 10} d) {0, 2, 4, 5, 6, 7, 8, 9, 10} Solution: next slide  Exercise on Set Operations Solution: Online Assignment 1  Exercise on Set Operations B⊆A Solution: A⊆B a) A∩B=𝜙 b) c) d) Nothing, because this is always true / Union is Commutative. e) A=B  3. Proving Set identities / Equalities using Membership Tables  Membership table: is a table displaying the membership of elements in sets.  We consider each combination of sets that an element can belong to and verify that elements in the same combinations of sets belong to both the sets in the identity.  To indicate that an element is in a set, a 1 is used; and to indicate that an element is not in a set, a 0 is used.  i.e., Union: 0∪0=0 ; 0 ∪ 1 = 1; 1 ∪ 0 = 1; 1∪1=1  Intersection: 0 ∩ 0 = 0; 0 ∩ 1 = 0; 1 ∩ 0 = 0; 1 ∩ 1 =1  Difference: 0-0=0; 0-1=0 ; 1-0=1; 1-1= 0 As row-wise the  Symmetric Difference: 0 ⊕ 0 = 0; 0 ⊕ 1 = 1; 1 ⊕membership 0 = 1; 1 ⊕ 1 = 0  Complementation: =1 ; =0 values for and columns are Example: Prove using membership table; same;  Exercise on Set Operations 0∪0=0 ; 0 ∪ 1 = 1; 1 ∪ 0 = 1; 1∪1=1  i.e., Union: Intersection: 0 ∩ 0 = 0; 0 ∩ 1 = 0; 1 ∩ 0 = 0; 1 ∩ 1 =1   Symmetric Difference: 0 ⊕ 0 = 0; 0 ⊕ 1 = 1; 1 ⊕ 0 = 1; 1 ⊕ 1 = 0  Complementation: =1 ; =0  Prove the first distributive law, which states that A ∩ (BUC) = (A∩B) U (A∩C) for all sets A, B, and C.  Solution: A Membership Table for the Distributed Property is given below:  Online Assignment 2  Let A, B, and C be sets; use membership table to show the following: 1. 2. 3. 4. A − (A − B) = A ∩ B 5. (A ∪ B) − B = A − B  Successor  The successor of the set A is the set A U { A }.  Exercise:  Solution: a) { 1, 2, 3, { 1, 2, 3} } b) {𝜙} c) {𝜙, {𝜙}} d) {𝜙, {𝜙}, {𝜙, {𝜙} } }  Exercise: How many elements does the successor of a set with n elements have?  Answer: n+1  Multisets  Sometimes the number of times that an element occurs in an unordered collection matters.  Multisets are unordered collections of elements where an element can occur as a member more than once.  The notation { m1∙ a1, m2∙ a2, ……, mr∙ ar } denotes the multiset with element a1 occurring m1 times, element a2 occurring m2 times, and so on.  The numbers mi, i = 1, 2,... , r are called the multiplicities of the elements ai , i = 1, 2,... , r.  Example: If {a, a, a, b, b, c} is a multiset; then {a, a, a, b, b, c} = {3·a, 2·b, 1.c}  Example: If {1, 1, 3, 3, 2, 3, 3} is a multiset; then {1, 1, 3, 3, 2, 3, 3} = {2∙ 1, 1∙ 2, 4 ∙3}  Operations on Multisets  Let P and Q be multisets.  The union of the multisets P and Q (denoted by P ∪ Q) is the multi set where the multiplicity of an element is the maximum of its multiplicities in P and Q. Example: Let A and B be the multisets {3·a, 2·b, 1·c} and {2·a, 3·b, 4·d} respectively. Find A ∪ B. Solution: {3·a, 3·b, 1·c, 4·d}  The intersection of the multisets P and Q (denoted by P ∩ Q) is the multiset where the multiplicity of an element is the minimum of its multiplicities in P and Q. Example: Let A and B be the multisets {3·a, 2·b, 1.c} and {2.a , 3.b, 4.d} respectively. Find A ∩ B. Solution: {2·a, 2·b}  Operations on Multisets  The difference of multisets P and Q (denoted by P − Q) is the multiset where the multiplicity of an element is the multiplicity of the element in P less its multiplicity in Q unless this difference is negative, in which case the multiplicity is 0. Example: Let A and B be the multisets {3·a, 2·b, 1·c} and {2·a, 3·b, 4·d} respectively. Find A − B and B − A. Solution: A − B = {1·a, 1·c} B − A = {1·b, 4·d}  The sum of multisets P and Q (denoted by P + Q) is the multiset where the multiplicity of an element is the sum of multiplicities in P and Q. Example: Let A and B be the multisets {3·a, 2·b, 1·c} & {2·a, 3·b, 4·d} respectively. Find A + B. Solution: {5·a, 5·b, 1·c, 4·d}  Principle of Inclusion-Exclusion  We often are interested in finding the cardinality of a union of two finite sets A and B; and which is given by;  Whereas, the cardinality of a union of three finite sets A, B, and C is given by; |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + | A ∩ B ∩ C|  Similarly, the cardinality of a union of four finite sets A, B, C, and D is given by; |A ∪ B ∪ C ∪ D | = |A| + |B| + |C| + |D| − |A ∩ B| − |A ∩ C| − | A ∩ D| − |B ∩ C| − |B ∩ D| − |C ∩ D| + |A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| − |A ∩ B ∩ C ∩ D|  And so on;