Intersection of equivalence relations containing a binary relation on a set.

Question

I am currently stuck on the second part of the following exercise (Exercise A.3 from Introduction to Topological Manifolds):
“Let $R \subseteq X \times X$ be any relation on $X$, and define $\sim$ to be the intersection of all equivalence relations in $X \times X$ that contain $R$.

• Show that $\sim$ is an equivalence relation.
• Show that $x \sim y$ if and only if at least one of the following statements is true:
  1. $x = y,$
  2. $x R’ y,$
  3. there is a finite sequence of elements ${z_1, \dots, z_n} \in X$ such that $xR’z_1R’ \dots R’z_nR’ y,$
  where $xR’y$ means $xRy$ or $yRx$.

I am comfortable proving that LHS $\impliedby$ RHS by showing that RHS is contained in any equivalence relation on $X$ containing $R$. However, I am struggling to deduce RHS from LHS. Any help would be greatly appreciated.

Answer 1

Since I do not want to write some unusual notation such as $\sim_1 \subseteq \sim_2$, I will use this notation:

• $E_1$ is the equivalence relation defined by the intersection;
• $E_2$ is the relation defined by the three conditions.

As you rightly said, $E_2$ is is a subset of any equivalence relation containing $R$, and thus $E_2\subseteq E_1$.

It remains to show $E_1\subseteq E_2$. To see this, it is enough to show that $E_2$ is an equivalence relation and that it contains $R$. (Since then $E_2$ is one of the relations used in the intersection.)

You might have a look at some results about transitive (and maybe reflexive and symmetric closure, too):

• Wikipedia: Transitive closure
• ProofWiki: Transitive Closure of Reflexive Symmetric Relation is Equivalence
• Closure of equivalence relations