Multi-adjoints as conjoints

In this post I want to describe an observation I made recently about multi-adjoints: multi-adjoints are conjoints in a certain Kleisli double category.

So, what’s a multi-adjoint? If we think of left adjoints as free constructions, then we end up with a left multi-adjoint when we need a set of extra data in order to perform our free construction.

Def: A functor R : \mathcal{C} \to \mathcal{D} admits a left-multi adjoint L if for every D \in \mathcal{D}, there is a set I_D and a family L(D, i) \in \mathcal{C} for each i \in I(D) together with units \eta_i : D \to RL(D, i) which are universal in the sense that for any f : D \to RC, there is a unique i_f \in I(D) and transpose t_f : L(D, i) \to C so that f = Rt_f \circ \eta_i.

Evidently, a multi-adjoint is an actual adjoint if the set I(D) of indices is a singleton. Not so obviously, functor R : \mathcal{C} \to \mathcal{D} where \mathcal{C} has a terminal object and \mathcal{D} is locally small has a left multi-adjoint if and only if it is a parametric right adjoint! Mike Shulman observes this fact in this blog post.

Parametric right adjoints are just about everywhere (polynomial functors, anyone?), and so multi-adjoints are just about everywhere. But I won’t be using them to do anything in this post — I just want to observe that they can be defined as conjoints, which we can think of as a way to turn the above “universal arrows” definition of a left multi-adjoint into a “unit and counit” definition of a left multi-adjoint.

Kleisli double categories of 2-monads

Suppose that M : \mathsf{Cat} \to \mathsf{Cat} is a 2-monad — by which I mean a monad in the 2-category of 2-categories, 2-functors, and natural transformations. Nice and strict. Then we can define the following “Kleisli double category” of M:

Def: The Kleisli double category \mathsf{kl}(M) of M has as its vertical (or "strict) category the category of categories, and as its horizontal morphisms the Kleisli morphisms of the form X \to MY. A square is a “quintet” of the following form:

These compose vertically by pasting and horizontally using Kleisli composition.

Clearly, this works if M is a pseudo-monad as well — we’ll just get a pseudo-double category. I won’t dwell on this here.

Note that if M is the identity monad on \mathsf{Cat}, then \mathsf{kl}(M) is the usual double category of quintets. A conjoint in the double category of quintets is nothing more than an adjoint. My claim here is the following:

Thm: Let M be the 2-monad that freely completes a category under strict cartesian products. Then R : \mathcal{C} \to \mathcal{D} has a conjoint in \mathsf{kl}(M) if and only if it has a left multi-adjoint.

To understand this, it’s good to have a nice presentation of the free strict cartesian product monad M. This is given by the “families construction” \mathsf{Fam}(\mathcal{C}), which can be described simply as the oplax slice of the inclusion of sets into categories over \mathcal{C}. That is, the objects of \mathsf{Fam}(\mathcal{C}) are pairs (I, c : I \to \mathcal{C}) of a set I and an I-tuple of objects c_i in \mathcal{C}. A morphism (r, f) \in \mathsf{Fam}(\mathcal{C})((I, c), (J, c')) is a function r : J \to I together with a family of maps f : (j \in J) \to c(r(j)) \to c'(j). As a diagram:

Therefore, a Kleisli morphism L : \mathcal{D} \to \mathsf{Fam}(\mathcal{C}) assigns to every D \in \mathcal{D} a set I(D) and for every i \in I(D) an object L(D, i) \in \mathcal{C} — exactly the data we want the left multi-adjoint to a functor R : \mathcal{C} \to \mathcal{D} to have. It also has to do something on morphisms, but by the usual “universal arrows” argument, we can derive that from the universal property it has as a left multi-adjoint. In particular, for f : D \to D' and j \in I(D') consider the map \eta_j \circ f : D \to RL(D', j). By the universal property, there is a unique r(j) \in I(D) and t_j(f) : L(D, r(j)) \to L(D', j) with \eta_j \circ f = Rt(f) \circ \eta_j. We take L(f) = (r, t(f)), and this gives us a functor L : \mathcal{D} \to \mathsf{Fam}(\mathcal{C}).

Furthermore, the units give us a square of the following form in \mathsf{kl}(\mathsf{Fam}):

Starting to look like a conjoint! The other square we would need is a counit like this:

This square asks for the following data: for every C \in \mathcal{C}, an index e(C) \in I(R(C)) and a map \varepsilon : L(R(C), e(C)) \to C. To get this from a left multi-adjoint, we again appeal to the universal property. This time, we consider \mathsf{id} : RC \to RC, which guarantees precisely the data we needed.

The definition of a conjoint also requires two equations, which I’ve called the “kink” equations on account of how they look in the string diagram calculus for double categories. They are the analogue of the zig-zag equations. I’ll think I’ll leave it as an exercise here to complete the proof and show that any left-multiadjoint gives a conjoint in this way. If you know the way to pass from the “unit and counit” presentation of an adjunction to its “universal arrow” presentation, you’ll see that this works in the same way.

Other 2-Monads

What happens if we put in other 2-monads M? Generally, we get sensible results if we stick with the “free completion under some limits” theme. If we take M = \mathsf{Pro} to be the free completion under cofiltered limits, then we get as the conjoints in \mathsf{kl}(\mathsf{Pro}) the usual pro-adjoints. If we take M to be the free completion under all small limits, then \mathsf{kl}(M) is in fact equivalent to the double category of categories and profunctors — and here every functor has a conjoint. This is almost certainly why they are called “profunctors” in the first place, by the way, with the use of “pro-” as “limit” (and perhaps not yet restricted to “cofiltered limit”).


Nice post, David!
Have you seen this paper by Arkor, Di Liberti and Loregian?

1 Like

Wow! Thanks, I had not seen this. It’s a beautiful story.

I wonder if the distributive law can be expressed by one monad lifting to a double monad on the Kleisli double category of the other…

1 Like

This is amazing! Great insight.

Do you remember in Berkeley, you showed me some string diagrams, in ways they can make big ideas simple? One was how we can form the Kleisli category just by turning a monad sideways. Well, my thesis defines 3D string diagrams, and the Kleisli double category is formed in the same way.

It would be awesome to talk sometime! Let me know the best place to send a message.

1 Like