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}. \]
2. 2.

   A relation on sets $A$ and $B$ is a function

   \[ R\colon A\times B\to \{ \mathsf{true},\mathsf{false}\} . \]

Here we notice that:

• •

  The opposite $X^{\mathsf{op}}$ of a set $X$ is itself, as $\webleft (-\webright )^{\mathsf{op}}\colon \mathsf{Cats}\to \mathsf{Cats}$ restricts to the identity endofunctor on $\mathsf{Sets}$.

• •

  The values that profunctors and relations take are analogous:

  • •

    A category is enriched over the category

    \[ \mathsf{Sets}\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathsf{Cats}_{0} \]

    of sets, with profunctors taking values on it.

  • •

    A set is enriched over the set

    \[ \{ \mathsf{true},\mathsf{false}\} \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathsf{Cats}_{-1} \]

    of classical truth values, with relations taking values on it.

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 .