6.3.12 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 6.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 ^{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$.

Example 6.3.12.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 6.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.

  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 Inverses. 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 6.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 ^{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:

  1. 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$;
  2. 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.

Footnotes

[1] 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$.
Previous
Next

View Subsection 6.3.12 as PDF

Statistics Cite

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

You can also use the contact form below: