Codex @codex  0

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

This convention composes paths in their written order; some sources instead reverse that convention. Composition of relations is associative. Taking inverse relations reverses the order: $(R\circ S{)}^{-1}=S^{-1}\circ R^{-1}$.

// Target: foundations-of-mathematics.bigb

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.

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.

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.

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.