The Clowder Project

The notion of a relation is a decategorification of that of a profunctor:

1. 1.

   A profunctor from a category $\mathcal{C}$ to a category $\mathcal{D}$ is a functor

   \[ \mathfrak {p}\colon \mathcal{D}^{\mathsf{op}}\times \mathcal{C}\to \mathsf{Sets}. \]

Extending Remark 8.1.2.1.1, the equivalent definitions of relations in Definition 8.1.1.1.1 are also related to the corresponding ones for profunctors (), which state that a profunctor $\mathfrak {p}\colon \mathcal{C}\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}\mathcal{D}$ is equivalently:

1. 1.

   A functor $\mathfrak {p}\colon \mathcal{D}^{\mathsf{op}}\times \mathcal{C}\to \mathsf{Sets}$.

2. 2.

   A functor $\mathfrak {p}\colon \mathcal{C}\to \mathsf{PSh}\webleft (\mathcal{D}\webright )$.

3. 3.

   A functor $\mathfrak {p}\colon \mathcal{D}^{\mathsf{op}}\to \mathsf{CoPSh}\webleft (\mathcal{C}\webright )$.

4. 4.

   A colimit-preserving functor $\mathfrak {p}\colon \mathsf{PSh}\webleft (\mathcal{C}\webright )\to \mathsf{PSh}\webleft (\mathcal{D}\webright )$.

5. 5.

   A limit-preserving functor $\mathfrak {p}\colon \mathsf{CoPSh}\webleft (\mathcal{D}\webright )^{\mathsf{op}}\to \mathsf{CoPSh}\webleft (\mathcal{C}\webright )^{\mathsf{op}}$.

Indeed:

• •

  The equivalence between Item 1 and Item 2 (and also that between Item 1 and Item 3, which is proved analogously) is an instance of currying, both for profunctors as well as for relations, using the isomorphisms

  \begin{align*} \mathsf{Sets}\webleft (A\times B,\{ \mathsf{true},\mathsf{false}\} \webright ) & \cong \mathsf{Sets}\webleft (A,\mathsf{Sets}\webleft (B,\{ \mathsf{true},\mathsf{false}\} \webright )\webright )\\ & \cong \mathsf{Sets}\webleft (A,\mathcal{P}\webleft (B\webright )\webright ), \end{align*}

  and

  \begin{align*} \mathsf{Fun}\webleft (\mathcal{D}^{\mathsf{op}}\times \mathcal{D},\mathsf{Sets}\webright ) & \cong \mathsf{Fun}\webleft (\mathcal{C},\mathsf{Fun}\webleft (\mathcal{D}^{\mathsf{op}},\mathsf{Sets}\webright )\webright )\\ & \cong \mathsf{Fun}\webleft (\mathcal{C},\mathsf{PSh}\webleft (\mathcal{D}\webright )\webright ). \end{align*}
• •

  The equivalence between Item 2 and Item 4 follows from the universal properties of:

  • •

    The powerset $\mathcal{P}\webleft (X\webright )$ of a set $X$ as the free cocompletion of $X$ via the characteristic embedding

    \[ \chi _{\webleft (-\webright )} \colon X \hookrightarrow \mathcal{P}\webleft (X\webright ) \]

    of $X$ into $\mathcal{P}\webleft (X\webright )$, as stated and proved in Chapter 4: Constructions With Sets, Proposition 4.4.5.1.1.

  • •

    The category $\mathsf{PSh}\webleft (\mathcal{C}\webright )$ of presheaves on a category $\mathcal{C}$ as the free cocompletion of $\mathcal{C}$ via the Yoneda embedding

    \[ {\text{よ}}\colon \mathcal{C} \hookrightarrow \mathsf{PSh}\webleft (\mathcal{C}\webright ) \]

    of $\mathcal{C}$ into $\mathsf{PSh}\webleft (\mathcal{C}\webright )$, as stated and proved in , of .

• •

  The equivalence between Item 3 and Item 5 follows from the universal properties of:

  • •

    The powerset $\mathcal{P}\webleft (X\webright )$ of a set $X$ as the free completion of $X$ via the characteristic embedding

    \[ \chi _{\webleft (-\webright )} \colon X \hookrightarrow \mathcal{P}\webleft (X\webright ) \]

    of $X$ into $\mathcal{P}\webleft (X\webright )$, as stated and proved in Chapter 4: Constructions With Sets, Proposition 4.4.6.1.1.

  • •

    The category $\mathsf{CoPSh}\webleft (\mathcal{D}\webright )^{\mathsf{op}}$ of copresheaves on a category $\mathcal{D}$ as the free completion of $\mathcal{D}$ via the dual Yoneda embedding

    \[ \style {display: inline-block; transform: rotate(180deg)}{よ}\mkern -2.5mu\colon \mathcal{D} \hookrightarrow \mathsf{CoPSh}\webleft (\mathcal{D}\webright )^{\mathsf{op}} \]

    of $\mathcal{D}$ into $\mathsf{CoPSh}\webleft (\mathcal{D}\webright )^{\mathsf{op}}$, as stated and proved in , of .