Equivalence Relations with inverses?

Question

I have no Ida how to approach this problem:

Suppose S is a relation on a set X which is reflexive and transitive. Then S intersection S inverse is an equivalence relation on X.

Any idea on how I would tackle this would be appreciated.

Answer 1

This is what I call a follow your nose proof: at each stage there’s really only one sensible thing to do, and it works. You have a reflexive, transitive relation $S$ on a set $X$, and you want to prove that $S\cap S^{-1}$ is an equivalence relation. Check the definition of an equivalence relation: it’s a relation that is reflexive, symmetric, and transitive, so to prove that $S\cap S^{-1}$ is an equivalence relation, you must prove that it is reflexive, symmetric, and transitive. Take them one at a time.

• Suppose that $R$ is any relation on $X$; what does it mean for $R$ to be reflexive? It means that $\langle x,x\rangle\in R$ for every $x\in X$. Thus, you need to show that if $x\in X$, then $\langle x,x\rangle\in S\cap S^{-1}$.

• A relation $R$ on $X$ is symmetric if $\langle y,x\rangle\in R$ whenever $\langle x,y\rangle\in R$. Thus, you need to show that if $\langle x,y\rangle\in S\cap S^{-1}$, then $\langle y,x\rangle\in S\cap S^{-1}$. I’ll do this one for you as an illustration.

Suppose that $\langle x,y\rangle\in S\cap S^{-1}$. Then in particular $\langle x,y\rangle\in S^{-1}$. This means that $\langle y,x\rangle\in S$ (why?). Moreover, $\langle x,y\rangle\in S$, so $\langle y,x\rangle\in S^{-1}$ (again, why?). But then $\langle y,x\rangle\in S\cap S^{-1}$, which is exactly what we wanted to show. It follows that $S\cap S^{-1}$ is symmetric.

• Finally, what does it mean for a relation $R$ on $X$ to be transitive? What do you have to show in order to prove that $S\cap S^{-1}$ is transitive?