21 Oct - DM -Equivalence Relations Part - 2
Duration: 2 hr 18 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
This comprehensive lecture covers the fundamental concepts of Equivalence Relations and Partitions in Discrete Mathematics. The instructor begins by defining an equivalence relation as a relation that is reflexive, symmetric, and transitive. Through a series of detailed examples involving sets of natural numbers and modular arithmetic, the lecture demonstrates how to verify these three properties. Key topics include the analysis of relations defined by conditions such as |a-b| <= 2, a+b being even, and modular congruences. The session transitions to the properties of equivalence relations under set operations, proving that the intersection of equivalence relations is always an equivalence relation, while the union is not necessarily so. The concept of Bell's Triangle is introduced to calculate the number of possible equivalence relations on a finite set. Finally, the lecture connects equivalence relations to partitions, defining equivalence classes and solving GATE examination problems to reinforce the theoretical concepts.
Chapters
0:00 – 2:00 00:00-02:00
The video begins with a title card displaying the name 'Sanchit Jain' against a black background. This introductory segment sets the stage for the lecture, identifying the instructor before the main content begins. The screen remains static, serving as a placeholder for the start of the educational session.
2:00 – 5:00 02:00-05:00
The lecture formally introduces the topic 'Equivalence Relation'. The slide defines a relation R on a set A as an equivalence relation if it satisfies three specific properties: Reflexive, Symmetric, and Transitive. The instructor writes these terms on the board and underlines them for emphasis. An example is introduced with a set A = {1, 2, 3, 4} and a relation R = {(1,1), (2,2), (3,3)}. The instructor begins to analyze this example, noting that it is reflexive because (1,1), (2,2), and (3,3) are present, although (4,4) is missing, which might be a point of discussion for reflexivity on the full set.
5:00 – 10:00 05:00-10:00
The instructor presents a list of relations to check for equivalence properties. The first example is R = {(a,b)/aRb where |a-b| <= 2}. The second is R = {(a,b)/aRb where a+b = even}. The third is R = {(a,b)/aRb where a+b = odd}. The instructor writes these on the board and begins to discuss the conditions. For the second example, the instructor notes that if a+b is even, then b+a is also even, suggesting symmetry. The discussion focuses on verifying the three properties for each of these specific relations.
10:00 – 15:00 10:00-15:00
The list of relations continues with more complex modular arithmetic conditions. Example 4 is R = {(a,b)/aRb where |a+b|mod2=0, for all a,b in N}. Example 5 is R = {(a,b)/aRb where |a+b|mod4=0, for all a,b in N}. Example 6 is R = {(a,b)/aRb where |a-b|mod2=0, for all a,b in N}. Example 7 is R = {(a,b)/aRb where |a-b|mod4=0, for all a,b in N}. The instructor highlights these examples as the core problems to be solved in the lecture, emphasizing the need to check reflexivity, symmetry, and transitivity for each.
15:00 – 20:00 15:00-20:00
The instructor begins a detailed analysis of Example 4: R = {(a,b)/aRb where |a+b|mod2=0}. He writes out the set N x N and checks for reflexivity. He notes that for any a, a+a = 2a, which is even, so 2a mod 2 = 0. Thus, the relation is reflexive. He then checks symmetry: if a+b is even, then b+a is even, so it is symmetric. Finally, he checks transitivity: if a+b is even and b+c is even, then (a+b)+(b+c) = a+2b+c is even. Since 2b is even, a+c must be even. Therefore, the relation is transitive. He concludes that Example 4 is an equivalence relation.
20:00 – 25:00 20:00-25:00
The lecture moves to Example 5: R = {(a,b)/aRb where |a+b|mod4=0}. The instructor checks reflexivity first. He tests (1,1) where 1+1=2. 2 mod 4 is not 0. Thus, the relation is not reflexive. Since it fails reflexivity, it cannot be an equivalence relation. He then checks symmetry: if a+b is divisible by 4, then b+a is divisible by 4, so it is symmetric. He then checks transitivity with an example: (1,3) and (3,5). 1+3=4 (divisible by 4) and 3+5=8 (divisible by 4). However, 1+5=6, which is not divisible by 4. Thus, it is not transitive. He concludes it is not an equivalence relation.
25:00 – 30:00 25:00-30:00
The instructor analyzes Example 6: R = {(a,b)/aRb where |a-b|mod2=0}. He checks reflexivity: a-a = 0, and 0 mod 2 = 0, so it is reflexive. For symmetry, if a-b is divisible by 2, then b-a = -(a-b) is also divisible by 2, so it is symmetric. For transitivity, if a-b is even and b-c is even, then (a-b)+(b-c) = a-c is even. Thus, it is transitive. He concludes that Example 6 is an equivalence relation. He also notes that this is equivalent to saying a and b have the same parity (both even or both odd).
30:00 – 35:00 30:00-35:00
The lecture covers Example 7: R = {(a,b)/aRb where |a-b|mod4=0}. The instructor checks reflexivity: a-a=0, 0 mod 4 = 0, so it is reflexive. Symmetry: if a-b is divisible by 4, then b-a is divisible by 4, so it is symmetric. Transitivity: if a-b is divisible by 4 and b-c is divisible by 4, then (a-b)+(b-c) = a-c is divisible by 4. Thus, it is transitive. He concludes that Example 7 is an equivalence relation. He writes down the checkmarks for Reflexive, Symmetric, and Transitive for this example.
35:00 – 40:00 35:00-40:00
The instructor moves to 'Important Points of Equivalence Relation'. He poses two questions. 1. Is the Union of two or more equivalence relations also an equivalence relation? He writes 'NO' and explains that it may or may not be. 2. Is the Intersection of two or more equivalence relations also an equivalence relation? He writes 'Yes'. He begins to set up a counterexample for the union property using a set A = {1, 2, 3, 4, 5, 6}.
40:00 – 45:00 40:00-45:00
The instructor provides a counterexample for the union of equivalence relations. He defines R1 = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (2,3), (3,2)} and R2 = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (2,1), (1,2)}. Both are equivalence relations. He considers R1 U R2. He notes that (2,3) is in R1 and (3,1) is in R2 (wait, he corrects this to (1,2) in R2). He shows that (2,3) is in the union and (3,1) is not directly in the union but he constructs a case where transitivity fails. He writes (2,3) and (3,2) in R1 and (2,1) and (1,2) in R2. He shows that (2,3) and (3,2) are in the union, but (2,2) is there. He then shows a case where (2,3) and (3,1) might be in the union but (2,1) is not, breaking transitivity. He concludes the union is not necessarily an equivalence relation.
45:00 – 50:00 45:00-50:00
The instructor proves that the intersection of two equivalence relations is an equivalence relation. He defines R1 and R2 as equivalence relations on set A. He shows that for the intersection R1 n R2, reflexivity holds because (a,a) is in both R1 and R2. Symmetry holds because if (a,b) is in both, then (b,a) is in both. Transitivity holds because if (a,b) and (b,c) are in both, then (a,c) is in both. He writes down the intersection R1 n R2 = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)} for his previous example, which is clearly an equivalence relation.
50:00 – 55:00 50:00-55:00
The topic shifts to 'Bell's Triangle'. The instructor asks how many equivalence relations are possible on a set A = {1, 2, 3, 4, 5}. He explains that this is related to the number of partitions of the set. He introduces Bell's Triangle as a method to calculate the number of partitions (Bell numbers). He starts drawing the triangle on the board, beginning with the number 1 at the top.
55:00 – 60:00 55:00-60:00
The instructor continues constructing Bell's Triangle. He writes the numbers for n=1 to n=5. For n=1, the number is 1. For n=2, the numbers are 1, 2. For n=3, the numbers are 2, 3, 5. For n=4, the numbers are 5, 7, 10, 15. For n=5, the numbers are 15, 20, 27, 37, 52. He explains that the last number in each row represents the Bell number Bn, which is the total number of partitions of a set with n elements. For n=5, the answer is 52.
60:00 – 65:00 60:00-65:00
The instructor discusses the properties of symmetric relations. He asks if the union of two symmetric relations is symmetric. He writes { (a,b), (b,a) } U { (c,d), (d,c) }. He concludes that the union is symmetric because if (x,y) is in the union, it must be in one of the relations, and since that relation is symmetric, (y,x) is also in that relation, and thus in the union. He marks this as a true statement.
65:00 – 70:00 65:00-70:00
The instructor discusses the properties of transitive relations. He asks if the union of two transitive relations is transitive. He provides a counterexample. Let R1 = { (1,2), (2,1), (1,1), (2,2) } which is transitive. Let R2 = { (2,3), (3,2), (2,2), (3,3) } which is transitive. The union contains (1,2) and (2,3). For transitivity, (1,3) must be in the union. However, (1,3) is not in R1 or R2. Thus, the union is not transitive. He concludes that the union of transitive relations is not necessarily transitive.
70:00 – 75:00 70:00-75:00
The lecture introduces 'Equivalence Class'. The slide states that the set of all distinct equivalence classes of A define a partition of a set A. The instructor explains that an equivalence class [a] is the set of all elements in A that are related to a. He writes down Example 1: How many equivalence classes? A = {1, 2, 3, 4, 5} and R = {(1,1), (2,2), (3,3), (4,4), (5,5), (1,4), (4,1), (2,5), (5,2)}. He begins to find the classes for each element.
75:00 – 80:00 75:00-80:00
The instructor solves Example 1. He finds [1] = {1, 4} because (1,1) and (1,4) are in R. He finds [2] = {2, 5} because (2,2) and (2,5) are in R. He finds [3] = {3} because only (3,3) is in R. He finds [4] = {1, 4} which is the same as [1]. He finds [5] = {2, 5} which is the same as [2]. He concludes there are 3 distinct equivalence classes: {1, 4}, {2, 5}, and {3}. He writes that the union of these classes is the set A.
80:00 – 85:00 80:00-85:00
The instructor moves to Example 2: How many equivalence classes? A = {1, 2, 3, 4} and R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4), (4,3)}. He finds [1] = {1, 2}. He finds [2] = {1, 2}. He finds [3] = {3, 4}. He finds [4] = {3, 4}. He concludes there are 2 distinct equivalence classes: {1, 2} and {3, 4}. He writes '2 equivalence classes' on the board.
85:00 – 90:00 85:00-90:00
The instructor presents Example 3: How many equivalence classes? A = {1, 2, 3, 4} and R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (1,3), (2,1), (3,2), (3,1)}. He finds [1] = {1, 2, 3} because 1 is related to 2 and 3. He finds [2] = {1, 2, 3}. He finds [3] = {1, 2, 3}. He finds [4] = {4}. He concludes there are 2 distinct equivalence classes: {1, 2, 3} and {4}. He writes '2 equivalence classes' on the board.
90:00 – 95:00 90:00-95:00
The instructor discusses Example 4: N = {1, 2, 3, 4, 5, 6, 7, 8... n} and R = {(a,b)/aRb where a+b = even, for all a,b in N}. He states this is an equivalence relation. He finds the equivalence class [1]. Since 1 is odd, 1+b must be even, so b must be odd. Thus [1] = {1, 3, 5, 7, 9, 11...}. He finds the equivalence class [2]. Since 2 is even, 2+b must be even, so b must be even. Thus [2] = {2, 4, 6, 8, 10...}. He concludes there are only 2 equivalence classes: the set of odd numbers and the set of even numbers.
95:00 – 100:00 95:00-100:00
The instructor discusses Example 5: N = {1, 2, 3, 4, 5, 6, 7, 8... n} and R = {(a,b)/aRb where |a+b|mod4=0, for all a,b in N}. He states this is NOT an equivalence relation. He gives a counterexample for transitivity: (1,3) is in R because 1+3=4. (3,5) is in R because 3+5=8. But (1,5) is not in R because 1+5=6, which is not divisible by 4. He crosses out the example and moves to the next one.
100:00 – 105:00 100:00-105:00
The instructor corrects Example 5 to R = {(a,b)/aRb where |a-b|mod4=0, for all a,b in N}. He states this IS an equivalence relation. He finds the equivalence classes. [1] = {1, 5, 9, 13, 17...} (numbers congruent to 1 mod 4). [2] = {2, 6, 10, 14, 18...} (numbers congruent to 2 mod 4). [3] = {3, 7, 11, 15, 19...} (numbers congruent to 3 mod 4). [4] = {4, 8, 12, 16, 20...} (numbers congruent to 0 mod 4). He concludes there are 4 equivalence classes.
105:00 – 110:00 105:00-110:00
The lecture covers 'Partition of set'. The slide defines a partition of S as a sub-division of S into non-overlapping, non-empty subsets such that A1 U A2 U ... U An = S and Ai intersect Aj = phi if i != j. The instructor gives an example: If A = {a, b, c, d, e}, then P1 = {{a,c}, {b,e}, {d}} and P2 = {{a}, {b}, {c,d,e}} are valid partitions. He emphasizes the two conditions: union must be the whole set, and intersection must be empty.
110:00 – 115:00 110:00-115:00
The instructor presents an example problem: A = {1, 2, 3, 4, 5} and Partition = {{1,3}, {2,4,5}}. He asks to find the equivalence relation on A. He writes down the relation R. Since {1,3} is a class, (1,1), (3,3), (1,3), (3,1) are in R. Since {2,4,5} is a class, (2,2), (4,4), (5,5), (2,4), (4,2), (2,5), (5,2), (4,5), (5,4) are in R. He writes out the full set of ordered pairs for R.
115:00 – 120:00 115:00-120:00
The instructor discusses GATE Question 2.79. Let R be a relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. He asks which statement is true. He checks reflexivity: aRa requires a and a to be distinct, which is false. So it is not reflexive. He checks symmetry: if a and b have a common divisor, then b and a have a common divisor. So it is symmetric. He checks transitivity: (4,12) and (12,9). 4 and 12 share 2, 12 and 9 share 3. But 4 and 9 do not share a common divisor > 1. So it is not transitive. He concludes it is symmetric but not reflexive and not transitive.
120:00 – 125:00 120:00-125:00
The instructor discusses GATE Question 2.45. Let R and S be any two equivalence relations on a non-empty set A. He asks which statement is true. He reviews the options: (a) R n S, R U S are both equivalence relations. (b) R U S is an equivalence relation. (c) R n S is an equivalence relation. (d) Neither R U S nor R n S is an equivalence relation. He recalls that the intersection of equivalence relations is always an equivalence relation, while the union is not necessarily so. He selects option (c).
125:00 – 130:00 125:00-130:00
The instructor discusses GATE Question 2.32. The binary relation S = {empty set} on set A = {1, 2, 3}. He asks for the properties of S. Since S is empty, it has no elements. Reflexivity requires (1,1), (2,2), (3,3) to be in S, which they are not. So it is not reflexive. Symmetry requires if (a,b) in S then (b,a) in S. Since there are no elements, the condition is vacuously true. So it is symmetric. Transitivity requires if (a,b) and (b,c) in S then (a,c) in S. Since there are no elements, the condition is vacuously true. So it is transitive. He concludes it is symmetric and transitive.
130:00 – 135:00 130:00-135:00
The instructor discusses GATE Question 2.16. Let R be a non-empty relation on a collection of sets defined by A R B if and only if A intersect B = phi. He asks to pick the true statement. He checks reflexivity: A intersect A = A. For A intersect A to be phi, A must be phi. Since the collection is non-empty and contains sets, it's not necessarily reflexive. He checks symmetry: if A intersect B = phi, then B intersect A = phi. So it is symmetric. He checks transitivity: if A intersect B = phi and B intersect C = phi, does A intersect C = phi? No, A and C could overlap. So it is not transitive. He concludes it is symmetric and not transitive.
135:00 – 137:47 135:00-137:47
The instructor concludes the lecture by reviewing the properties of the relation in Question 2.16. He reiterates that A R B means A and B are disjoint. He confirms that the relation is symmetric because disjointness is a symmetric property. He confirms it is not transitive because disjointness is not transitive (A disjoint from B, B disjoint from C does not imply A disjoint from C). He confirms it is not reflexive because a set is not disjoint from itself unless it is empty. He selects the option 'R is symmetric and not transitive'.
The lecture provides a thorough exploration of equivalence relations, starting with the fundamental definition requiring reflexivity, symmetry, and transitivity. Through a series of progressively complex examples involving modular arithmetic and set conditions, the instructor demonstrates how to verify these properties. A significant portion is dedicated to the behavior of equivalence relations under set operations, proving that intersection preserves the equivalence property while union does not. The concept of Bell's Triangle is introduced as a combinatorial tool to count the number of possible equivalence relations on a finite set. The lecture culminates in the connection between equivalence relations and partitions, defining equivalence classes and solving practical problems, including GATE examination questions, to solidify understanding of these abstract concepts.