Subsection 8.6.5 (02GQ): Internal Comonads

We have a natural identification

\[ \left\{ \begin{gathered} \text{Comonads in}\\ \text{$\boldsymbol {\mathsf{Rel}}^{\mathord {\mathbin {\square }}}$ on $X$} \end{gathered} \right\} \cong \left\{ \text{Strict total orders on $X$}\right\} . \]

A comonad in $\boldsymbol {\mathsf{Rel}}^{\mathord {\mathbin {\square }}}$ on $X$ consists of a relation $R\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X$ together with maps

\begin{align*} \Delta _{R} & \colon R \subset R\mathbin {\square }R,\\ \epsilon _{R} & \colon R \subset \nabla _{X} \end{align*}

making the diagrams

commute. However, since all morphisms involved are inclusions, the commutativity of the above diagrams is automatic (Chapter 11: Categories, Item 4 of Proposition 11.2.7.1.2), and hence all that is left is the data of the two maps $\mu _{R}$ and $\eta _{R}$, which correspond respectively to the following conditions:

1.
For each $x,z\in X$, if $x\sim _{R}z$, then, for each $y\in X$, we have $x\sim _{R}y$ or $y\sim _{R}z$.
2.
For each $x,y\in X$, if $x\sim _{R}y$, then $x\neq y$.

Replacing $\sim _{R}$ with $<_{R}$ and taking the contrapositive of each condition, we obtain:

1.
For each $x,z\in X$, if there exists some $y\in X$ such that $x<_{R}y$ and $y<_{R}z$, then $x<_{R}z$.
2.
For each $x\in X$, we have $x\nless _{R}x$.

These are exactly the requirements for $R$ to be a strict linear order (). Conversely, any strict linear order $<_{R}$ gives rise to a pair of maps $\Delta _{<_{R}}$ and $\epsilon _{<_{R}}$, forming a comonad on $X$.

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

1.
The codensity monad $\operatorname {\mathrm{Ran}}_{R}(R)\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ is given by
for each $b\in B$. Thus, it corresponds to the preorder

\[ \mathord {\preceq _{\operatorname {\mathrm{Ran}}_{R}(R)}}\colon B\times B\to \{ \mathsf{t},\mathsf{f}\} \]

on $B$ obtained by declaring $b\preceq _{\operatorname {\mathrm{Ran}}_{R}(R)}b'$ iff the following equivalent conditions are satisfied:
1. (a)
  For each $a\in A$, if $a\sim _{R}b$, then $a\sim _{R}b'$.
2. (b)
  We have $R^{-1}(b)\subset R^{-1}(b')$.
2.
The dual codensity monad $\operatorname {\mathrm{Rift}}_{R}(R)\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}A$ is given by
for each $a\in A$. Thus, it corresponds to the preorder

\[ \mathord {\preceq _{\operatorname {\mathrm{Rift}}_{R}(R)}}\colon A\times A\to \{ \mathsf{t},\mathsf{f}\} \]

on $A$ obtained by declaring $a\preceq _{\operatorname {\mathrm{Rift}}_{R}(R)}a'$ iff the following equivalent conditions are satisfied:
1. (a)
  For each $a\in A$, if $a\sim _{R}b$, then $a'\sim _{R}b$.
2. (b)
  We have $R(a')\subset R(a)$.

The Clowder Project

8.6.5 Internal Comonads