Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 10, 2013

A Weighted Limits Proof of Monadicity

Posted by Emily Riehl

Since the 1970s, it has been known that the Eilenberg-Moore object (EM-object) associated with a monad in a 2-category 𝒦\mathcal{K} can be characterized as a weighted limit. An element of the limit of a Set-valued diagram can be thought of as a cone over that diagram. Similarly, in the case of a monad in Cat, an object of this weighted limit, more commonly called an algebra for the monad, is exactly a cone over the monad diagram whose shape is described by the weight.

Using the weighted limits formalism, EM-objects in a 2-category are defined representably. It follows that the monadicity theorem characterizing EM-objects and their monadic adjunction can be deduced representably from the monadicity theorem in Cat. Despite this fact, I want to give a direct proof of the 2-categorical monadicity theorem to illustrate that a suitable reinterpretation of Beck’s proof is “all in the weights.” To begin, we’ll use weighted limits to characterize the monadic adjunction. It follows immediately that any adjunction inducing the same monad has a comparison map to the monadic adjunction. Inspecting the weights, we observe that the monadic forgetful functor is conservative. We also show that any object in the EM-object is the colimit of a canonical diagram, itself described by a weighted limit, and the monadic forgetful functor preserves these colimits. If the domain of the comparison map admits certain colimits, this map has a left adjoint. If the forgetful functor is conservative, then the comparison adjunction is an adjoint equivalence.

The point of all this is that the 2-functors defining these weights can be interpreted as simplicial functors. The same discussion, with only minimal modifications, then gives a (formal!) proof of the monadicity theorem for homotopy coherent adjunctions of quasi-categories. I’ll be speaking about this in Sydney this week and Warsaw later this month. This is joint work with Dominic Verity.

The free adjunction

The free monad is a 2-category Mnd built from the algebraist’s Δ +\Delta_+, the free monoidal category containing a monoid. Here it will be convenient to observe that Mnd is a full subcategory of the Schanuel-Street free adjunction Adj. The 2-category Adj has two objects, + and -, with hom-categories

Adj(+,+)=Δ +\Delta_+, Adj(-,-)=Δ + op\Delta_+^{op}, Adj(-,+)=Δ \Delta_\infty Adj(+,-)=Δ \Delta_{-\infty}

The categories Δ \Delta_\infty and Δ \Delta_{-\infty} are opposites, defined to be the subcategories of Δ\Delta containing maps that preserve the top or bottom elements, respectively, in each ordinal. A 2-functor Adj 𝒦\to \mathcal{K} is an adjunction in the 2-category 𝒦\mathcal{K}. We’ll use the familiar notation f:BA:uf : B \rightleftarrows A : u, η:1 Buf\eta \colon 1_B \Rightarrow uf, ϵ:fu1 A\epsilon \colon fu \Rightarrow 1_A. The functor

Adj(+,+)=Δ +𝒦(B,B)\Delta_+\to\mathcal{K}(B,B)

defines the monad resolution associated to the adjunction. The diagram

Adj(-,+)=Δ 𝒦(A,B)\Delta_\infty\to\mathcal{K}(A,B)

is one of the bar resolutions associated to the adjunction. (If this is unfamiliar, see the displayed equations in section 4 here.)

We define Mnd to be the full sub 2-category on the object +. A 2-functor Mnd𝒦\to \mathcal{K} is a monad in the 2-category 𝒦\mathcal{K}.

Weights for the monadic adjunction

Write Adj+_+ and Adj_- for the two representable 2-functors for Adj and W +W_+ and W W_- for their restrictions to Mnd. Suppose T:T\colonMnd𝒦\to\mathcal{K} is a monad in 𝒦\mathcal{K}. By the Yoneda lemma, the weighted limit {W +,T}=B\{W_+,T\} = B, the object on which the monad acts. By contrast, the weighted limit {W ,T}\{W_-,T\} is — you guessed it — the EM-object!

You can check this directly in 𝒦=\mathcal{K}=Cat. The weighted limit is defined to be the equalizer

{W ,T}B Δ B Δ +×Δ .\{W_-,T\} \rightarrowtail B^{\Delta_\infty} \rightrightarrows B^{\Delta_+\times\Delta_\infty}.

One of the maps in the equalizer diagram is the monad resolution. The other is precomposition with ordinal sum Δ +×Δ Δ \Delta_+\times\Delta_\infty \to \Delta_\infty, which defines horizontal composition in Adj. It follows representably that this weighted limit defines the EM-object whenever it exists. (For more on this see Ross Street’s Limits indexed by category-valued 2-functors.)

The advantage of this description of the weight for the EM-object is that we immediately obtain the monadic adjunction: it is an adjunction between the weights W +W_+ and W W_-! This adjunction is simply the restriction of the Yoneda embedding

Adjop^{op}\to[Adj,Cat]\to[Mnd,Cat]

Composing with the weighted limit 2-functor

{-,-}:[Mnd,Cat]op×^op\times[Mnd,𝒦]𝒦\mathcal{K}]\to\mathcal{K}

we get an adjunction 𝒦\mathcal{K} between B[T]:={W ,T}B[T]\colon=\{W_-,T\} and B={W +,T}B=\{W_+,T\}, the monadic adjunction.

Conservativity of the monadic forgetful functor

The monadic forgetful functor u T:B[T]Bu^T\colon B[T] \to B is induced from the map W +W W_+\to W_- of weights in [Mnd,Cat], defined by pre-composing with [0]:+[0]\colon - \to +. Applied to the unique object of Mnd, the image is the identity-on-objects inclusion Δ +Δ \Delta_+\to\Delta_\infty. We can factor W +W W_+\to W_- as a relative cell complex built from two types of cells, which both have the form:

  • the product Mnd+×(CD)_+ \times (C \to D) of the representable with a functor CDC \to D.

Here CDC \to D is either the inclusion of the two endpoints into the walking arrow (used to freely attach the missing map in each hom-set from [n+1][n+1] to [n][n]), or it is the surjection from the parallel pair into the walking arrow (used to impose the appropriate composition relations for the attached cells). Importantly both functors are identity-on-objects.

The point is the map of weighted limits {W ,T}{W +,T}\{W_-,T\}\to\{W_+,T\} factors as a composite of pullbacks of products of maps

  • {Mnd+×D_+ \times D, TT}\to{Mnd+×C_+ \times C, TT}

and this, by the Yoneda lemma, is just the induced map between the cotensors DBCBD \pitchfork B \to C \pitchfork B. Now this map is (representably) conservative because a natural transformation is invertible if and only if its components are isomorphisms, and the functor CDC \to D is identity-on-objects. Hence, u T:B[T]Bu^T \colon B[T] \to B is conservative.

Colimit representation of algebras

Any algebra (b,β)(b,\beta) for a monad TT on a category BB is the colimit of a canonical u Tu^T-split coequalizer diagram. More exactly, there is a reflexive coequalizer diagram in B[T]B[T] built from free algebras (though not free algebra maps) whose colimit is (b,β)(b,\beta), and this diagram admits a splitting upon application of the forgetful functor u T:B[T]Bu^T\colon B[T] \to B.

These canonical colimits diagrams are also “all in the weights”! Before making this precise, allow me to change the diagram shape. The reflexive coequalizer diagram defines a final subcategory of Δ op\Delta^{op}; instead of reflexive coequalizers, we’ll speak of colimits of simplicial objects; colimit cones have shape Δ + op\Delta_+^{op}. Such a colimit cone is split if it extends along the natural identity-on-objects inclusion Δ + opΔ \Delta_+^op\to\Delta_\infty.

We’ll describe a weight WW for a higher dimensional analog of u Tu^T-split augmented simplicial objects. For formal reasons, augmented simplicial objects of this form are colimit diagrams, indeed are absolute colimits. There is a map of weights WW W \to W_-, hence a map of weighted limits, carrying the EM-object to the object of these canonical colimit cones.

It is easy to define the weight WW using the principle that the weighted limit functor is cocontinuous in the weights (and contravariant). Namely, WW is the pushout

W +×Δ + op W +×Δ W ×Δ + op W \begin{matrix} W_+ \times \Delta_+^{op} & \longrightarrow & W_+ \times \Delta_\infty \\ \downarrow & & \downarrow \\ W_-\times\Delta_+^{op} & \longrightarrow & W \end{matrix} The categories Δ \Delta_\infty and Δ + op\Delta_+^{op} act on the restricted representables using composition in Adj (ordinal sum). This action defines a cone under the pushout diagram with summit W W_- and hence the desired map WW W \to W_-.

The functor W ×Δ + opW_- \times \Delta_+^{op} defines the weight for augmented simplicial objects in B[T]B[T]. By cocontinuity, {W,T}\{W,T\} is the pullback {W,T} Δ + opB[T] u T Δ B Δ + opB \begin{matrix} \{W,T\} & \longrightarrow & \Delta_+^{op} \pitchfork B[T] \\ \downarrow & & \downarrow u^T\\ \Delta_\infty \pitchfork B & \longrightarrow & \Delta_+^{op} \pitchfork B \end{matrix} i.e., it is the object of augmented simplicial objects in B[T]B[T] whose images under u Tu^T admit a splitting. Thus {W,T}\{W,T\} is the object of u Tu^T-split augmented simplicial objects in B[T]B[T]. Using the (locally posetal) 2-category structure on Δ +\Delta_+, there is a 2-cell

W ×Δ op W W \begin{matrix} W_- \times \Delta^{op} & \longrightarrow & W \\ \downarrow & \overset{\Downarrow}{\nearr} & \\ W_- & \end{matrix} that defines an absolute left extension diagram. Furthermore, this universal property is equationally witnessed and so preserved by any 2-functor. In particular, taking weighted limits and restricting along {W ,T}{W,T}\{W_-,T\} \to \{W,T\} we get an absolute left lifting diagram

B[T]={W ,T} id const B[T]={W ,T} Δ opB[T]={W ×Δ op,T} \begin{matrix} & & B[T]=\{W_-,T\} \\ & {\mathrm{id}}\underset{\Uparrow}{\nearr} &\downarrow\mathrm{const} \\ B[T]=\{W_-,T\} & \longrightarrow & \Delta^{op}\pitchfork B[T]=\{W_-\times\Delta^{op},T\} \end{matrix} which we interpret as presenting the elements of the EM-object as colimits of diagrams of shape Δ op\Delta^{op}. Furthermore, the monadic forgetful functor preserves these colimits, essentially by functoriality of our definition of the maps between the weights.

I realize this is all a bit sketchy. The best I can do here is give a reference: this argument is very similar to the discussion in section 5.3 of this paper.

Comparison with the monadic adjunction

Of course, monadicity is about comparing an adjunction f:BA:uf : B \rightleftarrows A : u with monad uf=Tuf=T with the monadic adjunction f T:BB[T]:u Tf^T : B \rightleftarrows B[T] : u^T. Recall adjunctions are diagrams of shape Adj in 𝒦\mathcal{K}. A general result, immediate from the defining universal properties, says that the weighted limit of a restricted diagram is isomorphic to the limit of the original diagram weighted by the left Kan extension of the weight. In particular, writing H:H\colonAdj𝒦\to\mathcal{K} for our adjunction, its monad is resH:\mathrm{res}H\colonMnd𝒦\to\mathcal{K}. Hence, its EM-object is the weighted limit

{W W_-, res HH} = {lanW W_-, HH} = {lan res Adj_-, HH}

recalling that W W_- was defined to be the restriction along Mnd\toAdj of the representable Adj_-. The weight for the monadic adjunction is now the left Kan extension of the restriction of the Yoneda embedding y:y\colonAdjop^{op}\to[Adj,Cat]. The limit {y,H}\{y,H\} returns the adjunction HH. Hence, the canonical map of weights lan res yyy \to y induces the comparison from the given adjunction f:BA:uf : B \rightleftarrows A : u to the monadic adjunction f T:BB[T]:u Tf^T : B \rightleftarrows B[T] : u^T. We write R:AB[T]R\colon A \to B[T] for the non-identity component. Functoriality implies that u TR=uu^T R = u.

Monadicity

As above, the weight WW' for uu-split simplicial objects in AA is defined to be a pushout

Adj +×Δ op Adj +×Δ Adj ×Δ op W \begin{matrix} Adj_+ \times \Delta^{op} & \longrightarrow & Adj_+ \times \Delta_\infty \\ \downarrow & & \downarrow \\ Adj_-\times\Delta^{op} & \longrightarrow & W' \end{matrix} Here we’re using Δ op\Delta^{op} and not Δ + op\Delta_+^{op} because we’re defining the weight for the (simplicial object shaped) diagrams, not the (augmented simplicial object shaped) cones under these diagrams. We say that AA admits colimits of uu-split simplicial objects if there is an absolute left lifting diagram

A={Adj ,H} colim const {W,H} Δ opA={Adj ×Δ op,H} \begin{matrix} & & A=\{Adj_-,H\} \\ & {\mathrm{colim}}\underset{\Uparrow}{\nearr} &\downarrow\mathrm{const} \\ \{W',H\} & \longrightarrow & \Delta^{op}\pitchfork A=\{Adj_-\times\Delta^{op},H\} \end{matrix}

The weight lan W W_- defines a cone under the pushout defining WW' in the expected way. Hence, there is a map

L:B[T]={lanW ,H}{W,H}AL\colon B[T]=\{\mathrm{lan} W_-, H\}\to\{W',H\}\to A

under the hypothesis that AA admits colimits of uu-split simplicial objects. It follows from the universal property of the absolute lifting that this is left adjoint to the comparison map R:AB[T]R:A \to B[T].

Let ι\iota and ν\nu denote the unit and counit of the comparison adjunction LRL \dashv R. If u:ABu\colon A \to B preserves colimits of uu-split simplicial objects, then, as in the classical proof, it follows that u Tιu^T\iota is an isomorphism; as u Tu^T is conservative, ι\iota must be an isomorphism. Now ι R\iota_R and hence RνR\nu is an isomorphism, so uν=u TRνu\nu = u^TR\nu is also an isomorphism. Finally, if uu is conservative we conclude that ν\nu is an isomorphism, in which case LRL\dashv R is an adjoint equivalence, completing the proof.

Posted at July 10, 2013 12:02 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2633

2 Comments & 0 Trackbacks

Re: A weighted limits proof of monadicity

In Richard’s talk at the pre-CT workshop, he mentioned that by right Kan extending along the inclusion of Mnd into Adj, you can obtain the entire monadic adjunction as a diagram. I liked that idea because working with derivators has taught me to sometimes prefer Kan extending along fully faithful functors over constructing (weighted) (co)limits. Can you reformulate your other weighted limits as fully faithful Kan extensions? If so, it might be the easiest way to do something analogous in a “2-derivator” (whatever that is).

Posted by: Mike Shulman on July 11, 2013 7:24 AM | Permalink | Reply to this

Re: A weighted limits proof of monadicity

That’s a good question.

One thing I might have mentioned is you can use that fact — that the monadic adjunction is the right Kan extension of the monad along the inclusion Mnd\hookrightarrowAdj — to derive our weight W W_-. Assuming, as we do, that the appropriate limits exist, there is a formula for the (pointwise) right Kan extension as a weighted limit: the right Kan extension of T:𝒞𝒦T \colon \mathcal{C}\to\mathcal{K} along K:𝒞𝒟K\colon \mathcal{C}\to\mathcal{D} is defined by

RanKT(d):={𝒟(d,K),T}_K T(d) \colon= \{ \mathcal{D}(d,K),T\}.

Specializing to TT:Mnd𝒦\to\mathcal{K}, this is:

Ran T():={Adj(,+),T}={W ,T}T(-) \colon= \{ Adj(-,+), T\} = \{W_-,T\}.

But I can’t see right away how to get any of our other weighted limits as extensions of fully faithful inclusions, even something simple like cotensors.

Posted by: Emily Riehl on July 13, 2013 2:53 AM | Permalink | Reply to this

Post a New Comment