Item 1 (02A7) — The Clowder Project

8.5.17 Internal Right Kan Extensions

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

Motivation 8.5.17.1.1 ▶ Setting for Internal Right Kan Extensions in $\boldsymbol {\mathsf{Rel}}$

We want to understand internal right Kan extensions in $\boldsymbol {\mathsf{Rel}}$, which look like this:

Note in particular here that $F\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X$ is a relation from $A$ to $X$. These will form a functor

\[ \operatorname {\mathrm{Ran}}_{R}\colon \mathbf{Rel}(A,X)\to \mathbf{Rel}(B,X) \]

that is right adjoint to the precomposition by $R$ functor

\[ R^{*}\colon \mathbf{Rel}(B,X)\to \mathbf{Rel}(A,X). \]

Proposition 8.5.17.1.2 ▶ Internal Right Kan Extensions in $\boldsymbol {\mathsf{Rel}}$

The internal right Kan extension of $F$ along $R$ is the relation $\operatorname {\mathrm{Ran}}_{R}(F)$ described as follows:

1.
Viewing relations from $B$ to $X$ as subsets of $B\times X$, we have

\[ \operatorname {\mathrm{Ran}}_{R}(F)=\left\{ (b,x)\in B\times X\ \middle |\ \begin{aligned} & \text{for each $a\in A$, if $a\sim _{R}b$,}\\ & \text{then we have $a\sim _{F}x$}\end{aligned} \right\} . \]

Viewing relations as functions $B\times X\to \{ \mathsf{true},\mathsf{false}\} $, we have

\begin{align*} (\operatorname {\mathrm{Ran}}_{R}(F))^{-_{1}}_{-_{2}} & = \int _{a\in A}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{-_{2}}_{a},F^{-_{1}}_{a})\\ & = \bigwedge _{a\in A}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{-_{2}}_{a},F^{-_{1}}_{a}),\end{align*}

where the meet $\bigwedge $ is taken in the poset $(\{ \mathsf{true},\mathsf{false}\} ,\preceq )$ of Chapter 3: Sets, Definition 3.2.2.1.3.

Viewing relations as functions $B\to \mathcal{P}(X)$, we have

where $\operatorname {\mathrm{Ran}}_{\chi '_{B}}(F)$ is computed by the formula

\begin{align*} [\operatorname {\mathrm{Ran}}_{\chi '_{A}}(F)](V) & \cong \int _{a\in A}\chi _{\mathcal{P}(A)^{\mathsf{op}}}(V,\chi _{a})\pitchfork F(a)\\ & \cong \int _{a\in A}\chi _{\mathcal{P}(A)}(\chi _{a},V)\pitchfork F(a)\\ & \cong \int _{a\in A}\chi _{V}(a)\pitchfork F(a)\\ & \cong \bigcap _{a\in A}\chi _{V}(a)\pitchfork F(a)\\ & \cong \bigcap _{a\in V}F(a) \end{align*}

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

\[ [\operatorname {\mathrm{Ran}}_{R}(F)](b)=\bigcap _{a\in R^{-1}(b)}F(a) \]

for each $b\in B$.

Proof of Proposition 8.5.17.1.2.

We have

\begin{align*} \operatorname {\mathrm{Hom}}_{\mathbf{Rel}(A,X)}(F\mathbin {\diamond }R,T) & \cong \int _{a\in A}\int _{x\in X}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }((F\mathbin {\diamond }R)^{x}_{a},T^{x}_{a})\\ & \cong \int _{a\in A}\int _{x\in X}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }((\int ^{b\in B}F^{x}_{b}\times R^{b}_{a}),T^{x}_{a})\\ & \cong \int _{a\in A}\int _{x\in X}\int _{b\in B}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(F^{x}_{b}\times R^{b}_{a},T^{x}_{a})\\ & \cong \int _{a\in A}\int _{x\in X}\int _{b\in B}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(F^{x}_{b},\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{b}_{a},T^{x}_{a}))\\ & \cong \int _{b\in B}\int _{x\in X}\int _{a\in A}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(F^{x}_{b},\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{b}_{a},T^{x}_{a}))\\ & \cong \int _{b\in B}\int _{x\in X}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(F^{x}_{b},\int _{a\in A}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{b}_{a},T^{x}_{a}))\\ & \cong \operatorname {\mathrm{Hom}}_{\mathbf{Rel}(B,X)}(F,\int _{a\in A}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{-_{2}}_{a},T^{-_{1}}_{a}))\end{align*}

naturally in each $F\in \mathbf{Rel}(B,X)$ and each $T\in \mathbf{Rel}(A,X)$, showing that

\[ \int _{a\in A}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{-_{2}}_{a},T^{-_{1}}_{a}) \]

is right adjoint to the precomposition functor $-\mathbin {\diamond }R$, being thus the right Kan extension along $R$. Here we have used the following results, respectively (i.e. for each $\cong $ sign):

1.
Chapter 8: Relations, Item 1 of Proposition 8.1.1.1.5.
2.
Definition 8.1.3.1.1.
3.
, of .
4.
Chapter 3: Sets, Proposition 3.2.2.1.5.
5.
, of .
6.
, of .
7.
Chapter 8: Relations, Item 1 of Proposition 8.1.1.1.5.

This finishes the proof.

Example 8.5.17.1.3 ▶ Examples of Internal Right Kan Extensions of Relations

Here are some examples of internal right Kan extensions of relations.

1.
Orthogonal Complements. Let $A=B=X=\mathcal{V}$ be an inner product space, and let $R=F=\mathord {\perp }$ be the orthogonality relation, so that we have

\begin{align*} R(v) & = v^{\perp }\\ F(u) & = u^{\perp }, \end{align*}

for each $u,v\in \mathcal{V}$, where

\[ v^{\perp }\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ u\in V\ \middle |\ v\perp u\right\} \]

is the orthogonal complement of $v$. The right Kan extension $\operatorname {\mathrm{Ran}}_{R}(F)$ is then given by

\begin{align*} [\operatorname {\mathrm{Ran}}_{R}(F)](v) & = \bigcap _{u\in R^{-1}(v)}F(u)\\ & = \bigcap _{\substack {u\in V\\ \begin{bgroup} u\perp v \end{bgroup}}}u^{\perp }\\ & = (v^{\perp })^{\perp },\end{align*}

the double orthogonal complement. In particular:
- •
  If $\mathcal{V}$ is finite-dimensional, then $[\operatorname {\mathrm{Ran}}_{R}(F)](v)=\mathrm{Span}(v)$.
- •
  If $\mathcal{V}$ is a Hilbert space, then $[\operatorname {\mathrm{Ran}}_{R}(F)](v)=\overline{\mathrm{Span}(v)}$.
2.
Galois Connections and Closure Operators. Let:
- •
  $B=X=(P,\preceq _{P})$ and $A=(Q,\preceq _{Q})$ be posets;
- •
  $(f,g)$ be a Galois connection (adjunction) between $P$ and $Q$;
- •
  $R,F\colon Q\mathrel {\rightrightarrows \kern -9.5pt\mathrlap {|}\kern 6pt}P$ be the relations defined by
  
  \begin{align*} R(q) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ p\in P\ \middle |\ q\preceq _{Q}f(p)\right\} ,\\ F(q) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ p\in P\ \middle |\ p\preceq _{P}g(q)\right\} \end{align*}
  
  for each $q\in Q$.
We have

\begin{align*} [\operatorname {\mathrm{Ran}}_{R}(F)](p) & = \bigcap _{q\in R^{-1}(p)}F(q)\\ & = \bigcap _{\substack {q\in Q\\ \begin{bgroup} q\preceq _{Q}f(p) \end{bgroup}}}\left\{ p\in P\ \middle |\ p\preceq _{P}g(q)\right\} \\ & = \left\{ p\in P\ \middle |\ p\preceq _{P}g(f(q))\right\} \\ & = \mathord {\downarrow }\mkern 5mug(f(p)), \end{align*}

the down set of $g(f(p))$. In other words, $\operatorname {\mathrm{Ran}}_{R}(F)$ is the closure operator on $P$ associated with the Galois connection $(f,g)$.

Proposition 8.5.17.1.4 ▶ Properties of Internal Right Kan Extensions in $\boldsymbol {\mathsf{Rel}}$

Let $A$, $B$, $C$ and $X$ be sets and 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 $F\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X$ be relations.

1.
Functoriality. The assignments $R,F,(R,F)\mapsto \operatorname {\mathrm{Ran}}_{R}(F)$ define functors

\[ \begin{array}{ccc} \operatorname {\mathrm{Ran}}_{(-)}(F)\colon \mkern -15mu & \mathbf{Rel}(A,B)^{\mathsf{op}} \mkern -17.5mu& {}\mathbin {\to }\mathbf{Rel}(B,X),\\ \operatorname {\mathrm{Ran}}_{R}\colon \mkern -15mu & \mathbf{Rel}(A,X) \mkern -17.5mu& {}\mathbin {\to }\mathbf{Rel}(B,X),\\ \operatorname {\mathrm{Ran}}_{(-_{1})}(-_{2})\colon \mkern -15mu & \mathbf{Rel}(A,X)\times \mathbf{Rel}(A,B)^{\mathsf{op}} \mkern -17.5mu& {}\mathbin {\to }\mathbf{Rel}(B,X). \end{array} \]

In other words, given relations
if $R_{1}\subset R_{2}$ and $F_{1}\subset F_{2}$, then $\operatorname {\mathrm{Ran}}_{R_{2}}(F_{1})\subset \operatorname {\mathrm{Ran}}_{R_{1}}(F_{2})$.
2.
Interaction With Composition. We have

\[ \operatorname {\mathrm{Ran}}_{S\mathbin {\diamond }R}(F)= \operatorname {\mathrm{Ran}}_{S}(\operatorname {\mathrm{Ran}}_{R}(F)) \]

and an equality
of pasting diagrams in $\boldsymbol {\mathsf{Rel}}$.
3.
Interaction With Converses. We have

\[ \operatorname {\mathrm{Ran}}_{R}(F)^{\dagger } = \operatorname {\mathrm{Rift}}_{R^{\dagger }}(F^{\dagger }). \]
4.
Interaction With Inverse Images. We have

\[ [\operatorname {\mathrm{Ran}}_{R}(F)]^{-1}(x)=\left\{ b\in B\ \middle |\ R^{-1}(b)\subset F^{-1}(x)\right\} \]

for each $x\in X$.

Proof of Proposition 8.5.17.1.4.

Item 1: Functoriality

We have

\begin{align*} [\operatorname {\mathrm{Ran}}_{R_{2}}(F_{1})](b) & = \bigcap _{a\in R^{-1}_{2}(b)}F_{1}(a)\\ & \subset \bigcap _{a\in R^{-1}_{1}(b)}F_{1}(a)\\ & \subset \bigcap _{a\in R^{-1}_{1}(b)}F_{2}(a)\\ & = [\operatorname {\mathrm{Ran}}_{R_{1}}(F_{2})](b) \end{align*}

for each $b\in B$, so we therefore have $\operatorname {\mathrm{Ran}}_{R_{2}}(F_{1})\subset \operatorname {\mathrm{Ran}}_{R_{1}}(F_{2})$.

Item 2: Interaction With Composition

This holds in a general bicategory with the necessary right Kan extensions, being therefore a special case of

Item 3: Interaction With Converses

We have

\begin{align*} [\operatorname {\mathrm{Rift}}_{R^{\dagger }}(F^{\dagger })](x) & = \left\{ b\in B\ \middle |\ R^{\dagger }(b)\subset F^{\dagger }(x)\right\} \\ & = \left\{ b\in B\ \middle |\ R^{-1}(b)\subset F^{-1}(x)\right\} \\ & = \operatorname {\mathrm{Ran}}_{R}(F)^{-1}(x)\\ & = \operatorname {\mathrm{Ran}}_{R}(F)^{\dagger }(x)\end{align*}

where we have used Proposition 8.5.18.1.2 and Item 4.

Item 4: Interaction With Inverse Images

We proceed in a few steps.

•
We have $b\in [\operatorname {\mathrm{Ran}}_{R}(F)]^{-1}(x)$ iff, for each $a\in R^{-1}(b)$, we have $b\in F(a)$.
•
This holds iff, for each $a\in R^{-1}(b)$, we have $a\in F^{-1}(b)$.
•
This holds iff $R^{-1}(b)\subset F^{-1}(b)$.

This finishes the proof.

Statistics Cite

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

•Email
•Discord

You can also use the contact form below: