Subsection 7.3.12 (00QT): Composition of Relations

Style	Class	Font	Theorem Environments
Style 1	`book`	Alegreya Sans	`tcbthm`
Style 2	`book`	Alegreya Sans	`amsthm`
Style 3	`book`	Arno*	`amsthm`
Style 4	`book`	Computer Modern	`amsthm`

7.3.12 Composition of Relations

Let $A$, $B$, and $C$ be sets and let $R\subset A\times B$ and $S\subset B\times C$ be relations.

Definition 7.3.12.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}}}=}}\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 ^{y\in B}S^{-_{1}}_{y}\times R^{y}_{-_{2}}\\ & = \bigvee _{y\in B}S^{-_{1}}_{y}\times R^{y}_{-_{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¹
\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$.

¹That is: the relation $R$ may send $a\in A$ to a number of elements $\webleft\{ b_{i}\webright\} _{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 $\webleft\{ S\webleft (b_{i}\webright )\webright\} _{i\in I}=\webleft\{ \webleft\{ c_{j_{i}}\webright\} _{j_{i}\in J_{i}}\webright\} _{i\in I}$ in $C$.

Example 7.3.12.1.2 ▶ Examples of Composition of Relations

Here are some examples of composition of relations.

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*}
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 7.3.12.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.

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*}
Associativity. We have
\[ \webleft (T\mathbin {\diamond }S\webright )\mathbin {\diamond }R = T\mathbin {\diamond }\webleft (S\mathbin {\diamond }R\webright ). \]
Unitality. We have
\begin{align*} \chi _{B}\mathbin {\diamond }R & = R,\\ R\mathbin {\diamond }\chi _{A} & = R. \end{align*}
Interaction With Inverses. We have
\[ \webleft (S\mathbin {\diamond }R\webright )^{\dagger } = R^{\dagger }\mathbin {\diamond }S^{\dagger }. \]
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 7.3.12.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 ^{y\in C}T^{-_{1}}_{x}\times S^{x}_{-_{2}}\webright )\mathbin {\diamond }R\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{x\in B}\webleft (\int ^{y\in C}T^{-_{1}}_{x}\times S^{x}_{y}\webright )\mathbin {\diamond }R^{y}_{-_{2}}\\ & = \int ^{x\in B}\int ^{y\in C}\webleft (T^{-_{1}}_{x}\times S^{x}_{y}\webright )\mathbin {\diamond }R^{y}_{-_{2}}\\ & = \int ^{y\in C}\int ^{x\in B}\webleft (T^{-_{1}}_{x}\times S^{x}_{y}\webright )\mathbin {\diamond }R^{y}_{-_{2}}\\ & = \int ^{y\in C}\int ^{x\in B}T^{-_{1}}_{x}\times \webleft (S^{x}_{y}\mathbin {\diamond }R^{y}_{-_{2}}\webright )\\ & = \int ^{x\in B}T^{-_{1}}_{x}\times \webleft (\int ^{y\in C}S^{x}_{y}\mathbin {\diamond }R^{y}_{-_{2}}\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{x\in B}T^{-_{1}}_{x}\times \webleft (S\mathbin {\diamond }R\webright )^{x}_{-_{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:
1. We have $a\sim _{R}b$;
2. We have $b\sim _{T\mathbin {\diamond }S}d$, i.e. there exists some $c\in C$ such that:
  1. We have $b\sim _{S}c$;
  2. 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:
1. We have $a\sim _{S\mathbin {\diamond }R}c$, i.e. there exists some $b\in B$ such that:
  1. We have $a\sim _{R}b$;
  2. We have $b\sim _{S}c$;
2. 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\\ x=-_{1} }}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\\ x=-_{2} }}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:
1. We have $a\sim _{b}B$.
2. There exists some $b'\in B$ such that:
  1. We have $a\sim _{R}b'$
  2. 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:
1. There exists some $a'\in A$ such that:
  1. We have $a\sim _{\chi _{B}}a'$, i.e. $a=a'$.
  2. We have $a'\sim _{R}b$
2. We have $a\sim _{b}B$.

Item 4: Interaction With Inverses

Clear.

Item 5: Interaction With Composition

Clear.

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

You can also use the contact form below: