Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

2 Answers

up vote 5 down vote accepted

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?

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.