One of the great joys of category theory is the way you can so often watch familiar structures emerge unexpectedly from general constructions. It’s particularly amusing to apply the formal theory of monads to the 2-category Rel of sets and relations. (I mean the 2-category whose objects are sets, whose 1-cells are relations, and where there is a unique 2-cell from R to S just when R is a subset of S.) This is an easy example to study because all diagrams of 2-cells commute, since by definition there is at most one 2-cell between any pair of relations.
What’s an adjunction in Rel? It must consist of two relations like this:
such that 1X ⊆ GF and FG ⊆ 1Y (subject to a couple of equations that are between 2-cells, so always hold). It’s easy to check that this is equivalent to saying:
- for every x∈X there is a unique y∈Y for which x F y,
- x F y ⇔ y G x.
In other words, an adjunction in Rel is just a function!
We know that this adjunction will induce a monad on X and a comonad on Y, so what are monads and comonads? A monad on X is a relation R on X such that 1X ⊆ R and RR ⊆ R. The first condition says that R is reflexive, and the second condition says that it’s transitive. So a monad is an reflexive, transitive relation – otherwise known as a preorder.
What about a comonad? (Can you guess?) It should be a relation S on Y such that S ⊆ 1Y and S ⊆ SS. The first condition says that no element is related to anything other than itself, which means that S is essentially just a subset of Y, and the second condition is therefore redundant. So a comonad is just a subset.
Therefore a function induces a preorder on its source (which happens to be an equivalence relation: it’s the kernel of the function) and picks out a subset of its target (the range of the function). You knew that already, but maybe you didn’t know it was an instance of the theory of adjunctions. I didn’t, at any rate.
Something interesting is happening here. The monad induced by an adjunction is always an equivalence relation, i.e. a symmetric preorder. Yet there are certainly non-symmetric preorders – any non-trivial partial order, for example. So clearly, and in contrast with the situation in Cat, not every monad is induced by an adjunction. More on this in a second.
How about algebras for a monad? An algebra for a monad R on X is a relation P: A → X such that RP ⊆ P. If R is an equivalence relation then P is really a relation between A and the set of equivalence classes of R. That description answers the next obvious question, because it shows that the Eilenberg-Moore object of an equivalence relation (qua monad) is just its set of equivalence classes. The canonical adjunction between X and the Eilenberg-Moore object is the function that takes each element to its equivalence class. On the other hand a monad that is not an equivalence relation (because it’s not symmetric) cannot have an Eilenberg-Moore object. (If it did, then it would be induced by an adjunction.)
Similarly a coalgebra Q: B → Y for a comonad S on Y is a relation such that Q ⊆ SQ, or in plain terms a relation between B and the subset of Y picked out by S. So the co-Eilenberg-Moore object for a comonad is just the subset that it picks out.
Is this any use for anything? Who knows, but it’s fun…
PS. I’ve heard it said that Rel is often best understood as the full subcategory of discrete objects in RPro, the category of relational profunctors. An object of RPro is a preordered set, and an arrow R: X → Y is a relation with the property that a ≤ b R c ≤ d ⇒ a R d. (In Australian terms, RPro is V-Mod for V=2.) I think the usual reason for regarding Rel as embedded in RPro is that RPro has good (co)completeness properties. What matters here is that it has an Eilenberg-Moore object for every monad, so the monads that don’t have Eilenberg-Moore objects in Rel do have them in RPro. That makes intuitive sense too, since we’ve already seen that a monad in Rel is a preorder, and the objects of RPro are already preorders.
In fact every preorder is isomorphic in RPro to a partial order, obtained by collapsing the equivalence classes, so it doesn’t do any harm to restrict our attention to those objects that are already partial orders. Then a monad R on X is a preorder that’s compatible with (i.e. stronger than) the existing partial order on X, and the Eilenberg-Moore object of R is the partial order obtained from R by identifying R-equivalent elements of X.
PPS. Above I’ve been thinking of Rel as a 2-category, but secretly it’s a 5-category at least. (Why? :-))