Question

If \( R_1 \) and \( R_2 \) be two equivalence relations on a set A, then prove that \( (R_1 \cap R_2) \) also be an equivalence relation on A.

Hint:

The structure of proofs involving intersections of sets with certain properties is often the same: assume an element belongs to the intersection, which means it belongs to both sets individually. Apply the known property to each set, and then conclude that the result must also belong to both sets, and therefore to the intersection.

Answer 1

Step 1: Understanding the Concept:
To prove that the intersection of two equivalence relations is also an equivalence relation, we must show that the intersection, \( R_1 \cap R_2 \), satisfies the three required properties: reflexivity, symmetry, and transitivity. We can use the fact that \( R_1 \) and \( R_2 \) individually satisfy these properties.
Step 2: Key Definitions:
- Reflexive: For all \( a \in A \), \( (a, a) \in R \).
- Symmetric: If \( (a, b) \in R \), then \( (b, a) \in R \).
- Transitive: If \( (a, b) \in R \) and \( (b, c) \in R \), then \( (a, c) \in R \).
- Intersection: \( (a, b) \in R_1 \cap R_2 \) means \( (a, b) \in R_1 \) and \( (a, b) \in R_2 \).
Step 3: Detailed Explanation:
1. Reflexivity of \( R_1 \cap R_2 \):
Let \( a \in A \). Since \( R_1 \) is an equivalence relation, it is reflexive, so \( (a, a) \in R_1 \). Similarly, since \( R_2 \) is reflexive, \( (a, a) \in R_2 \). Since \( (a, a) \) is in both \( R_1 \) and \( R_2 \), by the definition of intersection, \( (a, a) \in R_1 \cap R_2 \).
Thus, \( R_1 \cap R_2 \) is reflexive.
2. Symmetry of \( R_1 \cap R_2 \):
Let \( (a, b) \in R_1 \cap R_2 \). This implies \( (a, b) \in R_1 \) and \( (a, b) \in R_2 \). Since \( R_1 \) is symmetric, \( (b, a) \in R_1 \). Since \( R_2 \) is symmetric, \( (b, a) \in R_2 \). As \( (b, a) \) is in both relations, it must be in their intersection: \( (b, a) \in R_1 \cap R_2 \).
Thus, \( R_1 \cap R_2 \) is symmetric.
3. Transitivity of \( R_1 \cap R_2 \):
Let \( (a, b) \in R_1 \cap R_2 \) and \( (b, c) \in R_1 \cap R_2 \). This means \( (a, b) \in R_1 \), \( (b, c) \in R_1 \), and also \( (a, b) \in R_2 \), \( (b, c) \in R_2 \).
Since \( R_1 \) is transitive, \( (a, b) \in R_1 \) and \( (b, c) \in R_1 \) implies \( (a, c) \in R_1 \).
Since \( R_2 \) is transitive, \( (a, b) \in R_2 \) and \( (b, c) \in R_2 \) implies \( (a, c) \in R_2 \).
Because \( (a, c) \) is in both \( R_1 \) and \( R_2 \), it must be in their intersection: \( (a, c) \in R_1 \cap R_2 \).
Thus, \( R_1 \cap R_2 \) is transitive.
Step 4: Final Answer:
Since \( R_1 \cap R_2 \) is reflexive, symmetric, and transitive, it is an equivalence relation. Hence proved.