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 no Ida how to approach this problem:

Suppose S is a relation on a set X which is reflexive and transitive. Then S intersection S inverse is an equivalence relation on X.

Any idea on how I would tackle this would be appreciated.

share|improve this question
3  
Do you know what "S inverse" means? Do you know what the intersection of two relations means? Do you know what equivalence relation means? Do you know how to check whether a relation is reflexive? Do you know how to check whether a relation is symmetric? Do you know how to check whether a relation is transitive? If any of your answers is no, that tells you where to get started on this problem. –  Gerry Myerson Oct 5 '12 at 4:36
    
I understand. These questions can seem tricky –  blutuu Oct 5 '12 at 5:03
    
Two hints: (1)If $X\subset S$, then does $X$ carry the the transitive property? (2)If $x\ne y$ and $xSy$, what else must be true for $x(S\cap S)y$ to hold. –  peoplepower Oct 5 '12 at 5:15
    
Yes, the questions can seem tricky, but this one is really just a matter of unraveling all the definitions. To show it's an equivalence relation, you have to show it's reflexive (among other things). To show it's reflexive, you have to show it contains $(x,x)$ for all $x$ in $X$. To show the intersection contains $(x,x)$, you have to show that both $S$ and its inverse contain $(x,x)$. Does $S$ contain $(x,x)$? Does its inverse contain $(x,x)$? You just have to work your way through this kind of reasoning. –  Gerry Myerson Oct 5 '12 at 5:20
add comment

1 Answer

up vote 0 down vote accepted

This is what I call a follow your nose proof: at each stage there’s really only one sensible thing to do, and it works. You have a reflexive, transitive relation $S$ on a set $X$, and you want to prove that $S\cap S^{-1}$ is an equivalence relation. Check the definition of an equivalence relation: it’s a relation that is reflexive, symmetric, and transitive, so to prove that $S\cap S^{-1}$ is an equivalence relation, you must prove that it is reflexive, symmetric, and transitive. Take them one at a time.

  • Suppose that $R$ is any relation on $X$; what does it mean for $R$ to be reflexive? It means that $\langle x,x\rangle\in R$ for every $x\in X$. Thus, you need to show that if $x\in X$, then $\langle x,x\rangle\in S\cap S^{-1}$.

  • A relation $R$ on $X$ is symmetric if $\langle y,x\rangle\in R$ whenever $\langle x,y\rangle\in R$. Thus, you need to show that if $\langle x,y\rangle\in S\cap S^{-1}$, then $\langle y,x\rangle\in S\cap S^{-1}$. I’ll do this one for you as an illustration.

Suppose that $\langle x,y\rangle\in S\cap S^{-1}$. Then in particular $\langle x,y\rangle\in S^{-1}$. This means that $\langle y,x\rangle\in S$ (why?). Moreover, $\langle x,y\rangle\in S$, so $\langle y,x\rangle\in S^{-1}$ (again, why?). But then $\langle y,x\rangle\in S\cap S^{-1}$, which is exactly what we wanted to show. It follows that $S\cap S^{-1}$ is symmetric.

  • Finally, what does it mean for a relation $R$ on $X$ to be transitive? What do you have to show in order to prove that $S\cap S^{-1}$ is transitive?
share|improve this answer
    
Ok that helps me a lot. I think I understand how to approach this question now. –  blutuu Oct 5 '12 at 13:45
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.