Question

Give an example to show that the union of two equivalence relations on a set A need not be an equivalence relation on A.

Answer 1

Hint: Recall the definition of an equivalence relation. Consider two relations ${{R}_{1}}$ and ${{R}_{2}}$ on the set of integers defined as $a{{R}_{1}}b\Leftrightarrow 5|b-a$ and $a{{R}_{2}}b\Leftrightarrow 7|b-a$. Argue that ${{R}_{1}}$ and ${{R}_{2}}$ are equivalence relations in $\mathbb{Z}$ but ${{R}_{1}}\bigcup {{R}_{2}}$ is not. Hence prove that the union of two equivalence relations may not be an equivalence relation.

Complete step-by-step answer:
Before solving the question, we need to understand what is an equivalence relation.
Reflexive relation: A relation R on a set “A” is said to be reflexive if $\forall a\in A$ we have $aRa$.
Symmetric relation: A relation R on a set “A” is said to be symmetric if $aRb\Rightarrow bRa$
Transitive relation: A relation R on a set “A” is said to be transitive if $aRb,bRc\Rightarrow aRc$.
Equivalence relation: A relation R on a set “A” is said to be an equivalence relation if the relation is reflexive, symmetric and transitive.
Consider two relations ${{R}_{1}}$ and ${{R}_{2}}$ on $\mathbb{Z}$ be such that $a{{R}_{1}}b\Leftrightarrow a-b\text{ is divisible by 5}$ and $a{{R}_{2}}b\Leftrightarrow a-b\text{ is divisible by 7}$.
Claim 1: ${{R}_{1}}$ is an equivalence relation.
Proof:
Reflexivity: We know that $\forall a-a=0$ which is divisible by 5. Hence we have $\forall a\in \mathbb{Z},a{{R}_{1}}a$. Hence the relation is reflexive.
Symmetricity: We know that if a-b is divisible by 5, then b-a is also divisible by 5. Hence, we have $a{{R}_{1}}b\Rightarrow b{{R}_{1}}a$. Hence the relation is symmetric.
Transitivity: We know that the sum of two integers divisible by 5 is also divisible by 5. Hence, we have if a-b is divisible by 5 and b-c is divisible by 5, then a-b+b-c= a-c is also divisible by 5.
Hence, we have $a{{R}_{1}}b,b{{R}_{1}}c\Rightarrow a{{R}_{1}}c$. Hence the relation is transitive.
Since the relation is reflexive, symmetric and transitive, the relation is an equivalence relation.
Claim 2: ${{R}_{2}}$ is an equivalence relation.
Proof:
Reflexivity: We know that $\forall a-a=0$ which is divisible by 7. Hence we have $\forall a\in \mathbb{Z},a{{R}_{2}}a$. Hence the relation is reflexive.
Symmetricity: We know that if a-b is divisible by 7, then b-a is also divisible by 7. Hence, we have $a{{R}_{2}}b\Rightarrow b{{R}_{2}}a$. Hence the relation is symmetric.
Transitivity: We know that the sum of two integers divisible by 7 is also divisible by 7. Hence, we have if a-b is divisible by 7 and b-c is divisible by 7, then a-b+b-c= a-c is also divisible by 7.
Hence, we have $a{{R}_{2}}b,b{{R}_{2}}c\Rightarrow a{{R}_{2}}c$. Hence the relation is transitive.
Since the relation is reflexive, symmetric and transitive, the relation is an equivalence relation.
Claim 3: ${{R}_{1}}\bigcup {{R}_{2}}$ is not transitive.
We have 7-2 = 5 which is divisible by 5.
Hence, $\left( 7,2 \right)\in {{R}_{1}}\Rightarrow \left( 7,2 \right)\in {{R}_{1}}\bigcup {{R}_{2}}$
Also 2-(-5) = 2+5=7 which is divisible by 7.
Hence, $\left( 2,-5 \right)\in {{R}_{2}}\Rightarrow \left( 2,-5 \right)\in {{R}_{1}}\bigcup {{R}_{2}}$
However 7-(-5) = 12, which is neither divisible by 5 nor by 7.
Hence, we have $\left( 7,-5 \right)\notin {{R}_{1}}\text{ and }\left( 7,-5 \right)\notin {{R}_{2}}\Rightarrow \left( 7,-5 \right)\notin {{R}_{1}}\bigcup {{R}_{2}}$.
Hence we have $\left( 7,2 \right)\in {{R}_{1}}\bigcup {{R}_{2}},\left( 2,-5 \right)\in {{R}_{1}}\bigcup {{R}_{2}}$ but $\left( 7,-5 \right)\notin {{R}_{1}}\bigcup {{R}_{2}}$.
Hence ${{R}_{1}}\bigcup {{R}_{2}}$ is not transitive.
Since ${{R}_{1}}\bigcup {{R}_{2}}$ is not transitive, it is not an equivalence relation.
Hence the union of two equivalence relations on a set may not be an equivalence relation.

Note: Alternative solution:
Choose the following relations on the set A ={1,2,3,4} defined as
{{R}_{1}}=\left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 3,3 \right),\left( 4,4 \right),\left( 1,2 \right),\left( 2,1 \right) \right\\} and {{R}_{1}}=\left\\{ \left( 1,1 \right),\left( 2,2 \right),\left( 3,3 \right),\left( 4,4 \right),\left( 2,3 \right),\left( 3,2 \right) \right\\}.
Observe that ${{R}_{1}}$ and ${{R}_{2}}$ are equivalence relations but $\left( 1,2 \right)\in {{R}_{1}}\bigcup {{R}_{2}},\left( 2,3 \right)\in {{R}_{1}}\bigcup {{R}_{2}},\left( 1,3 \right)\notin {{R}_{1}}\bigcup {{R}_{2}}$.
Hence the union of two equivalence relations is not necessarily an equivalence relation.