How to show (S∘R)−1=R−1∘S−1(S \circ R)^{-1} = R^{-1} \circ S^{-1}?

Start

Let RR be a relation from AA to BB, and let SS be a relation
from BB to CC. The composite of RR and SS is
S∘R={(a,c): there exists b∈B such that (a,b)∈R and (b,c)∈S}.S \circ R = \{(a, c):\text{ there exists $b \in B$ such that $(a, b) \in R$ and }(b, c) \in S\}.

pf. (x,y)∈(S∘R)−1(x,y) \in (S \circ R)^{-1}
 iff (a,c):∃b∈B such .that (a,b)∈R and (b,c)∈S\text{ iff }{(a, c): ∃b \in B\text{ such .that }(a, b)\in R \text{ and }(b, c) \in S}
iff (a,c):∃b∈B such that (b,a)∈R and (a,c)∈S\text{iff }{(a,c): ∃b \in B\text{ such that }(b,a)\in R\text{ and }(a,c) \in S}

I am lost at this point. I am pretty sure I have to do an iff proof, and just use the definitions properly, but I seem to not clearly understand them. If I could get some assistance that would be great. And I believe my formatting is off, but I have no clue how line up the iff, so, if someone could show me that too. Thank you.

=================

1

 

The idea of doing an iff proof is fine. Just recall the definitions; you have (a,b)∈R−1⟺(b,a)∈R(a,b) \in R^{-1} \iff (b,a) \in R, and you have (a,c)∈S∘R⟺∃b((a,b)∈R∧(b,c)∈S)(a,c) \in S \circ R \iff \exists b((a,b) \in R \land (b,c) \in S).
– Mees de Vries
2 days ago

  

 

You don’t have to input a mathematical equation in separate pieces, like R−1R^{-1}∘\circS−1S^{-1} $R^{-1}$$\circ$$S^{-1}$. You can (and should) use R−1∘S−1R^{-1}\circ S^{-1} $R^{-1} \circ S^{-1}$ instead. For some basic information about writing math at this site see e.g. here, here, here and here. (And, of course, you can also learn by example – when you see how other users edit your posts.)
– Martin Sleziak
2 days ago

=================

2 Answers
2

=================

The following statements are (evidently) equivalent:

⟨x,y⟩∈(S∘R)−1\langle x,y\rangle\in(S\circ R)^{-1}
⟨y,x⟩∈S∘R\langle y,x\rangle\in S\circ R
∃z[⟨y,z⟩∈R∧⟨z,x⟩∈S]\exists z[\langle y,z\rangle\in R\wedge\langle z,x\rangle\in S]
∃z[⟨z,y⟩∈R−1∧⟨x,z⟩∈S−1]\exists z[\langle z,y\rangle\in R^{-1}\wedge\langle x,z\rangle\in S^{-1}]
∃z[⟨x,z⟩∈S−1∧⟨z,y⟩∈R−1]\exists z[\langle x,z\rangle\in S^{-1}\wedge\langle z,y\rangle\in R^{-1}]
⟨x,y⟩∈R−1∘S−1\langle x,y\rangle\in R^{-1}\circ S^{-1}

Looking at first and last we conclude that: (S∘R)−1=R−1∘S−1(S\circ R)^{-1}=R^{-1}\circ S^{-1}

Since (a,b)∈R⟺(b,a)∈R−1(a,b)\in R\iff (b,a)\in R^{-1}, (b,c)∈S⟺(c,b)∈S−1(b,c)\in S\iff (c,b)\in S^{-1} there resullts that
∃b∈B:((a,b)∈R)∧((b,c)∈S)⟺∃b∈B:(((b,a)∈R−1)∧(c,b)∈S−1)⟺∃b∈B:((c,b)∈S−1)∧((b,a)∈R−1)\begin{align}\exists b\in B:((a,b)\in R)\wedge((b,c)\in S) &\iff\exists b\in B:(((b,a)\in R^{-1})\wedge(c,b)\in S^{-1})\cr
&\iff\exists b\in B:((c,b)\in S^{-1})\wedge((b,a)\in R^{-1})
\end{align}