Show that $R \cap R^*$ and $R \cup R^*$ are equivalence relations.

Question

Let $R$ be a reflexive and transitive relation on a set $S$. Let $R^*$ be the dual relation, $(a,b) \in R^*$ if and only if $(b,a) \in R$. Show that $R \cap R^*$ and $R \cup R^*$ are equivalence relations.

My attempt: By definition 6.2.3

R is reflexive if $(\forall x \in S)(b,b) \in R]$

R is transitive if $(\forall x, y, z \in S)[((b,a) \in R \land (a,c) \in R) \rightarrow (b,c) \in R]$.

At first I wanted to disprove the statement. I thought that R wouldn't be an equivalence relation because it was only reflexive and transitive, not symmetric. And by set intersection definition for $R \cap R^*$ I thought that $R$ and $R^*$ must both be an equivalence relation . However for set union definition, $R$ or $R^*$ can be equivalence relation. It turns out that it's possible to prove.

I was given this massive hint during the lecture:

$(a,b) \in R^* \leftrightarrow (b,a) \in R$.

Set $T = R \cap R^*$. Show that $T$ is an equivalence relation.

1. $(a,a) \in R$ and $ (a,a) \in R^* \rightarrow (a,a) \in R \cap R^*$

2. Suppose $(a,b) \in R \cap R^* \rightarrow (a,b) \in R$ and $(b,a) \in R \rightarrow (b,a) \in R \cap R^*$

3. Suppose $(a,b) \in R \cap R^*$ and $(b,c) \in R \cap R^*$ then $(a,b) \in R$ and $(b,a) \in R$. $(b,c) \in R)$ and $(c,b) \in R$. So $(a,c) \in R $ and $(c,a) \in R$. So $(a,c) \in R$ and $(a,c) \in R^*$ and $(a,c) \in R \cap R^*$

Is $R \cup R^*$ and equivalence relation?

$(a,b) \in R \cup R^*$ if $(a,b) \in R$ or $(b,a) \in R$.

$(a,b) \in R \cap R^*$ if $(a,b) \in R$ and $(b,a) \in R$

The first two work, but the last one won't match. give a counter example

I'm thinking that the last one won't match because we have the extra element c, but how do I show it. Do I let a,b,c be sets in $R$ and $R^*$ like let $A =[1,2],B = [1,2]$ and $C=[1,2,3]$? And then use the dual relation to see that something doesn't match due to the $3$ in $C$?

Answer 1

The following rules are not to difficult to prove:

1) For every relation $R$ the relations $R\cap R^*$ and $R\cup R^*$ are symmetric.

2) If $R$ is transitive (reflective, symmetric) then $R^*$ transitive (reflective,symmetric) .

3) If relations are reflexive then so is there intersection (union).

4) If relations are transitive then so is there intersection.

5) If relations are symmetric then so is there intersection (union).

Applying this shows easily that $R\cap R^*$ is an equivalence relation if $R$ is transitive and reflective, but it cannot be concluded that $R\cup R^*$ is an equivalence relation.

As a counterexample take set $\left\{ 1,2,3\right\} $ with on it the relation $\left(x,y\right)\in R\iff x\leq y\wedge\left(x,y\right)\ne\left(2,3\right)$. Then $R$ is reflexive and transitive, and $R\cup R^*=\left\{ 1,2,3\right\} \times\left\{ 1,2,3\right\} -\left\{ \left(2,3\right),\left(3,2\right)\right\} $ . Then $\left(3,1\right)$ and $\left(1,2\right)$ belong to $R\cup R^*$ but $\left(3,2\right)$ does not, so it is not transitive.

A proof of 1):

$$\left(a,b\right)\in R\cap R^{*}\iff\left(a,b\right)\in R\wedge\left(a,b\right)\in R^{*}\iff\left(b,a\right)\in R^{*}\wedge\left(b,a\right)\in R\iff\left(b,a\right)\in R\cap R^{*}$$

$$\left(a,b\right)\in R\cup R^{*}\iff\left(a,b\right)\in R\vee\left(a,b\right)\in R^{*}\iff\left(b,a\right)\in R^{*}\vee\left(b,a\right)\in R\iff\left(b,a\right)\in R\cup R^{*}$$