Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / c / ii / Solution

False, even for two equivalence relations. On $A=\{1,2,3\}$, let $R_1$ have equivalence classes $\{1,2\}$ and $\{3\}$, and let $R_2$ have equivalence classes $\{1\}$ and $\{2,3\}$. Both binary relations are transitive. For $S=R_2\circ R_1$, we have $3S2$, using the intermediate element $3$, and $2S1$, using the intermediate element $1$. However, $3S1$ fails: the only $R_1$-successor of $3$ is $3$, and $3R_{2}1$ is false. Thus the composite fails transitivity. The order of composition here means first $R_1$, then $R_2$.