Example 18: The intersection of two equivalence relations

Basics you need

Solution

1. What it means to be in $R_1 \cap R_2$

   Write $R = R_1 \cap R_2$⁠. Since $R_1$ and $R_2$ are both subsets of $A\times A$⁠, so is $R$⁠: it is a relation in $A$⁠. By the meaning of intersection,

   $$(a,b) \in R_1\cap R_2 \iff (a,b) \in R_1 \ \text{ and } \ (a,b) \in R_2.$$
   Every property we need to check is about which pairs belong to $R$⁠. This equivalence lets us translate a statement about $R$ into two statements, one about $R_1$ and one about $R_2$⁠, where we know the properties hold. It also works backwards: if a pair is in both, it is in $R$⁠. Every step below uses the backward direction to reach its conclusion, and the symmetric and transitive steps also use the forward direction on their starting assumption.
   Intersection means "in both" (Basic 2). A subset of $A\times A$ is a relation in $A$ (Basic 1).

2. Reflexive

   Let $a$ be any element of $A$⁠. Since $R_1$ is reflexive, $(a,a)\in R_1$⁠. Since $R_2$ is reflexive, $(a,a)\in R_2$⁠. So $(a,a)$ is in both, that is

   $$(a,a)\in R_1\cap R_2 \quad\text{for every } a\in A.$$

   Hence $R_1\cap R_2$ is reflexive.

   We need $(a,a)$ in the intersection, which by Step 1 means in $R_1$ and in $R_2$⁠. Each of those is given directly by the reflexivity of that relation. Because $a$ was an arbitrary element, the conclusion holds for all of $A$⁠.
   Reflexive: every element is related to itself (Basic 3).

3. Symmetric

   Suppose $(a,b)\in R_1\cap R_2$⁠. Then

   $$\begin{aligned} &(a,b)\in R_1 \text{ and } (a,b)\in R_2\\ \Longrightarrow\ &(b,a)\in R_1 \text{ and } (b,a)\in R_2\\ \Longrightarrow\ &(b,a)\in R_1\cap R_2. \end{aligned}$$

   The first arrow uses symmetry of $R_1$ on the first part and symmetry of $R_2$ on the second part. Hence $R_1 \cap R_2$ is symmetric.

   This is the "split, apply, join" move. Split: the pair is in each relation. Apply: each relation is symmetric, so each contains the reversed pair. Join: the reversed pair is in both, so in the intersection. We start from the "if" part, $(a,b)\in R_1 \cap R_2$⁠, as every proof of an "if … then" statement must.
   Symmetric: $(a,b)\in R \Rightarrow (b,a)\in R$ (Basic 3).

4. Transitive

   Suppose $(a,b)\in R_1\cap R_2$ and $(b,c)\in R_1\cap R_2$⁠. Look at $R_1$ and $R_2$ separately.

   • In $R_1$⁠: both $(a,b)\in R_1$ and $(b,c)\in R_1$⁠. Since $R_1$ is transitive, $(a,c)\in R_1$⁠.
   • In $R_2$⁠: both $(a,b)\in R_2$ and $(b,c)\in R_2$⁠. Since $R_2$ is transitive, $(a,c)\in R_2$⁠.

   So $(a,c)\in R_1$ and $(a,c)\in R_2$⁠, which gives $(a,c)\in R_1 \cap R_2$⁠. Hence $R_1\cap R_2$ is transitive.

   Transitivity of $R_1$ needs both links, $(a,b)$ and $(b,c)$⁠, to be in $R_1$⁠. We have that, because each link is in the intersection and so in $R_1$⁠. The same holds for $R_2$⁠. This is the step where the intersection matters: for a union it would break, because the two links might come from different relations (see Step 6).
   Transitive: $(a,b), (b,c)\in R \Rightarrow (a,c)\in R$ (Basic 3).

5. Conclude, and see it on a small example

   $R_1\cap R_2$ is reflexive, symmetric and transitive, so $R_1 \cap R_2$ is an equivalence relation in $A$.

   To see what this means, take $A = \{1,2,3,4\}$ with the equivalence relations whose classes are

   $$R_1:\ \{1,2\},\ \{3,4\} \qquad\qquad R_2:\ \{1,2,3\},\ \{4\}.$$

   Two elements are related by $R_1\cap R_2$ when they share a class in both. The pair $1,2$ does; $3,4$ does not (separated by $R_2$⁠); $1,3$ does not (separated by $R_1$⁠). So the classes of $R_1\cap R_2$ are $\{1,2\},\ \{3\},\ \{4\}$⁠, and

   $$R_1\cap R_2 = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)\}.$$
   The proof is general, but a concrete case shows what the intersection does: it keeps two elements together only if both relations keep them together. The resulting pieces are the non-empty overlaps of a class of $R_1$ with a class of $R_2$⁠. Here $\{1,2\}\cap\{1,2,3\} = \{1,2\}$⁠, $\{3,4\}\cap\{1,2,3\} = \{3\}$ and $\{3,4\}\cap\{4\} = \{4\}$⁠.
   An equivalence relation's classes are disjoint and cover the whole set. Basics: equivalence classes

6. Why the same is not true for $R_1 \cup R_2$

   The book does not ask this, but it explains why the proof needs "and". Take $A = \{1,2,3\}$⁠, $R_1$ with classes $\{1,2\},\{3\}$ and $R_2$ with classes $\{1\},\{2,3\}$⁠. Then $R_1\cup R_2$ contains $(1,2)$ (from $R_1$⁠) and $(2,3)$ (from $R_2$⁠), but not $(1,3)$⁠, which is in neither. So $R_1\cup R_2$ is not transitive, and not an equivalence relation.

   The union is still reflexive and symmetric (the same "split, apply" argument works with "or"). It is transitivity that fails, because the two links of the chain may come from different relations, and neither relation alone then guarantees the direct link. This one counterexample is enough to show that "the union of equivalence relations is an equivalence relation" is false in general.
   One counterexample disproves a general claim. Basics: proving and disproving

Every fact used, and where it comes from