Discrete Mathematics previous year-GATE 2025 Equivalence relation Let R and S be any two equivalence.
Discrete Mathematics previous year-GATE 2025 Equivalence relation Let R and S be any two equivalence.
It looks like you are looking for Discrete Mathematics – Equivalence Relations – Previous Year GATE Questions related to GATE 2025. Here’s a conceptual breakdown along with a sample problem:
Contents
Equivalence Relation – Definition
A relation R on a set S is called an Equivalence Relation if it satisfies the following three properties:
- Reflexive: aRaaRa for all a∈Sa \in S.
- Symmetric: If aRbaRb, then bRabRa for all a,b∈Sa, b \in S.
- Transitive: If aRbaRb and bRcbRc, then aRcaRc for all a,b,c∈Sa, b, c \in S.
Example GATE Question on Equivalence Relations
Question:
Let R and S be two equivalence relations on a set AA. Consider the relation R∩SR \cap S (intersection of R and S). Is R∩SR \cap S also an equivalence relation?
Solution Approach:
- Reflexive: Since both RR and SS are reflexive, (a,a)(a, a) belongs to both RR and SS, so it must belong to R∩SR \cap S.
- Symmetric: If (a,b)∈R∩S(a, b) \in R \cap S, then (a,b)∈R(a, b) \in R and (a,b)∈S(a, b) \in S. Since both RR and SS are symmetric, (b,a)∈R(b, a) \in R and (b,a)∈S(b, a) \in S, so (b,a)∈R∩S(b, a) \in R \cap S.
- Transitive: If (a,b)∈R∩S(a, b) \in R \cap S and (b,c)∈R∩S(b, c) \in R \cap S, then (a,b)(a, b) and (b,c)(b, c) belong to both RR and SS. Since both RR and SS are transitive, (a,c)∈R(a, c) \in R and (a,c)∈S(a, c) \in S, so (a,c)∈R∩S(a, c) \in R \cap S.
- Conclusion: Since R∩SR \cap S satisfies all three properties, it is also an equivalence relation.
- Answer: Yes, R∩SR \cap S is always an equivalence relation.
Would you like more GATE previous year questions with solutions or a short trick to solve equivalence relation problems faster?