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.

First some context (binary relations)

$F \subseteq W \times X \quad G \subseteq X \times Y \quad H \subseteq Y \times Z $

Does the following equality hold

$(G \circ F)^{-1} = F^{-1} \circ G^{-1}$

I haven't been able to find a counterexample, so I think it holds in general. But how would I prove it?

This identity

$G \circ F = F^{-1} \circ G^{-1}$

I have a counterexample for.

And then the following identity

$(H \circ G) \circ F = H \circ (G \circ F)$

I have not found a counterexample so this could hold. But how would I prove it?

Edit: The task says give a good reason, so it doesn't have to be a mathematical proof.

share|improve this question
1  
proofwiki.org/wiki/Inverse_of_Composite_Relation proofwiki.org/wiki/Composition_of_Relations_Associative I would write the second proof differently (by rewriting the condition $(x,z)\in (H\circ G)\circ F$), but perhaps it's just a matter of taste. –  Martin Sleziak May 1 '11 at 12:02
    
It would be helpful if you gave your definition of the composition and inverse. I would regard this as each binary relation being single steps and the composition being paths of two steps, so of course taking a path of two steps and reversing it is the same as taking reverse steps in the reverse order. –  Phira May 1 '11 at 12:04

1 Answer 1

up vote 1 down vote accepted

It should be a comment, but I do not have enough reputation points to leave any :-)

Think of a relation as matrix, inverse as matrix transposition, and composition as matrix multiplication. Then these properties follow from the well-known facts from linear algebra.

share|improve this answer
    
Have some rep then. :) –  Algific May 4 '11 at 18:49
    
Hey, that's unfair :-) –  Michal R. Przybylek May 4 '11 at 20:41

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.