Fun with Rel

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:

Adjunction

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? :-))

This entry was posted in category theory, chatter. Bookmark the permalink.

6 Responses to Fun with Rel

  1. L. Alonso says:

    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 category Rel.
    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.

  2. B. Bartlett says:

    Mmm… fascinating!

  3. bosker says:

    I certainly didn’t discover that functions can be defined as adjunctions in Rel! 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?)

  4. bosker says:

    L. Alonso’s remark that Rel is more natural than Set reminds 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: if T is the terminal (one object, one morphism) category, then T-Cat is sets and functions, (T-Cat)-Cat is categories and functors, ((T-Cat)-Cat)-Cat is 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)-Mod etc. takes a little bit longer to get going: T-Mod has only two isomorphism classes of objects, so it’s equivalent to the category 2, but then (T-Mod)-Mod is RPro and 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 RPro is 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.

  5. 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.

  6. bat020 says:

    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 Rel is 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 Rel equivalent to the full subcategory of free CJSLs, ie the Kliesi category for the monad induced by the covariant powerset functor on Set.

    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 Rel can be thought of as an concrete adjunction, why the “every monad arises from an adjunction” thing fails in Rel.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s