The composition of $R$ and $S$ is the relation $S\mathbin {\diamond }R$ defined as follows:
- Viewing relations from $A$ to $C$ as subsets of $A\times C$, we define
\[ S\mathbin {\diamond }R \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft\{ \webleft (a,c\webright )\in A\times C\ \middle |\ \begin{aligned} & \text{there exists some $b\in B$ such}\\ & \text{that $a\sim _{R}b$ and $b\sim _{S}c$}\end{aligned} \webright\} . \]
- Viewing relations as functions $A\times B\to \{ \mathsf{true},\mathsf{false}\} $, we define
\begin{align*} \webleft (S\mathbin {\diamond }R\webright )^{-_{1}}_{-_{2}} & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{b\in B}S^{-_{1}}_{b}\times R^{b}_{-_{2}}\\ & = \bigvee _{b\in B}S^{-_{1}}_{b}\times R^{b}_{-_{2}},\end{align*}
where the join $\bigvee $ is taken in the poset $\webleft (\{ \mathsf{true},\mathsf{false}\} ,\preceq \webright )$ of Chapter 1: Sets, Definition 1.2.2.1.3.
- Viewing relations as functions $A\to \mathcal{P}\webleft (B\webright )$, we define where $\text{Lan}_{\chi _{B}}\webleft (S\webright )$ is computed by the formula
\begin{align*} \webleft [\text{Lan}_{\chi _{B}}\webleft (S\webright )\webright ]\webleft (V\webright ) & \cong \int ^{y\in B}\chi _{\mathcal{P}\webleft (B\webright )}\webleft (\chi _{y},V\webright )\odot S_{y}\\ & \cong \int ^{y\in B}\chi _{V}\webleft (y\webright )\odot S_{y}\\ & \cong \bigcup _{y\in B}\chi _{V}\webleft (y\webright )\odot S_{y}\\ & \cong \bigcup _{y\in V}S_{y} \end{align*}for each $V\in \mathcal{P}\webleft (B\webright )$. In other words, $S\mathbin {\diamond }R$ is defined by[1]
\begin{align*} \webleft [S\mathbin {\diamond }R\webright ]\webleft (a\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}S\webleft (R\webleft (a\webright )\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{x\in R\webleft (a\webright )}S\webleft (x\webright ). \end{align*}for each $a\in A$.
