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


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.




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


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})