2
$\begingroup$

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

  • 0
    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.2011-07-30

2 Answers 2

5

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?

  • 0
    Thanks I did manage to narrow it to the Transitive $p$ro$p$erty but could not find an example for some reason :)2011-07-30
2

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.