Set Relation Composition

Definition

Let $A$, $B$ and $C$ be sets. Let $R\subseteq A\times B$ be a relation, and $S\subseteq B\times C$ be a relation. The composition of $R$ with $S$ ($R\circ S$) is the relation from $A$ to $C$ such that: $\forall x\in A,\forall z\in C\left(xS\circ Rz\iff \left(\exists y\in B(xRy\wedge ySz)\right)\right)$ i.e. $x\in A$ and $z\in C$ are "$S\circ R$" related iff there s a “path” from $x$ to $z$ via some intermediate element $y\in B$ in the arrow diagram

Laws

Let $A$, $B$, $C$ and $D$ be sets. Let $R\subseteq A\times B$, $S\subseteq B\times C$ and $T\subseteq C\times D$ be relations.

Associative

$T\circ (S\circ R)=(T\circ S)\circ R=T\circ S\circ R$

Inverse

$(S\circ R{)}^{-1}=R^{-1}\circ S^{-1}$