Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation.
-
(c)
The relation $R$ is of the form $\operatorname {\mathrm{Gr}}(f)$ (as in Definition 8.2.2.1.1) for some function $f$.
-
•
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).
-
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 have1
\[ [\operatorname {\mathrm{Lan}}_{f}(R)](b)=\bigcup _{a\in f^{-1}(b)}R(a) \]for each $b\in B$.
- 1Cf. Item 3 of Proposition 8.5.17.1.2.
-
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)$.
- 1Specifically for $R$ and $S$, not $\operatorname {\mathrm{Lan}}_{S}$ the functor.
8.5.15 Internal Left Kan Extensions
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”].
This finishes the proof.
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
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 \]
by
\[ [\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:
The issue is two-fold:
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 extension1
\[ \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].
