Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 (Numbers and Sets)

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.

A binary relation $T$ is symmetric exactly when $T=T^{-1}$. By the reversed-chain identity, condition (i) therefore gives $R\circ S=S\circ R$, in particular condition (iii). Conversely, if $S\circ R\subseteq R\circ S$, reversing both sides gives $R\circ S\subseteq S\circ R$. Thus condition (iii) gives equality and therefore symmetry. Conditions (i) and (iii) are equivalent.

If $T$ is transitive, then $T\circ T\subseteq T$. Since $S,R\subseteq T$, monotonicity of composition of relations giveswhich is condition (iii).

Conversely, condition (iii), associativity of composition of relations, and the identities $R\circ R=R$, $S\circ S=S$ giveFor a direct chain description, start with $xRaSbRcSz$. Replace its middle $aSbRc$ by $aRdSc$ using condition (iii), then use transitivity inside $R$ and $S$ to obtain $xRdSz$. Hence $T$ is transitive. Conditions (ii) and (iii) are equivalent.

The preceding proofs show that this inclusion forces both symmetry and transitivity of $T$; its reflexivity already follows from that of $R,S$. It actually forces equality of the composites, not just a one-way inclusion:This is the composition of commuting equivalence relations criterion. It remains to establish the asserted smallest-extension characterization, rather than merely to identify an equivalence relation.

Assume any of conditions (i)–(iii). The established reflexivity, symmetry and transitivity make $T$ an equivalence relation, and it contains both $R,S$. If $E$ is any equivalence relation containing $R,S$ and $xRaSz$, then $xEaEz$, so transitivity of $E$ gives $xEz$. Thus $T\subseteq E$. This proves that $T$ is the unique smallest equivalence relation containing $R$ and $S$. Conversely, condition (iv) explicitly makes $T$ an equivalence relation, so it has properties (i) and (ii). Together these implications prove all four conditions equivalent.

For the final integer example, let $g=\gcd (m,n)$. If $x\equiv y(\mathrm{mod}m)$ and $y\equiv z(\mathrm{mod}n)$, then $z-x$ is a sum of a multiple of $m$ and a multiple of $n$, so $x\equiv z(\mathrm{mod}g)$. Conversely, if $g$ divides $z-x$, Bezout identity provides integers $a,b$ with $z-x=am+bn$. Set $y=x+am$. Then $y-x$ is divisible by $m$ and $z-y$ by $n$, so $xRySz$. ThereforeInterchanging $m,n$ gives the other equality. The composite is thus exactly congruence modulo the greatest common divisor, an equivalence relation, and all four equivalent conditions hold.