# Thread: Composition of transitive relations

1. ## Composition of transitive relations

Hi,

I have this problem that is really driving me crazy:

Suppose R and S are transitive relations on A. Prove that if SºR c RºS, then RºS is transitive.

I tried to use the theorem that says: R is transitive iff RºR c R, but I couldn't get to the end.

(c means subset)

2. This is a completely tedious proof. I will give you the outline.
Suppose that $\displaystyle (p,q) \in R \circ S \wedge (q,r) \in R \circ S$.
That means that $\displaystyle \left( {\exists s} \right)\left[ {(p,s) \in S \wedge (s,q) \in R} \right]\,\& \,\left( {\exists t} \right)\left[ {(q,t) \in S \wedge (t,r) \in R} \right]$.
From which it follows that $\displaystyle (s,q) \in R \wedge (q,t) \in S \Rightarrow (s,t) \in S \circ R \Rightarrow (s,t) \in R \circ S$.
It follows from that $\displaystyle \left( {\exists d} \right)\left[ {(s,d) \in S \wedge (d,t) \in R} \right]$.
Because both $\displaystyle S~\&~T$ are transitive we get $\displaystyle (p,d)\in S~\&~(d,r)\in R$.
But that means that $\displaystyle (p,r)\in R\circ S$.

3. Thanks a lot!
The outline was really what I needed. Thanks again!