Item 2 (02FC) — The Clowder Project

8.5.15 Internal Left Kan Extensions

Proposition 8.5.15.1.1 ▶ Internal Left Kan Extensions in $\boldsymbol {\mathsf{Rel}}$

Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation.

1.
Non-Existence of All Internal Left Kan Extensions in $\boldsymbol {\mathsf{Rel}}$. Not all relations in $\boldsymbol {\mathsf{Rel}}$ admit left Kan extensions.
2.
Characterisation of Relations Admitting Internal Left Kan Extensions Along Them. The following conditions are equivalent:
1. (a)
  The left Kan extension
  
  \[ \operatorname {\mathrm{Lan}}_{R}\colon \mathbf{Rel}(A,X)\to \mathbf{Rel}(B,X) \]
  
  along $R$ exists.
2. (b)
  The relation $R$ admits a left adjoint in $\boldsymbol {\mathsf{Rel}}$.
3. (c)
  The relation $R$ is of the form $\operatorname {\mathrm{Gr}}(f)$ (as in Definition 8.2.2.1.1) for some function $f$.

Proof of Proposition 8.5.15.1.1.

Item 1: Non-Existence of All Internal Left Kan Extensions in $\boldsymbol {\mathsf{Rel}}$

By Item 2, it suffices to take a relation that doesn’t have a left adjoint.

Item 2: Characterisation of Relations Admitting Left Kan Extensions Along Them

This proof is mostly due to Tim Campion, via [Campion, Answer to “Existence and characterisations of left Kan extensions and liftings in the bicategory of relations I”].

•
We may view precomposition

\[ -\mathbin {\diamond }R\colon \mathrm{Rel}(B,C)\to \mathrm{Rel}(A,C) \]

with $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ as a cocontinuous functor from $\mathcal{P}(B\times C)$ to $\mathcal{P}(A\times C)$ (via Item 5 of Definition 8.1.1.1.1).
•
By the adjoint functor theorem (), this map has a left adjoint iff it preserves limits.
•
If $C=\text{Ø}$, this holds trivially.
•
Otherwise, $C$ admits $\mathrm{pt}$ as a retract, and we reduce to the case $C=\mathrm{pt}$ via .
•
For the case $C=\mathrm{pt}$, a relation $T\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}\mathrm{pt}$ is the same as a subset of $B$, and $-\mathbin {\diamond }R$ becomes the inverse image functor $R^{-1}$ of .
•
Now, again by the adjoint functor theorem, $R^{-1}$ preserves limits exactly when it has a left adjoint.
•
Finally, $R^{-1}$ has a left adjoint precisely when $R=\operatorname {\mathrm{Gr}}(f)$ for $f$ a function ( of Proposition 8.7.3.1.3).

This finishes the proof.

Example 8.5.15.1.2 ▶ Internal Left Kan Extensions Along Functions

Given a function $f\colon A\to B$, the left Kan extension

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

along $f$ exists by Item 2 of Proposition 8.5.15.1.1. Explicitly, given a relation $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X$, the left Kan extension

may be described as follows:

1.
We declare $b\sim _{\operatorname {\mathrm{Lan}}_{f}(R)}x$ iff there exists some $a\in R$ such that $b=f(a)$ and $a\sim _{R}x$.
2.
We have¹

\[ [\operatorname {\mathrm{Lan}}_{f}(R)](b)=\bigcup _{a\in f^{-1}(b)}R(a) \]

for each $b\in B$.

¹Cf. Item 3 of Proposition 8.5.17.1.2.

Remark 8.5.15.1.3 ▶ Illustrating the Failure of Internal Left Kan Extensions in $\boldsymbol {\mathsf{Rel}}$ to Exist

Following Example 8.5.15.1.2, given a relation $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ and a relation $F\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X$, we could perhaps try to define an “honorary” left Kan extension

\[ \operatorname {\mathrm{Lan}}'_{R}(F)\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X \]

\[ [\operatorname {\mathrm{Lan}}'_{F}(F)](b)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{a\in R^{-1}(b)}F(a) \]

for each $b\in B$.

The failure of $\operatorname {\mathrm{Lan}}'_{R}(F)$ to be a Kan extension can then be seen as follows. Let $G\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X$ be a relation. If $\operatorname {\mathrm{Lan}}'_{R}(F)$ were a left Kan extension, then the following conditions would be equivalent:

1.
For each $b\in B$, we have $\bigcup _{a\in R^{-1}(b)}F(a)\subset G(b)$.

2.
For each $a\in A$, we have $F(a)\subset \bigcup _{b\in R(a)}G(b)$.

The issue is two-fold:

•
Totality. If $R$ isn’t total, then the implication Item 1 $\Rightarrow $ Item 2 fails.
•
Functionality. If $R$ isn’t functional, then the implication Item 2 $\Rightarrow $ Item 1 fails.

Question 8.5.15.1.4 ▶ Existence of Specific Internal Left Kan Extensions of Relations

Given relations $S\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X$ and $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$, is there a characterisation of when the left Kan extension¹

\[ \operatorname {\mathrm{Lan}}_{S}(R)\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X \]

exists in terms of properties of $R$ and $S$?

This question also appears as [Emily, Existence and characterisations of left Kan extensions and liftings in the bicategory of relations II].

¹Specifically for $R$ and $S$, not $\operatorname {\mathrm{Lan}}_{S}$ the functor.

Statistics Cite

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

•Email
•Discord

You can also use the contact form below: