4
$\begingroup$

I'm doing preparaton problems for my exam and one of the first problems in the "composition of relations" section is this:

Prove: $$ (A \circ B)^{-1} = B^{-1} \circ A^{-1} $$

I know I need to prove 2 inclusions (L = Left side of the equation, R = right side of the equation):

$ L \subseteq R$ and $R \subseteq L$

After few first steps (in both cases) I'm stuck. My short "observations":

$ L \subseteq R$:

I know:

  1. $(x,y) \in (A \circ B) \Leftrightarrow \exists z: (x,z) \in A \land (z,y) \in B$, and
  2. $(x,y) \in A^{-1} \Leftrightarrow (y,x) \in A$.

So, let's take $(x,y) \in (A \circ B)^{-1}$. From (2): $(y,x)\in(A\circ B)$. From (1) and previous conclusion: $\exists z: (y,z) \in A \land (z,x) \in B$. But... what's now?

I tried to do something, but I don't know, how to solve this and similar problems. I showed some of my "work", so it's not just asking you to solve this problem for me. I'm also asking for explanation(s), how to think about this kind of problems.

Thanks.

1 Answers 1

1

Your initial work is good. You seem to get lost, perhaps due to inexperience. Working step by step, and one at a time can be very helpful. Write different steps on different lines to organize your thoughts. E.g.:

  • Suppose that $(y,x)\in (A\circ B)^{-1}$, then $(x,y)\in A\circ B$.
  • Therefore there is $z$ such that $(x,z)\in A$ and $(z,y)\in B$.
  • Therefore $(z,x)\in A^{-1}$ and $(y,z)\in B^{-1}$.
  • Therefore $(y,x)\in B^{-1}\circ A^{-1}$.

The other direction is equally daunting if you work systematically.

  • 1
    Thank you! I just needed to rearrange 3rd step to see the obvious: $(y,z)\in B^{-1}$ and $(z,x)\in A^{-1}$. It's the definition of composition of relations: $(y,x) \in B^{-1} \circ A^{-1}$, cause we know that required $z$ exists (2nd step in your solution). I write this all, because it can be useful for somebody who is as inexperienced as me and doesn't see simple connections at first. Anyway: thanks again, Asaf, your answer is very helpful!2012-11-11
  • 0
    Solution for $R \subseteq L$: Suppose $(x,y) \in B^{-1} \circ A^{-1}$. That means: $\exists z: (x,z) \in B^{-1} \land (z,y) \in A^{-1}$. Therefore $(z,x) \in B \land (y,z) \in A$. We can rearrange this and write: $(y,z) \in A \land (z,x) \in B$, so it's easier to see that $(y,x) \in A \circ B$. So, $(x,y) \in (A\circ B)^{-1}$. I think it's ok (if not, please correct me), maybe it's useful for somebody who will have the same problem in the future.2012-11-11