Question

If \(R_1\) and \(R_2\) are equivalence relations in the set A, prove that \(R_1 \cap R_2\) is also an equivalence relation in A.

Hint:

This property holds for the intersection of any number of equivalence relations. However, the union of two equivalence relations is not necessarily an equivalence relation (it is reflexive and symmetric, but may not be transitive).

Answer 1

Step 1: Understanding the Concept:
An equivalence relation is a binary relation that is reflexive, symmetric, and transitive. To prove that the intersection of two equivalence relations is also an equivalence relation, we must show that the intersection itself satisfies all three of these properties, assuming the original relations do.
Step 2: Key Formula or Approach:
Let \(R_1\) and \(R_2\) be two equivalence relations on a set A. Let \(R = R_1 \cap R_2\). We need to prove the following: 1. Reflexivity: For all \(a \in A\), \((a, a) \in R\). 2. Symmetry: If \((a, b) \in R\), then \((b, a) \in R\). 3. Transitivity: If \((a, b) \in R\) and \((b, c) \in R\), then \((a, c) \in R\).
Step 3: Detailed Explanation or Calculation:
1. Proof of Reflexivity:
Let \(a\) be an arbitrary element of A.
Since \(R_1\) is an equivalence relation, it is reflexive. Therefore, \((a, a) \in R_1\).
Since \(R_2\) is an equivalence relation, it is reflexive. Therefore, \((a, a) \in R_2\).
By the definition of intersection, since \((a, a)\) is in both \(R_1\) and \(R_2\), we have \((a, a) \in R_1 \cap R_2\).
Thus, \(R_1 \cap R_2\) is reflexive.
2. Proof of Symmetry:
Let \((a, b)\) be an arbitrary element of \(R_1 \cap R_2\).
This means \((a, b) \in R_1\) and \((a, b) \in R_2\).
Since \(R_1\) is symmetric, if \((a, b) \in R_1\), then \((b, a) \in R_1\).
Since \(R_2\) is symmetric, if \((a, b) \in R_2\), then \((b, a) \in R_2\).
Because \((b, a)\) is in both \(R_1\) and \(R_2\), it must be in their intersection: \((b, a) \in R_1 \cap R_2\).
Thus, \(R_1 \cap R_2\) is symmetric.
3. Proof of Transitivity:
Let \((a, b) \in R_1 \cap R_2\) and \((b, c) \in R_1 \cap R_2\).
From \((a, b) \in R_1 \cap R_2\), we know \((a, b) \in R_1\) and \((a, b) \in R_2\).
From \((b, c) \in R_1 \cap R_2\), we know \((b, c) \in R_1\) and \((b, c) \in R_2\).
Now consider \(R_1\): We have \((a, b) \in R_1\) and \((b, c) \in R_1\). Since \(R_1\) is transitive, it follows that \((a, c) \in R_1\).
Now consider \(R_2\): We have \((a, b) \in R_2\) and \((b, c) \in R_2\). Since \(R_2\) is transitive, it follows that \((a, c) \in R_2\).
Since \((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 in the set A.