= Commuting equivalence relations
{title2=$R\circ S=S\circ R$}
For two <equivalence relations> on the same set, their composite contains each and is reflexive. It is symmetric exactly when the relations commute. It is transitive exactly when $S\circ R\subseteq R\circ S$, which by inversion is also equivalent to commutation. Under these conditions the composite is the smallest equivalence relation containing both. For congruences modulo $m,n$ on the integers, their composite is congruence modulo $\gcd(m,n)$.
// Target: combinatorics.bigb
Back to article page
