Composition of relations

Definition

Let $A$, $B$ and $C$ be sets, let $R \subseteq A \times B$ and let $S \subseteq B \times C$ be binary relations. The composition of $R$ and $S$ is the relation from $A$ to $C$ $$R \mathbin{;} S = \{(a, c) \in A \times C \mid \exists b \in B, \, a \mathrel{R} b \text{ and } b \mathrel{S} c\}.$$

Remarks

Many authors write $S \circ R$ for $R \mathbin{;} S$. This order agrees with function composition. Composition of relations is associative. A relation $R$ on a set is transitive exactly when $R \mathbin{;} R \subseteq R$.

Explanations

L1 human

Let $R$ be "is a parent of" and let $S$ be "is a parent of" again. Then $R \mathbin{;} S$ is "is a grandparent of": you go from a person to a child, then from the child to a grandchild.