Inverse of Composition of Relation – Elementary Set Theory

elementary-set-theoryrelations

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.

Best Answer

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.

Related Question