Composition

Definition 1. The composition of two binary relations $R$ and $S$ is the binary relation

\[S \circ R = \{(x, z) : (\exists y : x \,R\, y \,\land\, y \,S\, z) \}.\]

This is a set by Separation Schema:

\[S \circ R \subseteq \dom R \times \im S.\]

Proposition 1. Let $X$ and $Y$ be two sets. For any binary relation $R$ on $X$ and $Y$,

\[R \circ \id_X = \id_Y \circ R = R.\]

Proposition 2. Associativity. For any binary relations $R$, $S$ and $T$,

\[(R \circ S) \circ T = R \circ (S \circ T).\]

Proposition 3. For any functions $f$ and $g$ on a set $X$, $f \circ g$ is also a function on $X$. In other words, $\fun(X, X)$ is closed under composition.

Proposition 4. For any set $X$, $\rel(X, X)$ is a monoid under composition with neutral element $\id_X$.

Proposition 5. For any set $X$, $\fun(X, X)$ is a submonoid of $\rel(X, X)$ with neutral element $\id_X$.

Proposition 6. For any binary relations $R$ and $S$,

\[(R \circ S)^{-1} = S^{-1} \circ R^{-1}.\]