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

Question

Start

Let $R$ be a relation from $A$ to $B$, and let $S$ be a relation from $B$ to $C$. The composite of $R$ and $S$ is $$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) \in (S \circ R)^{-1}$ $$\text{ iff }{(a, c): ∃b \in B\text{ such .that }(a, b)\in R \text{ and }(b, c) \in 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.

Answer 1

The following statements are (evidently) equivalent:

• $\langle x,y\rangle\in(S\circ R)^{-1}$
• $\langle y,x\rangle\in S\circ R$
• $\exists z[\langle y,z\rangle\in R\wedge\langle z,x\rangle\in S]$
• $\exists z[\langle z,y\rangle\in R^{-1}\wedge\langle x,z\rangle\in S^{-1}]$
• $\exists z[\langle x,z\rangle\in S^{-1}\wedge\langle z,y\rangle\in R^{-1}]$
• $\langle x,y\rangle\in R^{-1}\circ S^{-1}$

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

Answer 2

Since $(a,b)\in R\iff (b,a)\in R^{-1}$, $(b,c)\in S\iff (c,b)\in S^{-1}$ there resullts that \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}