Equivalence relations and composition, intersections of them

Question

I've been having some trouble with this one, I hope someone get's it.

Let S and R be equivalence relations within X.

Prove that if R∘S is an equivalence relation, then it is equal to the intersection of all equivalence relations within X that include R and S.

Thank you!

Answer 1

HINT: Suppose that $S,R$, and $R\circ S$ are all equivalence relations. By definition

$$R\circ S=\left\{\langle x,y\rangle\in X\times X:\exists z\in X\,\big(\langle x,z\rangle\in S\text{ and }\langle z,y\rangle\in R\big)\right\}\;.$$

The first thing that you need to show is that if $E$ is an equivalence relation on $X$ such that $S\subseteq E$ and $R\subseteq E$, then $R\circ S\subseteq E$. This isn’t too hard. Suppose that $\langle x,y\rangle\in R\circ S$; then there is a $z\in X$ such that $\langle x,z\rangle\in S\subseteq E$ and $\langle z,y\rangle\in R\subseteq E$.

• Why can you now conclude that $\langle x,y\rangle\in E$?

This shows that if $\mathscr{E}$ is the set of all equivalence relations on $X$ such that $S,R\subseteq E$, then

$$R\circ S\subseteq\bigcap\mathscr{E}\;.$$

To finish the proof, you need to show that

$$\bigcap\mathscr{E}\subseteq R\circ S\;.\tag{1}$$

Recall that you’re assuming that $R\circ S$ is an equivalence relation.

• Show that $S,R\subseteq R\circ S$, and conclude that $R\circ S\in\mathscr{E}$.
• Use this to prove $(1)$.