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:
- $(x,y) \in (A \circ B) \Leftrightarrow \exists z: (x,z) \in A \land (z,y) \in B$, and
- $(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.