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\} . \]
-
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$.
-
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$.
-
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:
-
(a)
For each $a\in A$, if $a\sim _{R}b$, then $a\sim _{R}b'$.
-
(a)
-
(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:
8.6.5 Internal Comonads
Let $X$ be a set.
Proof of Proposition 8.6.5.1.1.
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
Replacing $\sim _{R}$ with $<_{R}$ and taking the contrapositive of each condition, we obtain:
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.
