= Composition of commuting equivalence relations
{title2=$R\circ S=S\circ R$}
Using the left-to-right convention for <composition of relations>, two <equivalence relations> $R,S$ have an equivalence-relation composite exactly when $R\circ S=S\circ R$. Its inverse is $S\circ R$. Commutation gives $(R\circ S)^2=R^2\circ S^2=R\circ S$, proving transitivity. Every equivalence relation containing $R,S$ contains their two-step composite, so this is their least common extension.
// Destination: combinatorics.bigb
Back to article page
