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

An equivalence relation on $A$ is a binary relation that is reflexive, symmetric and transitive: $xRx$ for every $x$; $xRy\Rightarrow yRx$; and $xRy,yRz\Rightarrow xRz$. Write $T=R\circ S$, using the stated order for composition of relations. Composition is associative because both possible bracketings mean that there is a two-step sequence of intermediate witnesses. Reflexivity showsand also that $T$ is reflexive. Transitivity and reflexivity of the original relations give $R\circ R=R$, $S\circ S=S$. Since both original relations are symmetric,The four parts below show that each condition is equivalent to the commuting equivalence relations condition $R\circ S=S\circ R$.

For the integer example, put $d=\gcd (m,n)$. Membership of $(x,z)$ in the composite means that some $y$ satisfies $y-x=ma$, $z-y=nb$ for integers $a,b$. Consequently $z-x=ma+nb$ is divisible by $d$. Conversely, if $z-x$ is divisible by $d$, the Bezout identity expresses it as $ma+nb$; setting $y=x+ma$ provides the required witness. ThusReversing the roles of $m,n$ gives exactly the same modular congruence relation, hence $R\circ S=S\circ R$. This verifies all four conditions and identifies their common smallest equivalence relation explicitly.

By the inverse identity established in the root solution, the composite $T$ is a symmetric relation precisely whenThus condition (i) implies condition (iii). Conversely, if $S\circ R\subseteq R\circ S$, take inverse relations. Since $R,S$ are symmetric, this gives the reverse inclusion $R\circ S\subseteq S\circ R$. The two composites are equal, making $T$ symmetric. Therefore (i) and (iii) are equivalent, and either one forces commutation.

A binary relation $T$ is transitive exactly when $T\circ T\subseteq T$. If condition (iii) holds, associativity and monotonicity of composition of relations giveHence (iii) implies (ii). Conversely, the inclusions $R,S\subseteq T$ implyIf $T$ is a transitive relation, the right side lies in $T$, which is condition (iii). Thus (ii) and (iii) are equivalent.

The inverse argument in part (i) proves that the one-sided inclusion in (iii) already implies equality:Parts (i) and (ii) then make $T$ both symmetric and transitive; it is reflexive from the root solution. Therefore $T$ is an equivalence relation containing $R$ and $S$.

If $U$ is any other equivalence relation containing both, a witness $xRy,ySz$ gives $xUy,yUz$, and transitivity gives $xUz$. Hence $T\subseteq U$. Thus (iii) implies the unique-smallest assertion in (iv).

Condition (iv) says in particular that $T$ is an equivalence relation, so it is symmetric and transitive. It therefore implies (i) and (ii), closing the chain of implications.

Uniqueness is literal: if two equivalence relations both contain $R,S$ and are each contained in every such relation, each is contained in the other, so they are equal. Combining the preceding proofs givesTheir common relation is the equivalence relation generated by $R\cup S$, and under these conditions it is already obtained by the two-step composite $R\circ S$.