Suppose R is a relation from A to B and S and T are relations from B to C. Prove that (SoR)\(ToR) is a subset of (S\T) o R
-
Suppose (a,c) is an element of (S o R) \ (T o R).
Then in particular, (a,c) is an element of S o R, so there is some b in B such that (a,b) is in R and (b,c) is in S.
Now, if (b,c) were in T, then since (a,b) is in R, we'd have (a,c) in T o R, which is a contradiction. Therefore (b,c) can't be in T, so (b,c) is in S \ T.
Lastly, since (a,b) is in R and (b,c) is in S \ T, we have
(a,c) is in (S \ T) o R,
which finishes the proof, since (a,c) was an arbitrary element of (S o R) \ (T o R).
Then in particular, (a,c) is an element of S o R, so there is some b in B such that (a,b) is in R and (b,c) is in S.
Now, if (b,c) were in T, then since (a,b) is in R, we'd have (a,c) in T o R, which is a contradiction. Therefore (b,c) can't be in T, so (b,c) is in S \ T.
Lastly, since (a,b) is in R and (b,c) is in S \ T, we have
(a,c) is in (S \ T) o R,
which finishes the proof, since (a,c) was an arbitrary element of (S o R) \ (T o R).