Set Theory PDF

Faculty of Computer Applications Bachelors of Computer Applications BCA - Sem 1 Mathematics - 1 05BC3101 Unit 1 Set Theory NAAC A+ Accredited University  UNIT 1 : SET THEORY CO...

Faculty of Computer Applications Bachelors of Computer Applications BCA - Sem 1 Mathematics - 1 05BC3101 Unit 1 Set Theory NAAC A+ Accredited University  UNIT 1 : SET THEORY COURSE CONTENT : 1) Introduction 2) Methods of describing a set 3) Types of Sets (Null Set, Singleton Set, Finite Set, Infinite Set, Equal Set, Equivalent Set, Subset, Proper Subset, Power Set, Universal Set) 4) Operation on Sets (Union, Intersection, Difference, Symmetric Difference, Complement of a set) 5) Algebra of Sets (Commutative Laws, Associative Laws, Distributive Laws) 6) De Morgan’s Laws 7) Venn Diagrams 8) Cardinality of sets 9) Cartesian Product of two sets NAAC A+ Accredited University  A Set : A set is a collection of elements without repetition. A set can be finite or infinite. Following are some examples of sets. A = {1, 2, 3}, B = {a, b, c}, C = {-1, 0, 1} etc. The above sets are all finite sets. We say that a member/element ‘belongs to’ that set, and this is denoted using the symbol ∈. Thus, mathematically we write 1, 2, 3 ∈ A a, b, c ∈ B -1, 0, 1 ∈ C Some Standard Set Notations : Natural numbers (Counting numbers) : N = {1, 2, 3, 4, 5, …….} Integers : Z = {……, -2, -1, 0, 1, 2, …….} Rational numbers (Fractions) : The rational numbers cannot be listed as above, but are defined by their property.  p  Q =  x / x = , where p, q  Z , q  0   q  -3, 0, 1/3, -5/2 etc. are some examples of rational numbers. Irrational numbers : The irrational numbers are those which are not rational. That is,  p  I =  x / x  , where p, q  Z , q  0   q  2, 3,  etc. are irrational numbers. Real numbers : The union of the rational and the irrational numbers is called the set of real numbers, denoted by R. Thus mathematically, R = Q  I NAAC A+ Accredited University  Methods to denote a set : Listing method : In this method we simply list out all the members of the set separated by a comma enclosed within a pair of curly brackets. As, A = 1, 2, 3, 4, 5 Property method : In this method, instead of Explicitly mentioning each member of the set, we use their mathematical property using some standard set notations and some algebraic conditions. The above set A shown in ‘Listing method’ can be demonstrated using ‘Property method’ as, A =  x / x  N , x  5 Null Set or Empty Set : A set which has no elements is called an empty set or a null set, and is denoted using { } or φ(phi). Thus, if A is an empty set, we write A = { } or A = φ (Note that A = {φ} is not a correct notation for a null set.) Singleton Set : A set having only one element is called singleton set. Examples : A = {2} B = {x ∈ N / x is an even prime number} C = {x / x is least positive integer} = {1} D = {x / x is a perfect square of an integer 60 < x < 70} Finite Set : A set is called finite set if it is either null set or its elements can be counted by natural numbers or process of listing terminates at a certain natural number. Examples : A = {x ∈ N / 1 < x < 100} B = {a, e, i, o, u} NAAC A+ Accredited University  Cardinality or Order of a Finite Set : The total number of element in a finite set is called Cardinality or Order of a finite set. It is denoted by n (A) or |A|. Examples : A = {a, e, i, o, u} Here n (A) = 5 B = {x ∈ Z / -4 < x < 4} Thus, B = {-3, -2, -1, 0, 1, 2, 3} Here n (B) = 7 Infinite Set : If the elements of a set cannot be counted in a finite number, then the set is called an infinite set. Examples : A = {1, 2, 3, 4, …} B = {x / x is an even natural number} Also, N, Z, Q, R, Z+, Q+, R+ all are infinite sets. Subset of a Set : For any two sets A and B, if all the elements of set A are also present in set B, then we say that, set A is a subset of set B. And we denote this as A  B. Consider the following example. If A = {1, 2, 3} and B = {0, 1, 2, 3, 4} then A  B. Notes : A null set is a subset of every set. Any set can be regarded as a subset of itself. Thus, any non - empty set has atleast two subsets; the null set and the set itself. Also, if A is a subset of B, then B is called a ‘superset’ of A. NAAC A+ Accredited University  Union and intersection of sets : Union of sets : Consider two sets A and B. Then the union of sets A and B is a set which contains all the elements of set A and set B, and this is denoted as A  B. Intersection of sets : Consider two sets A and B. Then the intersection of sets A and B is a set which contains only the elements which are common to both sets A and B, and this is denoted as A  B. Example : Consider the following sets. A = {0, 1, 2, 3}, B = {2, 3, 4, 5} and C = {6, 7} Here, observe that A  B = {0, 1, 2, 3, 4, 5} A  B = { 2, 3} B C = { } NOTE : For the above defined sets, observe the inclusion relation NZQR I  R Q  I={} Equal Sets : Two sets A and B are said to be equal sets if every element of set A is also an element of set B and every element of set B is an element of set A. Notation : A = B Examples : (1) A = {-1, 1}, B = {x ∈ Z / x2 – 1 = 0} Here A = B (2) C = {2, 3, 4, 5}, D = {x ∈ N / 1 < x < 6} Here C = D NAAC A+ Accredited University  Equivalent Sets : Two finite sets A and B are said to be equivalent sets if they have same number of elements. In other words, two finite sets A and B are said to be equivalent sets if n (A) = n (B). Notation: A ≡ B Examples : (1) A = {a, e, i, o, u} and B = {1, 2, 3, 4, 5} Here n (A) = n (B) = 5. Therefore A ≡ B (2) A = {x ∈ N / x is a factor of 4} and B = {x ∈ N / x is a factor of 9} Here A = {1, 2, 4} and B = {1, 3, 9} So, n (A) = n (B) = 3 Therefore A ≡ B Note : Two equal sets are always equivalent, but two equivalent sets may not be equal sets. Power set of a set : The set of all subsets of a given set is known as the ‘power set’ of that set. Notation : The power set of a set A is denoted as P(A). Example : Write the power set of set A = {a, b} Subsets of A = ∅, {a, b}, {a}, {b} P(A) = {∅, {a}, {b}, {a, b}} Example : Write power set of a set B = {x 𝛜 N / x is a factor of 9} Here B = {1, 3, 9} P(B) = {∅, {1}, {3}, {9}, {1, 3}, {1, 9}, {3, 9}, {1, 3, 9}} NAAC A+ Accredited University Example : Write power set of a set C = {x 𝛜 N / x is a factor of 8} Here C = {1, 2, 4, 8} P(C) = {∅, {1}, {2}, {4}, {8}, {1, 2}, {1, 4}, {1, 8}, {2, 4}, {2, 8}, {4, 8}, {1, 2, 4}, {1, 2, 8}, {1, 4, 8}, {2, 4, 8}, {1, 2, 4, 8}} Exercise : (1) Write power set of a set A = {x 𝛜 N / x is a factor of 25} (2) Write all proper subsets of set A = {x 𝛜 N / x is a factor of 15} No. of Set Subsets No. of Elements subsets = 2n (n) 0 A={} {} 20 = 1 1 A = {a} { }, {a} 21 = 2 2 A = {a, b} { }, {a}, {b}, {a, b} 22 = 4 3 A = {a, b, c} { }, {a}, {b}, {c}, {a, b}, {a, 23 = 8 c}, {b, c}, {a, b, c} 4 A = {a, b, c, d} { }, {a}, {b}, {c}, {d}, 24 = 16 {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} Note : Observe that, for a set with n members, its power set will have 2n members i.e., if n (A) = n, then n{P(A)} = 2n Example : Find total number of subsets of a set A = {x ∈ N / x is a factor of 4}. Also write all subsets of set A. Solution : Here A = {1, 2, 4} So, n (A) = 3 Total number of subsets of A = 23 = 8 Also, P(A) = {∅, {1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}} NAAC A+ Accredited University Example : Find total number of subsets of the set A = {x ∈ N / x is a factor of 27}. Solution : Here A = {1, 3, 9, 27} So, n (A) = 4 Total number of subsets of set A = 24 = 16 Also, P(A) = {∅, {1, 3, 9, 27}, {1}, {3}, {9}, {27}, {1, 3}, {1, 9}, {1, 27}, {3, 9}, {3, 27}, {9, 27}, {1, 3, 9}, {1, 3, 27}, {1, 9, 27}, {3, 9, 27}} Universal Set : A set which is the superset of all the sets under consideration is known as Universal Set and is denoted as U. Disjoint Sets : Two sets A and B are called disjoint sets if they have no elements in common, i.e., their intersection is an empty set. Mathematically, if A  B =  , then we say that A and B are disjoint sets. Example : If A = {-1, 0, 1} and B = {2, 4, 6, 8, 10}, then A and B are disjoint. Complement of a Set : The complement of a set is a set all the member of the Universal set, which are not present in the given set. Notation : The complement of a set A is denoted as A’ or AC. Example : Let 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8} and A = {2, 4, 6, 8}. Then find A’. Here 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8} and A = {2, 4, 6, 8} Therefore A’ = {1, 3, 5, 7} NAAC A+ Accredited University  Venn Diagrams : A Venn Diagram is a pictorial representation of sets where the Universal set is shown as the interior of a rectangle, and all other sets are demonstrated as the interiors of circles within the rectangle. Let us consider the following cases for two sets A and B. And then represent them in Venn diagrams. (i) Intersecting Sets ( A  B   ) : U (ii) Disjoint Sets ( A  B =  ) : U NAAC A+ Accredited University (iii) A is a subset of B ( A  B ) : U (iv) A and B are equal (A = B) : U NAAC A+ Accredited University  Demonstrating set operations using Venn Diagrams : (i) Union of sets A and B (A  B) : (ii) Intersection of A and B (A  B) : (iii) Complement of a set A (i.e. A’) : U NAAC A+ Accredited University Example : Let 𝕌 = {1, 2, 3, …, 8, 9, 10} and A = {1, 2, 4, 5, 9}. Then, find A’ and represent it using a Venn Diagram. Solution : Here A = {1, 2, 4, 5, 9} Thus, A’ = {3, 6, 7, 8, 10} Venn Diagram for A’ is shown below. A’ Example : Let 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {1, 2, 3, 4, 5} and B = {3, 5, 7, 9}. Then find A ∪ B and A ∩ B. And represent their Venn diagrams. Solution : Here A = {1, 2, 3, 4, 5} and B = {3, 5, 7, 9} Therefore, A ∪ B = {1, 2, 3, 4, 5, 7, 9} Venn diagram for A U B is shown below. NAAC A+ Accredited University Again, A = {1, 2, 3, 4, 5} and B = {3, 5, 7, 9} Therefore A ∩ B = {1, 2, 3, 4, 5} ∩ {3, 5, 7, 9} = {3, 5} Venn diagram for A ∩ B is shown below. AB Example : Let 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {𝒙 ∈ N / x is a factor of 10} and B = {𝒙 ∈ N / x is a factor of 8}. Then, find A ∪ B and represent its Venn Diagram: Solution : A = {1, 2, 5, 10}, B = {1, 2, 4, 8} Thus, A ∪ B = {1, 2, 4, 5, 8, 10} Venn Diagram : Try yourself. Exercise : (1) Let 𝕌 = {1, 2, 3, …, 9, 10,11}, A = {1, 2, 4, 5, 10} and B = {2, 6, 9,11}. Then determine the following. (i) A’ and its Venn Diagram (ii) B’ and its Venn Diagram (iii) A ∪ B and its Venn Diagram (iv) A ∩ B and its Venn Diagram NAAC A+ Accredited University (2) Let 𝕌 = {1, 2, 3, …, 9, 10, 11, 12}, A = {x ∈ N / x is factor of 12} and B = {x ∈ N / x is factor of 10}. Then, determine the following: (i) A’ and its Venn Diagram (ii) B’ and its Venn Diagram (iii) A ∪ B and its Venn Diagram (iv) A ∩ B and its Venn Diagram Notes : (i) (A’)’ = A (ii)  ’= 𝕌 and 𝕌’ =  (iii) For any set A, A ∪ A’ = 𝕌 and A ∩ A’ =  (iv) For any set A, A ∪  = A and A ∩  =  (v) For any set A, A ∪ 𝕌 = 𝕌 and A ∩ 𝕌 = A (vi) For sets A and B, if A  B, then A ∪ B = B and A ∩ B = A Example : N ∪ Z = Z, N ∩ Q = N etc. Difference of two sets : Let A and B be two sets. Then the ‘Difference set’ A – B is a set of all elements which belong to A but do not belong to B. Venn Diagram for Difference set A – B : NAAC A+ Accredited University Venn Diagram for Difference set B – A : Example : A = {1, 2, 3, 4, 5} and B = {2, 4, 6, 7}. Then, find A – B and B – A. A – B = {1, 2, 3, 4, 5} – {2, 4, 6, 7} = {1, 3, 5} B – A = {2, 4, 6, 7} – {1, 2, 3, 4, 5} = {6, 7} Exercise : For A = {1, 3, 5, 7, 9}, B = {2, 4, 6, 8, 9, 10}. Then find A – B and B – A. Note : If A and B are disjoint sets, then A – B = A and B – A = B Example : A = {1, 2, 3} B = {4, 5} A – B = {1, 2, 3} – {4, 5} = {1, 2, 3} = A B – A = {4, 5} – {1, 2, 3} = {4, 5} = B Example : Let 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {2, 3, 5, 7, 8} and B = {1, 2, 4, 8, 9}. Then find A – B and B – A and draw their Venn Diagrams. Solution : Here 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {2, 3, 5, 7, 8} and B = {1, 2, 4, 8, 9} Now A – B = {2, 3, 5, 7, 8} – {1, 2, 4, 8, 9} = {3, 5, 7} NAAC A+ Accredited University Venn diagram for A – B : And B – A = {1, 2, 4, 8, 9} – {2, 3, 5, 7, 8} = {1, 4, 9} Venn diagram for B – A : Symmetric Difference of Two Sets : For two sets A and B, the Symmetric Difference set of A and B is the set which contains all elements belongs to set A and B but not present in both. Notation : A ∆ B (A delta B) A ∆ B = (A ∪ B) – (A ∩ B) OR A ∆ B = (A – B) ∪ (B – A) NAAC A+ Accredited University Venn diagram for Symmetric Difference Set A  B : U A∆B Example : Let 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {2, 3, 5, 7, 8} and B = {1, 2, 4, 8, 9}. Then find A ∆ B and draw its Venn Diagram. Solution : A ∆ B = (A ∪ B) – (A ∩ B) A ∪ B = {2, 3, 5, 7, 8} ∪ {1, 2, 4, 8, 9} = {1, 2, 3, 4, 5, 7, 8, 9} A ∩ B = {2, 3, 5, 7, 8} ∩ {1, 2, 4, 8, 9} = {2, 8} Therefore, A ∆ B = (A ∪ B) – (A ∩ B) = {1, 2, 3, 4, 5, 7, 8, 9} – {2, 8} = {1, 3, 4, 5, 7, 9} OR : A ∆ B = (A – B) ∪ (B – A) Now A – B = {2, 3, 5, 7, 8} – {1, 2, 4, 8, 9} A – B = {3, 5, 7} and B – A = {1, 2, 4, 8, 9} – {2, 3, 5, 7, 8} = {1, 4, 9} Therefore A ∆ B = (A – B) ∪ (B – A) = {3, 5, 7} ∪ {1, 4, 9} = {1, 3, 4, 5, 7, 9} NAAC A+ Accredited University Venn Diagram for A ∆ B : AB Exercise : Let A = {1, 2, 3, 4, 5, 6} and B = {3, 2, 4, 7, 8, 9}, then determine A ∆ B. (Solution : A ∆ B = {1, 5, 6, 7, 8, 9}) Examples : Let 𝕌 = {x ∈ N / x is a factor of 48}, A = {x ∈ N / x is a factor of 24}, B = {x ∈ N / x is a factor of 12} and C = {x ∈ N / x is a factor of 8}. Then find the following : (1) A’ (2) B’ (3) C’ (4) A ∪ B and its Venn Diagram (5) A ∩ B and its Venn Diagram (6) A ∆ B and its Venn Diagram (7) P(C) (8) (B ∪ C)’ (9) B’ ∩ C’ Solution : Here 𝕌 = {1, 2, 3, 4, 6, 8, 12, 16, 24, 48} A = {1, 2, 3, 4, 6, 8, 12, 24}, B = {1, 2, 3, 4, 6, 12} and C = {1, 2, 4, 8} (1) A’ = {16, 48} (2) B’ = {8, 16, 24, 48} NAAC A+ Accredited University (3) C’ = {3, 6, 12, 16, 24, 48} (4) A ∪ B = {1, 2, 3, 4, 6, 8, 12, 24} ∪ {1, 2, 3, 4, 6, 12} = {1, 2, 3, 4, 6, 8, 12, 24} Venn Diagram : U (5) A ∩ B = {1, 2, 3, 4, 6, 8, 12, 24} ∩ {1, 2, 3, 4, 6, 12} = {1, 2, 3, 4, 6, 12} Venn Diagram : U (6) A ∆ B = (A – B) ∪ (B – A) Now A – B = {1, 2, 3, 4, 6, 8, 12, 24} - {1, 2, 3, 4, 6, 12} = {8, 24} NAAC A+ Accredited University And B – A = {1, 2, 3, 4, 6, 12} – {1, 2, 3, 4, 6, 8, 12, 24} = ∅ Therefore A ∆ B = {8, 24} ∪ ∅ = {8, 24} Venn Diagram : U (7) P(C) Here C = {1, 2, 4, 8} Therefore P(C) = {∅, {1}, {2}, {4}, {8}, {1, 2}, {1, 4}, {1, 8}, {2, 4}, {2, 8}, {4, 8}, {1, 2, 4}, {1, 2, 8}, {1, 4, 8}, {2, 4, 8}, {1, 2, 4, 8}} (8) (B ∪ C)’ B ∪ C = {1, 2, 3, 4, 6, 12} ∪ {1, 2, 4, 8} = {1, 2, 3, 4, 6, 8, 12} (B ∪ C)’ = {16, 24, 48} 9) B’ ∩ C’ = {8, 16, 24, 48} ∩ {3, 6, 12, 16, 24, 48} = {16, 24, 48} Example : Let 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {1, 2, 4, 5}, B = {6, 7, 9, 10} and C = {1, 2, 9, 10}. Then find the following : (1) A’ (2) B’ (3) C’ (4) A ∪ B and its Venn Diagram (5) A ∩ B and its Venn Diagram (6) A ∆ B and its Venn Diagram (7) Verify (B ∪ C)’ = B’ ∩ C’ NAAC A+ Accredited University Solution : Here 𝕌 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 2, 4, 5}, B = {6, 7, 9, 10} and C = {1, 2, 9, 10} (1) A’ = {3, 6, 7, 8, 9, 10} (2) B’ = {1, 2, 3, 4, 5, 8} (3) C’ = {3, 4, 5, 6, 7, 8} (4) A ∪ B = {1, 2, 4, 5} ∪ {6, 7, 9, 10} = {1, 2, 4, 5, 6, 7, 9, 10} Venn Diagram : U A∪B (5) A ∩ B = {1, 2, 4, 5} ∩ {6, 7, 9, 10} = ∅ Venn Diagram : U A∩B NAAC A+ Accredited University (6) A ∆ B = (A – B) ∪ (B – A) Now A – B = {1, 2, 4, 5} – {6, 7, 9, 10} = {1, 2, 4, 5} = A And B – A = {6, 7, 9, 10} – {1, 2, 4, 5} = {6, 7, 9, 10} = B Therefore A ∆ B = (A – B) ∪ (B – A) = A ∪ B = {1, 2, 4, 5} ∪ {6, 7, 9, 10} = {1, 2, 4, 5, 6, 7, 9, 10} Venn Diagram : U (7) Verify (B ∪ C)’ = B’ ∩ C’ L.H.S. = (B ∪ C)’ Now, B ∪ C = {6, 7, 9, 10} ∪ {1, 2, 9, 10} = {1, 2, 6, 7, 9, 10} Therefore (B ∪ C)’ = {3, 4, 5, 8} R.H.S = B’ ∩ C’ = {1, 2, 3, 4, 5, 8} ∩ {3, 4, 5, 6, 7, 8} = {3, 4, 5, 8} Thus, (B ∪ C)’ = B’ ∩ C’ NAAC A+ Accredited University Example : Let 𝕌 = {11, 12, 13, 14, 15, 16, 17, 18,19, 20}, A = {11, 13, 15, 18}, B = {12, 14, 16, 17, 18}, C = {18, 19, 20}. Then find the following: (i) A U B and its Venn Diagram (ii) B U C and its Venn Diagram (iii) P(A) (iv) P(C) (v) A’ – B’ (vi) B’ – C’ (vii) A Δ B (viii) C Δ B (ix) B ∩ C Solution : (i) A U B = {11, 13, 15, 18} U {12, 14, 16, 17, 18} = {11, 13, 15, 18, 12, 14, 16, 17} (iii) P(A) = {{ }, {11}, {13}, {15}, {18}, {11, 13}, {11, 15}, {11, 18}, {13, 15}, {13, 18}, {15, 18}, {11, 13, 15}, {11, 13, 18}, {13, 15, 18}, {11, 15, 18}, {11, 13, 15, 18}} (v) A’ = {12, 14, 16, 17, 19, 20} and B’ = {11, 13, 15, 19, 20} C’ = {11, 12,13, 14, 15, 16, 17} A’ – B’ = {12, 14, 16, 17, 19, 20} – {11, 13, 15, 19, 20} = {12, 14, 16, 17} B’ – A’ = {11, 13, 15} (vi) B’ – C’ = {11, 13, 15, 19, 20} – {11, 12, 13, 14, 15, 16, 17} = {19, 20} (vii) A Δ B = (A – B) ∪ (B – A) A – B = {11, 13, 15, 18} – {12, 14, 16, 17, 18} = {11, 13, 15} B – A = {12, 14, 16, 17, 18} – {11, 13, 15, 18} = {12, 14, 16, 17} A Δ B = {11, 13, 15} ∪ {12, 14, 16, 17} = {11, 13, 15, 12, 14, 16, 17} (viii) C Δ B = (C – B) ∪ (B – C) C – B = {18, 19, 20} – {12, 14, 16, 17, 18} = {19, 20} B – C = {12, 14, 16, 17, 18} – {18, 19, 20} = {12, 14, 16, 17} C Δ B = (C – B) ∪ (B – C) = {19, 20} ∪ {12, 14, 16, 17} = {19, 20, 12, 14, 16, 17} NAAC A+ Accredited University  Algebras Of Sets (1) Commutative Laws : (i) Union is commutative : A ∪ B = B ∪ A Let A = {1, 2, 3} and B = {3, 4, 5} L.H.S. = A ∪ B = {1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5} R.H.S. = B ∪ A = {3, 4, 5} ∪ {1, 2, 3} = {1, 2, 3, 4, 5} Thus, A ∪ B = B ∪ A i.e., Union is commutative. (ii) Intersection is commutative : A ∩ B = B ∩ A Let A = {1, 2, 3} and B = {3, 4, 5} L.H.S. = A ∩ B = {1, 2, 3} ∩ {3, 4, 5} = {3} R.H.S. = B ∩ A = {3, 4, 5} ∩ {1, 2, 3} = {3} Thus, A ∩ B = B ∩ A i.e., Intersection is commutative (2) Associative Laws : (i) Union is associative : A ∪ (B ∪ C) = (A ∪ B) ∪ C Consider A = {1, 2, 3, 4}, B = {2, 3, 5, 6} and C = {2, 4, 7} L.H.S. = A ∪ (B ∪ C) NAAC A+ Accredited University  = {1, 2, 3, 4} ∪ [{2, 3, 5, 6} ∪ {2, 4, 7}] = {1, 2, 3, 4} ∪ {2, 3, 4, 5, 6, 7} = {1, 2, 3, 4, 5, 6, 7} R.H.S. = (A ∪ B) ∪ C = [{1, 2, 3, 4} ∪ {2, 3, 5, 6}] ∪ {2, 4, 7} = {1, 2, 3, 4, 5, 6} ∪ {2, 4, 7} = {1, 2, 3, 4, 5, 6, 7} Thus, A ∪ (B ∪ C) = (A ∪ B) ∪ C i.e., Union is associative. (ii) Intersection is associative : A ∩ (B ∩ C) = (A ∩ B) ∩ C Consider A = {1, 2, 3, 4}, B = {2, 3, 5, 6} and C = {2, 4, 7} L.H.S. = A ∩ (B ∩ C) = {1, 2, 3, 4} ∩ [{2, 3, 5, 6} ∩ {2, 4, 7}] = {1, 2, 3, 4} ∩ {2} = {2} R.H.S. = (A ∩ B) ∩ C = [{1, 2, 3, 4} ∩ {2, 3, 5, 6}] ∩ {2, 4, 7} = {2, 3} ∩ {2, 4, 7} = {2} Thus, A ∩ (B ∩ C) = (A ∩ B) ∩ C i.e., Intersection is associative. (3) Distributive Laws : (i) Union is distributive over intersection : A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Consider A = {1, 2, 3, 4}, B = {2, 4, 5, 6}, C = {4, 5, 7} L.H.S. = A ∪ (B ∩ C) NAAC A+ Accredited University  = {1, 2, 3, 4} ∪ [{2, 4, 5, 6} ∩ {4, 5, 7}] = {1, 2, 3, 4} ∪ {4, 5} = {1, 2, 3, 4, 5} R.H.S. = (A ∪ B) ∩ (A ∪ C) = [{1, 2, 3, 4} ∪ {2, 4, 5,6}] ∩ [{1, 2, 3, 4} ∪ {4, 5, 7}] = {1, 2, 3, 4, 5, 6} ∩ {1, 2, 3, 4, 5, 7} = {1, 2, 3, 4, 5} Thus, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) i.e., Union is distributive over intersection. (ii) Intersection is distributive over union : A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Consider A = {1, 2, 3, 4}, B = {2, 4, 5, 6}, C = {4, 5, 7} L.H.S. = A ∩ (B ∪ C) = {1, 2, 3, 4} ∩ [{2, 4, 5, 6} ∪ {4, 5, 7}] = {1, 2, 3, 4} ∩ {2, 4, 5, 6, 7} = {2, 4} R.H.S. = (A ∩ B) ∪ (A ∩ C) = [{1, 2, 3, 4} ∩ {2, 4, 5, 6}] ∪ [{1, 2, 3, 4} ∩ {4, 5, 7}] = {2, 4} ∪ {4} = {2, 4} Thus, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) i.e., Intersection is distributive over union. De Morgan’s Laws : Let 𝕌 be the Universal set and A and B are any two subsets of 𝕌 then, (i) (A ∪ B)’ = A’ ∩ B’ Consider 𝕌 = {1, 2, 3, 4, 5, 6, 7}, A = {1, 2, 3, 4} and B = {3, 4, 5} NAAC A+ Accredited University A ∪ B = {1, 2, 3, 4} ∪ {3, 4, 5} = {1, 2, 3, 4, 5} L.H.S. = (A ∪ B)’ = 𝕌 – (A ∪ B) = {1, 2, 3, 4, 5, 6, 7} – {1, 2, 3, 4, 5} = {6, 7} A’ = {5, 6, 7} and B’ = {1, 2, 6, 7} R.H.S. = A’ ∩ B’ = {5, 6, 7} ∩ {1, 2, 6, 7} = {6, 7} Thus, (A ∪ B)’ = A’ ∩ B’ (ii) (A ∩ B)’ = A’ ∪ B’ Consider 𝕌 = {1, 2, 3, 4, 5, 6, 7}, A = {1, 2, 3, 4} and B = {3, 4, 5} A ∩ B = {1, 2, 3, 4} ∩ {3, 4, 5} = {3, 4} L.H.S. = (A ∩ B)’ = 𝕌 – (A ∩ B) = {1, 2, 3, 4, 5, 6, 7} – {3, 4} = {1, 2, 5, 6, 7} A’ = {5, 6, 7}, B’ = {1, 2, 6, 7} R.H.S. = A’ ∪ B’ = {5, 6, 7} ∪ {1, 2, 6, 7} = {1, 2, 5, 6, 7} Thus, (A ∩ B)’ = A’ ∪ B’ Example : If A, B and C are three sets such that A ⊂ B then prove that : C – B ⊂ C – A Solution : A = {1, 2, 3}, B = {1, 2, 3, 4, 5} and C = {1, 4, 6, 7} L.H.S. = C – B NAAC A+ Accredited University  = {1, 4, 6, 7} – {1, 2, 3, 4, 5} = {6, 7} ----- (1) R.H.S. = C – A = {1, 4, 6, 7} – {1, 2, 3} = {4, 6, 7} ----- (2) Now, {4, 6} ⊂ {4, 6, 7} Thus, from (1) and (2), C – B ⊂ C – A Example : If A, B and C are any three sets then prove the following. A – (B ∪ C) = (A – B) ∩ (A – C) Solution : Let A = {1, 2, 3, 4}, B = {1, 3, 5} and C = {1, 5, 6} L.H.S. = A – (B ∪ C) = {1, 2, 3, 4} – [{1, 3, 5} ∪ {1, 5, 6}] = {1, 2, 3, 4} – {1, 3, 5, 6} = {2, 4} R.H.S. = (A – B) ∩ (A – C) = [{1, 2, 3, 4} – {1, 3, 5}] ∩ [{1, 2, 3, 4} – {1, 5, 6} = {2, 4} ∩ {2, 3, 4} = {2, 4} Thus, A – (B ∪ C) = (A – B) ∩ (A – C) Example : If A, B and C are any three sets then prove the following. A – (B ∩ C) = (A – B) ∪ (A – C) Solution : A = {1, 2, 3, 4}, B = {3, 4, 5, 6} and C = {1, 5, 7} L.H.S. = A – (B ∩ C) = {1, 2, 3, 4} – [{3, 4, 5, 6} ∩ {1, 5, 7}] = {1, 2, 3, 4} – {5} NAAC A+ Accredited University  = {1, 2, 3, 4} R.H.S. = (A – B) ∪ (A – C) = [{1, 2, 3, 4} – {3, 4, 5, 6}] ∪ [{1, 2, 3, 4} – {1, 5, 7}] = {1, 2} ∪ {2, 3, 4} = {1, 2, 3, 4} Thus, A – (B ∩ C) = (A – B) ∪ (A – C) Some Important Results on Cardinality of finite sets : (1) n (A ∪ B) = n (A) + n (B) – n (A ∩ B) Example : A = {1, 2, 3, 4} B = {3, 4, 5, 6} Thus, A ∩ B = {3, 4} and A ∪ B = {1, 2, 3, 4, 5, 6} n (A ∪ B) = 6 n (A) + n (B) – n (A ∩ B) = 4 + 4 – 2 = 6 (2) n (A ∪ B) = n (A) + n (B), if A and B are disjoint sets Example : Take A = {1, 2, 3} and B = {4, 5} which are disjoint. Here A ∪ B = {1, 2, 3, 4, 5} n (A ∪ B) = 5 n (A) + n (B) = 3 + 2 = 5 (3) n (A – B) = n (A) – n (A ∩ B) Example : A = {1, 2, 3, 4, 5} and B = {3, 5, 7, 8} A – B = {1, 2, 3, 4, 5} – {3, 5, 7, 8} = {1, 2, 4}, A ∩ B = {3, 5} n (A – B) = 3 n (A) – n (A ∩ B) = 5 – 2 = 3 Also, n (B – A) = n (B) – n (A ∩ B) NAAC A+ Accredited University Example : Let 𝕌 be the universal set and A and B are two subsets of 𝕌 such that n (𝕌) = 700, n (A) = 200, n (B) = 300 and n (A ∩ B) = 100. Then find n (A’ ∩ B’). Solution : By De Morgan’s law we have (A ∪ B)’ = A’ ∩ B’ ∴ n (A ∪ B)’ = n (A’ ∩ B’) ∴ n (A ∪ B)’ = n (𝕌) – n (A ∪ B) = n (𝕌) – [n (A) + n (B) – n (A ∩ B)] = 700 – [200 + 300 – 100] = 700 – 400 ∴ n (A’ ∩ B’) = 300 Example : In a class of 35 students, 17 have taken mathematics, 10 have taken mathematics but not physics. Find the number of students who have taken both physics and mathematics and also find the number of students who have taken physics but not mathematics. It is given that each student has taken either mathematics or physics. Solution : Let M denotes the set of students who has taken Mathematics and P denotes the set of students who has taken Physics. So, we have n (M ∪ P) = 35, n (M) = 17 and n (M – P) = 10 We know that, n (M – P) = n (M) – n (M ∩ P) ∴ 10 = 17 – n (M ∩ P) ∴ n (M ∩ P) = 17 – 10 = 7 Therefore, 7 students have taken both Physics and Mathematics. Now, n (P – M) = n (P) – n (M ∩ P) So first we have to find n (P) We know that n (M ∪ P) = n (M) + n (P) – n (M ∩ P) ∴ 35 = 17 + n (P) – 7 NAAC A+ Accredited University ∴ 35 = 10 + n (P) ∴ n (P) = 25 Now, n (P – M) = n (P) – n (M ∩ P) ∴ n (P – M) = 25 – 7 ∴ n (P – M) = 18 Therefore, 18 students have taken Physics but not Mathematics. Cartesian product of two sets : Let A and B are two sets. A set containing all possible pairs (x, y) where x ∈ A and y ∈ B is called Cartesian product of A and B. Notation : A × B A × B = {(x, y) | x ∈ A and y ∈ B} Note: (i) If A and B are different sets then A × B ≠ B × A but n (A × B) = n (B × A). (ii) n (A × B) = n (B × A) = n (A) × n (B) Example : Let A = {1, 2, 3} and B = {a, b, c, d}. Then find A × B and B × A. A × B = {1, 2, 3} × {a, b, c, d} = {(1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2, d), (3, a), (3, b), (3, c), (3, d)} B × A = {a, b, c, d} × {1, 2, 3} = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3), (d, 1), (d, 2), (d, 3)} Example : Let A = {1, 2, 3, 4} and B= {1, 4, 5} then find (i) A × B (ii) B × A (iii) (A × B) ∩ (B × A) (i) A × B = {1, 2, 3, 4} × {1, 4, 5} = {(1, 1), (1, 4), (1, 5), (2, 1), (2, 4), (2, 5), (3, 1), (3, 4), (3, 5), (4, 1), (4, 4), (4, 5)} (ii) B × A = {1, 4, 5} × {1, 2, 3, 4} = {(1, 1), (1, 2), (1, 3), (1, 4), (4, 1), (4, 2), (4, 3), (4, 4), (5, 1), (5, 2), (5, 3), (5, 4)} (iii) (A × B) ∩ (B × A) = {(1, 1), (1, 4), (4, 1), (4, 4)} NAAC A+ Accredited University NAAC A+ Accredited University