Equivalence Relation (GATE Problems) - Set 1

Summary

This presentation explores gate problems concerning equivalence relations. Problem one involves a relation 'r' on sets where 'a r b' if 'a intersection b' equals an empty set, questioning the properties of 'r'. The solution reveals 'r' is symmetric but not reflexive or transitive. Problem two asks for the size of the largest equivalence relation on a finite set 'a' with 'n' elements, concluding it to be 'n squared', as the relation is the Cartesian product of 'a' with itself.

Takeaways

• 🔍 The presentation discusses gate problems related to equivalence relations.
• 📚 Problem one involves a non-empty relation 'r' on a collection of sets where a r b if and only if a intersection b equals an empty set.
• ❌ The relation 'r' is not reflexive because a intersection a cannot be an empty set.
• ⚖️ The relation 'r' is symmetric because if a is related to b (a intersection b is empty), then b is related to a (b intersection a is also empty).
• 🚫 The relation 'r' is not transitive as shown by an example where a intersection b and b intersection c are empty, but a intersection c is not.
• ✅ Option B is correct: 'r' is symmetric and not transitive.
• 🧩 Problem two asks about the number of elements in the largest equivalence relation of a finite set 'a' with n elements.
• 🔑 The largest equivalence relation of set 'a' is the Cartesian product 'a x a', which has n squared elements.
• 🎯 The correct answer to problem two is that the largest equivalence relation has n squared elements, making option B the correct choice.
• 👋 The presentation concludes with a thank you note and some celebratory music and applause.

Q & A

What is the relation 'r' defined on a collection of sets?

The relation 'r' is defined such that a r b if and only if the intersection of sets a and b is equal to the empty set (denoted as phi), meaning there are no common elements between sets a and b.

Why is the relation 'r' not reflexive?

The relation 'r' is not reflexive because for a set to be related to itself (a r a), the intersection of the set with itself (a intersection a) must be the empty set, which is not possible as the intersection of any set with itself is the set itself.

How is the symmetry of relation 'r' demonstrated?

The symmetry of relation 'r' is shown by proving that if a is related to b (a r b), then b must also be related to a (b r a). This is because if the intersection of a and b is empty, then the intersection of b and a must also be empty.

What is the example given to demonstrate that relation 'r' is not transitive?

The example given involves three sets: a = {1, 2, 3}, b = {4, 5}, and c = {1, 2}. It shows that while a is related to b and b is related to c (since their intersections are empty), a is not related to c because their intersection is not empty.

Why is the relation 'r' not transitive?

The relation 'r' is not transitive because even if a is related to b and b is related to c (a r b and b r c), it does not necessarily mean that a is related to c (a r c). The example with sets a, b, and c illustrates that a intersection b and b intersection c are empty, but a intersection c is not.

What is the largest equivalence relation of a finite set 'a' with 'n' elements?

The largest equivalence relation of a finite set 'a' with 'n' elements is the Cartesian product of the set with itself, denoted as a x a, which contains n^2 (n squared) elements.

How many elements are in the largest equivalence relation of a set?

The largest equivalence relation of a set has the same number of elements as the Cartesian product of the set with itself, which is the square of the number of elements in the set.

What is the significance of the empty set in defining the relation 'r'?

The significance of the empty set in defining the relation 'r' is that it ensures that there are no common elements between the sets involved in the relation, which is a critical property for the relation to hold.

How does the script encourage active learning from the audience?

The script encourages active learning by pausing at key points to allow the audience to attempt to answer the questions on their own before revealing the solutions.

What is the purpose of the example given in the script?

The purpose of the example given in the script is to provide a concrete illustration of the abstract concept of relations and their properties, making it easier for the audience to understand and visualize the concepts being discussed.