1
$\begingroup$

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.

  • 0
    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.2011-05-01

1 Answers 1

1

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.

  • 0
    Hey, that's unfair :-)2011-05-04