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'm getting fairly confused with two exercises related to proving a relation's inverse's properties by knowing the original's. I couldn't do either. Any hint is appreciated.


If $R$ is a symmetric relation over $A$ with $A \not = \emptyset$, prove that $R^{-1}$ is also symmetric.

$R$ is symmetric, so we know that $(aRb \implies bRa)$.

We want to prove that $R^{-1}$ is symmetric. If we use the same $a,b$ as before, we could write it like this: $(bRa \implies aRb)$

So we want to prove $(bRa \implies aRb)$.

The rightmost part of that is $aRb$, which, according to our first premise, it implies $bRa$. I think we can replace it:

$$bRa \implies (aRb \implies bRa)$$

Uh, maybe we can simplify this with implication/disjunction:

$$b\not R a \lor (a\not Rb \lor bRa)$$

$$a\not Rb \lor V_0$$

This isn't quite right... But I'm way too lost - what should I have done?


If $R$ is a transitive relation over $A$ with $A \not = \emptyset$, prove that $R \cap R^{-1}$ is also transitive.

Frankly, I'm lacking even the slightest clue here.

The only think I could observe was that since $R$ is transitive, $R^{-1}$ is transitive as well (is this okay to state, or do I have to prove it?). Not sure how would that help me though.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

I'm not sure what definitions you are using, but the idea should be something like this:

$R^{-1}=\{(b,a):(a,b)\in{R}\}$. Let $(a,b)\in{R^{-1}}$. As a result ${(b,a)\in{R}}$. Since $R$ is symmetric, $(a,b)\in{R}$. So by definition $(b,a)\in{R^{-1}}$. Hence we have that $R^{-1}$ is symmetric.

As for the other question: Suppose $(a,b),(b,c)\in{R\cap{R^{-1}}}$. We would like to show that $(a,c)\in{R\cap{R^{-1}}}$. Now $(a,b),(b,c),(b,a),(c,b)\in{R}$. Since $R$ is transitive we have $(a,c),(c,a)\in{R}$ by using transitivity on $R$. So we have $(a,c)\in{R^{-1}}$ which gives us what we need.

share|improve this answer
    
For the second question, we proved in the first question that $R^{-1}$ is symmetric, so $(a,c) \in R^{-1}$, therefore the intersection $R \cap R^{-1}$ also contains $(a,c)$ since $(a,c) \in R$ as well, right? However, I'm not sure if the previous question should be treated as a separate scenario, or does it not matter? –  Zol Tun Kul Nov 5 '13 at 0:24
    
Sorry. The argument I had in mind, which you wrote down, is not fully correct (since we do not know that $R$ is reflexive.). I can't think of an immediate way to fix this, sorry. It would help to know what definitions you are working with though. –  Danul G Nov 5 '13 at 1:43
    
I'm not sure what do you mean by definitions (lol). I just quoted the exercise :(.. But thanks anyway, the insight was very helpful! –  Zol Tun Kul Nov 5 '13 at 1:46
    
Thank you for catching the error in my previous answer. It has been corrected. If the answer is correct now please do me a favor and accept it. –  Danul G Nov 5 '13 at 1:51
    
Yeah, it seems your answer is now correct. Thank you. –  Zol Tun Kul Nov 5 '13 at 2:29
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.