# A relation $R$ such that $R\cup R^{-1}$ is not an equivalence relation

I have a homework assignment to find a Relation $R$ over $A = \{1,2,3\}$ where $R\cup {{R}^{-1}}$ is not an equivalence relation (transitive, reflexive and symmetrical).

$R$ must be Transitive and Reflexive (${{I}_{A}}\subseteq R$)

Any clue anyone? I just am unable to find an example

Thanks

-
If $I_A\subseteq R$, then you are guaranteed that $R$ is reflexive; however, you are not guaranteed that $R$ is transitive. –  Arturo Magidin Jul 30 '11 at 16:28
@Arturo I meant that there is a restriction on your selected R and that restriction is it must be Transitive and Reflexive –  Jason Jul 30 '11 at 16:51
Okay; it wasn't clear, because the parenthetical comment "$I_A\subseteq R$" looks like the justification for "$R$ must be transitive and reflexive". –  Arturo Magidin Jul 30 '11 at 17:20
Nha, I'm just translating from my language so I was not sure of the term in English so I added it just to be sure. –  Jason Jul 30 '11 at 17:26
Yes, I see what it was you tried to say: it was just the justification for the final clause, not for the entire sentence. It just seemed like it was a justification for the entire sentence. –  Arturo Magidin Jul 30 '11 at 17:44

Given that you are assuming that $R$ is reflexive, the only thing that can fail for $R\cup R^{-1}$ to be an equivalence relation is transitivity: you should verify that since $I_A\subseteq R$, then $I_A\subseteq R\cup R^{-1}$; and that $R\cup R^{-1}$ is symmetric for every relation $R$. So the only possible pitfall lies in transitivity.

Now, you are assuming that $R$ itself is transitive. So, how can transitivity fail? Say you have $(a,b),(b,c)\in R\cup R^{-1}$; if $(a,b),(b,c)\in R$, then since we are assuming $R$ is transitive, then $(a,c)\in R\subseteq R\cup R^{-1}$. If $(a,b),(b,c)\in R^{-1}$, then $(c,b),(b,a)\in R$, and again by transitivity we conclude $(c,a)\in R$, hence $(a,c)\in R^{-1}\subseteq R\cup R^{-1}$.

So what's left? What happens if $(a,b)\in R$, and $(b,c)\in R^{-1}$, but we do not have $(a,b)\in R^{-1}$ nor $(b,c)\in R$? Can you construct such an example? What will happen then?

-
Thanks I did manage to narrow it to the Transitive property but could not find an example for some reason :) –  Jason Jul 30 '11 at 16:49

One sometimes helpful way to approach questions like this, if you can't find a counterexample, is simply to try and prove the opposite: that is, prove that $R\cup R^{-1}$ is an equivalence relation. Well, it's obviously reflexive; it's also obviously symmetric, because anything in $R$ will have its inverse in $R^{-1}$. So transitivity must be where it breaks down.

Suppose there are two relations a~b and b~c in $R\cup R^{-1}$ whose product a~c is not in $R\cup R^{-1}$. (You might also write these relations (a,b), etc.) It's easy to see that a, b and c must all be distinct elements, so in fact, we might as well choose 1~2, 2~3 and 1~3: we want the first two to be in $R\cup R^{-1}$, but not the third.

As $R$ is transitive, we can't have both 1~2 and 2~3 in $R$. Likewise they can't both be in $R^{-1}$ (otherwise, flip them over to $R$ and use transitivity there). So one of them must be in $R$ and one in $R^{-1}$. Taking $R$ and $R^{-1}$ to be minimal relations containing 1~2 and 2~3 respectively works as a counterexample.

-