Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive.
First, I'm wondering if my proof is correct? Second, I'm really curious as to if there are any more elegant ways of proving this statement? It took me a long time of playing around with different possibilities to find this argument. Are there any shortcuts I am missing, or any related theorems about relations that people find are helpful when trying to prove statements like the one above? Here is my proof:
Suppose $S \circ R \subseteq R \circ S$. Let $x,y,z \in A$. Suppose $(x,y) \in R \circ S$ and $(y,z) \in R \circ S$. Since $(x,y) \in R \circ S$, we can choose some $a \in A$ such that $(x,a) \in S$ and $(a,y) \in R$. Similarly, since $(y,z) \in R \circ S$, we can choose some $b \in B$ such that $(y,b) \in S$ and $(b,z) \in R$. We have $(a,y) \in R$ and $(y,b) \in S$, so $(a,b) \in S \circ R$. Since $S \circ R \subseteq R \circ S$, $(a,b) \in R \circ S$, so we can choose some $c \in A$ such that $(a,c) \in S$ and $(c,b) \in R$. We have $(x,a) \in S$ and $(a,c) \in S$, so since $S$ is transitive, $(x,c) \in S$. We also have $(c,b) \in R$ and $(b,z) \in R$, so since $R$ is transitive, $(c,z) \in R$. Hence, $(x,c) \in S$ and $(c,z) \in R$, so $(x,z) \in R \circ S$.
Your proof is OK. But there is a more concise way to say the same thing: $$ (R \circ S) \circ (R \circ S) = R \circ (S \circ R) \circ S \subseteq R \circ (R \circ S) \circ S = (R \circ R) \circ (S \circ S) \subseteq R \circ S. $$ Of course, we use several things here implicitly. First, we use the associativity of $\circ$, i.e. that $(X \circ Y) \circ Z = X \circ (Y \circ Z)$. Second, we use its "monotonicity", i.e. that if $X \subseteq X'$ and $Y \subseteq Y'$, then $X \circ Y \subseteq X' \circ Y'$.