The Clowder Project

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

1. 1.

   Viewing relations from $X$ to $A$ as subsets of $X\times A$, we have

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

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

   \begin{align*} (\operatorname {\mathrm{Rift}}_{R}(F))^{-_{1}}_{-_{2}} & = \int _{b\in B}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{b}_{-_{1}},F^{b}_{-_{2}})\\ & = \bigwedge _{b\in B}\mathbf{Hom}_{\{ \mathsf{t},\mathsf{f}\} }(R^{b}_{-_{1}},F^{b}_{-_{2}}),\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.

3. 3.

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

   \[ [\operatorname {\mathrm{Rift}}_{R}(F)](x)=\left\{ a\in A\ \middle |\ R(a)\subset F(x)\right\} \]

   for each $a\in A$.

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 X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be relations.

1. 1.

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

   \[ \begin{array}{ccc} \operatorname {\mathrm{Rift}}_{(-)}(F)\colon \mkern -15mu & \mathbf{Rel}(A,B)^{\mathsf{op}} \mkern -17.5mu& {}\mathbin {\to }\mathbf{Rel}(B,X),\\ \operatorname {\mathrm{Rift}}_{R}\colon \mkern -15mu & \mathbf{Rel}(A,X) \mkern -17.5mu& {}\mathbin {\to }\mathbf{Rel}(B,X),\\ \operatorname {\mathrm{Rift}}_{(-_{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{Rift}}_{R_{2}}(F_{1})\subset \operatorname {\mathrm{Rift}}_{R_{1}}(F_{2})$.

2. 2.

   Interaction With Composition. We have

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

   and an equality

   
   of pasting diagrams in $\boldsymbol {\mathsf{Rel}}$.

3. 3.

   Interaction With Converses. We have

   \[ \operatorname {\mathrm{Rift}}_{R}(F)^{\dagger } = \operatorname {\mathrm{Ran}}_{R^{\dagger }}(F^{\dagger }). \]
4. 4.

   Interaction With Inverse Images. We have

   
   where $\operatorname {\mathrm{Ran}}_{\chi _{A}}\big (F^{\dagger }\big )$ is computed by the formula
   \begin{align*} [\operatorname {\mathrm{Ran}}_{\chi _{A}}\big (F^{\dagger }\big )](U) & \cong \int _{a\in A}\chi _{\mathcal{P}(B)^{\mathsf{op}}}(U,\chi _{a})\pitchfork F^{\dagger }(a)\\ & \cong \int _{a\in A}\chi _{\mathcal{P}(B)}(\chi _{a},U)\pitchfork F^{-1}(a)\\ & \cong \int _{a\in A}\chi _{U}(a)\pitchfork F(a)\\ & \cong \bigcap _{a\in A}\chi _{U}(a)\pitchfork F(a)\\ & \cong \bigcap _{a\in U}F(a) \end{align*}

   for each $U\in \mathcal{P}(A)$, so we have

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

   for each $a\in A$.