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 *1 _{X} ⊆ GF* and

*FG ⊆ 1*(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:

_{Y}- 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 *1 _{X} ⊆ 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 ⊆ 1 _{Y}* 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? :-))

Wow! You have discoverd that the enormously succesful category

Set, which seems artificial if you view it from afar, –all the condictions for a relation to be a map are on the source, none on the target,– is the adjunction category of a really natural 2 categoryRel.Moreover the theory of monads is the canonical factorization of a map, enormously useful in so many contexts.

And it explains the assymetry associated to the axiom of choice. I think this comes from the choice of the 2-cells as inclusions.

I wonder how it would look a similar treatment when choosing surjections as the 2-cells. The category of adjunctions should be something “dual” to Sets.

Mmm… fascinating!

I certainly didn’t

discoverthat functions can be defined as adjunctions inRel! The idea essentially goes back to section 3 of Lawvere’s Metric spaces, generalized logic and closed categories (1973), and it’s explicitly stated in the introduction to Street’s Cauchy characterization of enriched categories (1981).(Aren’t TAC reprints wonderful?)

L. Alonso’s remark that

Relis more natural thanSetreminds me of something I’ve vaguely wondered about but never seriously investigated.The usual “ladder” of strict

n-categories can be regarded as a process of iterated enrichment: ifTis the terminal (one object, one morphism) category, thenT-Catis sets and functions,(T-Cat)-Catis categories and functors,((T-Cat)-Cat)-Catis 2-categories and 2-functors, and so on.But – just as there is no obvious reason to regard functions as more primitive than relations – there is no obvious reason to regard functors as more primitive than modules (aka distributors, profunctors, bimodules). The analogous progression

T-Mod,(T-Mod)-Modetc. takes a little bit longer to get going:T-Modhas only two isomorphism classes of objects, so it’s equivalent to the category2, but then(T-Mod)-ModisRProand we get going properly.This is interestingly close to the progression postulated by John Baez here, for different reasons. (

Update: Appendix A.1 of these notes describes a progression of precisely the sort I’m considering here, and mentions some advantages it has over the more familiar one.)We can try to reconstruct something more familiar by considering adjunctions. An adjunction in

RProis essentially a monotone map between posets. I don’t know quite what happens at the next level, but it ought to be something like a saturated anafunctor (up to Morita equivalence of the target).The intriguing thing about this approach is that it could conceivably be easier to describe the “weak” versions. After all, a (two-sided) fibration is a kind of weak module, and it’s easier to describe fibrations than pseudofunctors.

Do you know about allegories? All these ideas reappear at a more general level there. Given any arbitrary regular category C, you can form its category of relations, which is a poset-enriched category, Rel(C).

This acts very much like Rel. The adjoint pairs are precisely the maps of C; and comonads and symmetric monads play analogous rôles in Rel(C) to those you have outlined in Rel. Comonads will always split, giving you images of maps,because the category C you started with has images; and the symmetric monads split just when C is effective regular, i.e. whenever it has effective quotients of equivalence relations.

Have a look in Freyd & Scedrov “Categories, Allegories”, or Volume 1 of the Elephant.

Hi there. I did a little bit of category theory for my maths degree some 15 years ago and have retained an amateur interest in the subject – so apologies in advance if these remarks are too obvious or basic to be worth stating…

It struck me while thinking about this that any relation R between sets x and y can be thought of as a join-preserving function from Px to Py (where the power sets are thought of as complete join semi-lattices (CJSLs)), and conversely any join-preserving function between powersets encodes a unique relation between the underlying sets… so basically the 2-category

Relis equivalent to the category of powersets and join-preserving maps between them, right?And given that the powerset of x is just the free CJSL on x, it follows that

Relequivalent to the full subcategory of free CJSLs, ie the Kliesi category for the monad induced by the covariant powerset functor onSet.Moreover, in this Kliesi category the “formal” adjunction you sketch out above turns into an actual concrete adjunction of colimit-preserving functors (ie CJSL morphisms) between cocomplete preorders (ie CJSLs). And Freyd’s Adjoint Functor Theorem tells us that a join-preserving functor between two small CJSLs has a left adjoint iff it also happens to be meet-preserving.

So it seems to me that the questions “when does a join preserving map also preserve meets?” and “when does a relation have a left adjoint?” both turn out to have the same answer – when the relation is a function.

Two oddities arise though, which I can’t quite put my finger on – firstly, to prove that a join-preserving CJSL morphism between free CJSLs encodes a function you only need to assume the morphism preserves finite meets. So there’s some kind of “compactness” thing going on here, in that if finite meets are preserved, we get “all meets preserved” for free.

Also I don’t quite understand how, if the “formal” adjunction in

Relcan be thought of as an concrete adjunction, why the “every monad arises from an adjunction” thing fails inRel.