Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / Solution

An equivalence relation on a set $A$ is a binary relation that is reflexive, symmetric and transitive: every element is related to itself, related pairs may be reversed, and two consecutive related pairs imply the pair of endpoints is related.

Write $T=R\circ S$, using the printed left-to-right composition of relations convention. Reflexivity implies $R\subseteq T$ and $S\subseteq T$, and hence $T$ is reflexive. Reversing a two-step chain givessince $R,S$ are symmetric. Also $R\circ R=R$ and $S\circ S=S$: one inclusion is transitivity, and the reverse follows by inserting a reflexive step. These elementary identities supply the equivalences below, without presuming that a composite of equivalence relations is automatically an equivalence relation.