If $A$ and $B$ are two equivalence relations defined on set $C$, then which of the following is always true?
Step-by-Step Solution
Key Concept: Intersection of equivalence relations is always an equivalence relation; union of equivalence relations need not be (transitivity can fail).
Step 1: Understand what we need to verify for equivalence relations.
An equivalence relation must satisfy three properties: reflexivity, symmetry, and transitivity. We need to check whether $A \cap B$ and $A \cup B$ preserve these properties when $A$ and $B$ are both equivalence relations on set $C$.
Step 2: Verify reflexivity of $A \cap B$.
For any element $x \in C$, since $A$ is reflexive, we have $(x,x) \in A$. Similarly, since $B$ is reflexive, we have $(x,x) \in B$. Therefore, $(x,x) \in A \cap B$. This shows $A \cap B$ is reflexive. ✓
Step 3: Verify symmetry of $A \cap B$.
Suppose $(x,y) \in A \cap B$. This means $(x,y) \in A$ and $(x,y) \in B$. Since $A$ is symmetric, $(y,x) \in A$. Since $B$ is symmetric, $(y,x) \in B$. Therefore, $(y,x) \in A \cap B$. This shows $A \cap B$ is symmetric. ✓
Step 4: Verify transitivity of $A \cap B$.
Suppose $(x,y) \in A \cap B$ and $(y,z) \in A \cap B$. This means $(x,y), (y,z) \in A$ and $(x,y), (y,z) \in B$. Since $A$ is transitive, $(x,z) \in A$. Since $B$ is transitive, $(x,z) \in B$. Therefore, $(x,z) \in A \cap B$. This shows $A \cap B$ is transitive. ✓
Step 5: Conclude that $A \cap B$ is an equivalence relation.
Since $A \cap B$ satisfies reflexivity, symmetry, and transitivity, it is always an equivalence relation.
Step 6: Check whether $A \cup B$ is an equivalence relation.
Consider a counterexample: Let $C = \{1, 2, 3\}$, and define:
$$A = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$$
$$B = \{(1,1), (2,2), (3,3), (2,3), (3,2)\}$$
Both $A$ and $B$ are equivalence relations on $C$.
Step 7: Verify the counterexample fails transitivity for $A \cup B$.
We have $(1,2) \in A \subseteq A \cup B$ and $(2,3) \in B \subseteq A \cup B$. However, $(1,3) \notin A$ and $(1,3) \notin B$, so $(1,3) \notin A \cup B$. This violates transitivity, so $A \cup B$ is not necessarily an equivalence relation.
Step 8: State the final answer.
Since $A \cap B$ is always an equivalence relation when $A$ and $B$ are equivalence relations, the correct answer is **Option 1: $A \cap B$ is an equivalence relation**.
Correct Answer: 3