Show that $R \cap R^{−1}$ is an equivalence relation on $X$?

Question

Let $R$ be a reflexive and transitive relation on $X$. Show that $R \cap R^{−1}$ is an equivalence relation on $X$.

I am stuck and feel like I am doing something wrong, any help would be much appreciated!

Here is what I have so far:

$R = \{1,2,3\}$

$X = \{2,3,4,5,6\}$

$R$ on $X = \{(1,2), (1,3),(1,4),(1,5),(1,6),(2,4),(2,6),(3,6)\}$

$R^{-1} = \{1,1/2,1/3\}$

$R \cap R^{-1} = \{1\}$

$R^{-1}$ on $X = \{(1,2),(1,3),(1,4),(1,5)(1,6)\}$

TRUE

Am I completely off-base or am I close?

Thanks!

Answer 1

Given a relation $R$ on a set $X$ (that is, a subset of the Cartesian product $X \times X$ of orders pairs of things in $X$), the relation $R^{-1}$ is the inverse relation formed by taking the ordered pairs in $R$ and reversing them; that is,

$$R^{-1} = \{(y, x): (x, y) \in R\}.$$

This should remind you of inverse functions, where 'input' and 'output' are reversed.

---

OK, so to prove that $R \cap R^{-1}$ is an equivalence relation on $X$, you need to show that it's

• reflexive by showing that $(x, x) \in R \cap R^{-1}$ for all $x \in X$,

• symmetric by showing that if $(x, y)$ is in $R \cap R^{-1}$ then $(y, x)$ is too, and

• transitive by showing that if $(x, y)$ and $(y, z)$ are in $R \cap R^{-1}$, then $(x, z)$ is as well.

To do that, I would show that $R^{-1}$ is both reflexive and transitive, given that $R$ is. That $R^{-1}$ is reflexive should be immediate, realizing it's transitive requires a little something more; namely working backwards (literally; everything is just flipped around in $R^{-1}$).

Then you'll have to convince yourself that the intersection of two reflexive and transitive relations on $X$ is reflexive and transitive as well. At which point, you just need to show that $R \cap R^{-1}$ is symmetric.

In fact, regardless of any properties $R$ has, $R \cap R^{-1}$ is always symmetric; here's a picture of a relation on $\{0, 1, 2, 3\}$ for your intuition (points in $R \cap R^{-1}$ are outlined in orange in the last picture):

To actually show $R \cap R^{-1}$ is symmetric, assume $(x, y) \in R \cap R^{-1}$, so that $(x, y) \in R$ and $(x, y) \in R^{-1}$. What do each of those statements tell us about $(y, x)$?

Answer 2

A binary relation on $X$ is any subset of $R \times R$.And $R^{-1}=\{(x,y) : (y,x)\in R\}$.Now $(x,y) \in (R \cap R^{-1}$ iff $((x,y) \in R$ and $(y,x)\in R)$. From this it should be obvious that if $R$ is transitive then $R\cap R^{-1}$ is also transitive.