Proposition 8.1.3.1.3 (00QW): Properties of Composition of Relations

8.1.3 Composition of Relations

Let $A$, $B$, and $C$ be sets and let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ and $S\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}C$ be relations.

Definition 8.1.3.1.1 ▶ Composition of Relations

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}}}=}}\left\{ \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} \right\} . \]
•
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 3: Sets, Definition 3.2.2.1.3.
•
Viewing relations as functions $A\to \mathcal{P}\webleft (B\webright )$, we define
where $\operatorname {\mathrm{Lan}}_{\chi _{B}}\webleft (S\webright )$ is computed by the formula

\begin{align*} \webleft [\operatorname {\mathrm{Lan}}_{\chi _{B}}\webleft (S\webright )\webright ]\webleft (V\webright ) & \cong \int ^{b\in B}\chi _{\mathcal{P}\webleft (B\webright )}\webleft (\chi _{b},V\webright )\odot S_{b}\\ & \cong \int ^{b\in B}\chi _{V}\webleft (b\webright )\odot S_{b}\\ & \cong \bigcup _{b\in B}\chi _{V}\webleft (b\webright )\odot S_{b}\\ & \cong \bigcup _{b\in V}S_{b} \end{align*}

for each $V\in \mathcal{P}\webleft (B\webright )$, so we have¹

\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 _{b\in R\webleft (a\webright )}S\webleft (b\webright ). \end{align*}

for each $a\in A$.

¹That is: the relation $R$ may send $a\in A$ to a number of elements $\left\{ b_{i}\right\} _{i\in I}$ in $B$, and then the relation $S$ may send the image of each of the $b_{i}$’s to a number of elements $\left\{ S\webleft (b_{i}\webright )\right\} _{i\in I}=\left\{ \left\{ c_{j_{i}}\right\} _{j_{i}\in J_{i}}\right\} _{i\in I}$ in $C$.

Example 8.1.3.1.2 ▶ Examples of Composition of Relations

Here are some examples of composition of relations.

1.
Composing Less/Greater Than Equal With Greater/Less Than Equal Signs. We have

\begin{align*} \mathord {\leq }\mathbin {\diamond }\mathord {\geq } & = \sim _{\mathrm{triv}},\\ \mathord {\geq }\mathbin {\diamond }\mathord {\leq } & = \sim _{\mathrm{triv}}. \end{align*}
2.
Composing Less/Greater Than Equal Signs With Less/Greater Than Equal Signs. We have

\begin{align*} \mathord {\leq }\mathbin {\diamond }\mathord {\leq } & = \mathord {\leq },\\ \mathord {\geq }\mathbin {\diamond }\mathord {\geq } & = \mathord {\geq }. \end{align*}

Proposition 8.1.3.1.3 ▶ Properties of Composition of Relations

Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$, $S\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}C$, and $T\colon C\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}D$ be relations.

1.
Interaction With Ranges and Domains. We have

\begin{align*} \mathrm{dom}\webleft (S\mathbin {\diamond }R\webright ) & \subset \mathrm{dom}\webleft (R\webright ),\\ \mathrm{range}\webleft (S\mathbin {\diamond }R\webright ) & \subset \mathrm{range}\webleft (S\webright ). \end{align*}
2.
Associativity. We have

\[ \webleft (T\mathbin {\diamond }S\webright )\mathbin {\diamond }R = T\mathbin {\diamond }\webleft (S\mathbin {\diamond }R\webright ). \]
3.
Unitality. We have

\begin{align*} \chi _{B}\mathbin {\diamond }R & = R,\\ R\mathbin {\diamond }\chi _{A} & = R. \end{align*}
4.
Interaction With Converses. We have

\[ \webleft (S\mathbin {\diamond }R\webright )^{\dagger } = R^{\dagger }\mathbin {\diamond }S^{\dagger }. \]
5.
Interaction With Composition. We have

\begin{align*} \chi _{B} & \subset R\mathbin {\diamond }R^{\dagger },\\ \chi _{A} & \subset R^{\dagger }\mathbin {\diamond }R. \end{align*}

Proof of Proposition 8.1.3.1.3.

Item 1: Interaction With Ranges and Domains

Clear.

Item 2: Associativity

Indeed, we have

\begin{align*} \webleft (T\mathbin {\diamond }S\webright )\mathbin {\diamond }R & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft (\int ^{c\in C}T^{-_{1}}_{c}\times S^{c}_{-_{2}}\webright )\mathbin {\diamond }R\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{b\in B}\webleft (\int ^{c\in C}T^{-_{1}}_{c}\times S^{c}_{b}\webright )\mathbin {\diamond }R^{b}_{-_{2}}\\ & = \int ^{b\in B}\int ^{c\in C}\webleft (T^{-_{1}}_{c}\times S^{c}_{b}\webright )\mathbin {\diamond }R^{b}_{-_{2}}\\ & = \int ^{c\in C}\int ^{b\in B}\webleft (T^{-_{1}}_{c}\times S^{c}_{b}\webright )\mathbin {\diamond }R^{b}_{-_{2}}\\ & = \int ^{c\in C}\int ^{b\in B}T^{-_{1}}_{c}\times \webleft (S^{c}_{b}\mathbin {\diamond }R^{b}_{-_{2}}\webright )\\ & = \int ^{c\in C}T^{-_{1}}_{c}\times \webleft (\int ^{b\in B}S^{c}_{b}\mathbin {\diamond }R^{b}_{-_{2}}\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{c\in C}T^{-_{1}}_{c}\times \webleft (S\mathbin {\diamond }R\webright )^{c}_{-_{2}}\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}T\mathbin {\diamond }\webleft (S\mathbin {\diamond }R\webright ). \end{align*}

In the language of relations, given $a\in A$ and $d\in D$, the stated equality witnesses the equivalence of the following two statements:

•
We have $a\sim _{\webleft (T\mathbin {\diamond }S\webright )\mathbin {\diamond }R}d$, i.e. there exists some $b\in B$ such that:
- •
  We have $a\sim _{R}b$;
- •
  We have $b\sim _{T\mathbin {\diamond }S}d$, i.e. there exists some $c\in C$ such that:
  - •
    We have $b\sim _{S}c$;
  - •
    We have $c\sim _{T}d$;
•
We have $a\sim _{T\mathbin {\diamond }\webleft (S\mathbin {\diamond }R\webright )}d$, i.e. there exists some $c\in C$ such that:
- •
  We have $a\sim _{S\mathbin {\diamond }R}c$, i.e. there exists some $b\in B$ such that:
  - •
    We have $a\sim _{R}b$;
  - •
    We have $b\sim _{S}c$;
- •
  We have $c\sim _{T}d$;

both of which are equivalent to the statement

•
There exist $b\in B$ and $c\in C$ such that $a\sim _{R}b\sim _{S}c\sim _{T}d$.

Item 3: Unitality

Indeed, we have

\begin{align*} \chi _{B}\mathbin {\diamond }R & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{x\in B}\webleft (\chi _{B}\webright )^{-_{1}}_{x}\times R^{x}_{-_{2}}\\ & = \bigvee _{x\in B}\webleft (\chi _{B}\webright )^{-_{1}}_{x}\times R^{x}_{-_{2}}\\ & = \bigvee _{\substack {x\in B\\ \begin{bgroup} x=-_{1} \end{bgroup}}}R^{x}_{-_{2}}\\ & = R^{-_{1}}_{-_{2}}, \end{align*}

and

\begin{align*} R\mathbin {\diamond }\chi _{A} & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{x\in A}R^{-_{1}}_{x}\times \webleft (\chi _{A}\webright )^{x}_{-_{2}}\\ & = \bigvee _{x\in B}R^{-_{1}}_{x}\times \webleft (\chi _{A}\webright )^{x}_{-_{2}}\\ & = \bigvee _{\substack {x\in B\\ \begin{bgroup} x=-_{2} \end{bgroup}}}R^{-_{1}}_{x}\\ & = R^{-_{1}}_{-_{2}}. \end{align*}

In the language of relations, given $a\in A$ and $b\in B$:

•
The equality

\[ \chi _{B}\mathbin {\diamond }R=R \]

witnesses the equivalence of the following two statements:
- •
  We have $a\sim _{b}B$.
- •
  There exists some $b'\in B$ such that:
  - •
    We have $a\sim _{R}b'$
  - •
    We have $b'\sim _{\chi _{B}}b$, i.e. $b'=b$.
•
The equality

\[ R\mathbin {\diamond }\chi _{A}=R \]

witnesses the equivalence of the following two statements:
- •
  There exists some $a'\in A$ such that:
  - •
    We have $a\sim _{\chi _{B}}a'$, i.e. $a=a'$.
  - •
    We have $a'\sim _{R}b$
- •
  We have $a\sim _{b}B$.

Item 4: Interaction With Converses

Clear.

Item 5: Interaction With Composition

Clear.

Statistics Cite

Noticed something off, or have any comments? Feel free to reach out!

•Email
•Discord

You can also use the contact form below: