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.

January 27, 2014

Formal Theory of Monads (Following Street)

Posted by Emily Riehl

Guest post by Eduard Balzin

The Kan extension seminar continues, and with it we now come to the paper by Ross Street. Published in 1972, this paper is one of the first instances where the notion of a monad was made relative to an arbitrary 2-category. A lot of aspects, such as algebras over a monad, Eilenberg-Moore and Kleisli categories, the relation with adjunctions, were generalised accordingly. Other topics involve representability, duality, and the example of Cat\mathbf{Cat}. I will therefore try to talk about this paper in detail, and add something of my own.

Myself, in the course of my (higher)-categorical education, I have not learned in full about monads. I do not mean definitions or main theorems, but rather the answer to the question why monads. While preparing for the seminar, I’ve managed to give a series of answers to this (my own) question, and I hope that the discussion will take me (and everyone else) even further.

Let me sincerely thank Emily Riehl for organising the seminar. I truly hope it will be a new castle on the landscape of categorical life. I am also quite grateful for the participants of the seminar, who have greatly contributed during the online discussion and in their readers discussion. It all makes me happy.

I. What follows below is my summary and exposition of Street’s paper. At times, I add words of mine. The notation is not exactly of Street, but follows him closely for reading convenience. In addition, I rearranged some of the paragraphs in my exposition.

At the time this paper has written, monads had been around for quite a while and had achieved some recognition due to their usefulness in homological algebra and homotopy theory. Indeed, this is not the first paper where a monad internal to an arbitrary (weak) 2-category appears. Apparently the first mention of such general monads was made by Jean Bénabou in 1967. Formal Theory of Monads also restricts its attention to 2-categories instead of bicategories, strict 2-adjunctions instead of coherent ones. This brings more transparency to the theory but lessens the ability to apply the results of this paper directly.

II. A monad in a 2-category KK is a monoid object SS inside K(X,X)K(X,X) for some XKX \in K. Thus we have ‘multiplication’ 2-cells μ:SSS\mu: S S \to S and ‘unit’ η:1 XS\eta: 1_X \to S such that if we draw associativity and unit diagrams, we witness commutativity of those. A monad morphism (U,ϕ):(X,S)(Y,T)(U,\phi):(X,S) \to (Y,T) consists of a 1-cell U:XYU: X \to Y together with a 2-cell ϕ:TUUS\phi: T U \to U S. It should be required that ϕ\phi preserves units and associativity. A monad functor transformation (U,ϕ)(V,ψ)(U, \phi) \to (V, \psi) is a 2-cell UVU \to V suitably commuting with 2-cells. For each KK, this defines a 2-category Mnd(K)\mathbf{Mnd}(K), the construction is actually functorial in KK.

Maybe some readers are not willing to take this definition for granted. Then I remind them of the following situation in Cat\mathbf{Cat}. For a monad S:CCS: C \to C, a CC-algebra is an object xCx \in C equipped with a map SxxS x \to x, commuting suitably with μ\mu and η\eta. The map of monads (U,ϕ):(C,S)(D,T)(U,\phi):(C,S) \to (D,T) will send an SS-algebra xx to a TT-algebra.

A 2-category KK admits construction of algebras if the inclusion 2-functor Inc:KMnd(K)Inc:K \to \mathbf{Mnd}(K), sending XX to (X,1 X)(X,1_X), has a right adjoint (in the strict 2-categorical sense) Alg:(X,S)X SAlg:(X,S) \mapsto X^S. (IncInc always has a left adjoint Und:(X,S)XUnd:(X,S) \mapsto X.) The counit of 2-adjunction gives rise to a monad morphism (U S,χ):(X S,1)(X,S)(U^S, \chi) : (X^S,1) \to (X,S) through which each morphism of monads (Y,1)(X,S)(Y,1) \to (X,S) factors. The adjunct of (S,μ):(X,1)(X,S)(S, \mu) \colon (X,1) \to (X,S) defines a map J S:XX SJ^S:X \to X^S that is left adjoint to U SU^S and such that S=U SJ SS = U^S J^S. This gives us a theorem which says that when AlgAlg exists, each monad is generated by an adjunction.

Also, for each adjunction J:XA:UJ:X \leftrightharpoons A:U, there is a comparison 1-morphism AX UJA \to X^{UJ}. AA is monadic when this is an equivalence (Street asks for an isomorphism, though).

III. The paper also studies representability questions. In Cat\mathbf{Cat}, we know that C SC^S has the form of the category of algebras for a monad mentioned above. By direct consideration, it turns out, that there is an isomorphism (of categories — things are strict in this paper!) K(Y,X S)K(Y,X) K(Y,S) K(Y, X^S) \cong K(Y,X)^{K(Y,S)} where K(Y,S):K(Y,X)K(Y,X)K(Y,S):K(Y,X) \to K(Y,X) is the monad induced by Yoneda embedding. With this, we have two things to mention:

(a) X SX^S represents a functor K opCatK^{op} \to Cat. It turns out that X SX^S can be obtained as a weighted limit. This is observed but not proved in the paper, but was actually done afterwards.

(b) Many things about monads in KK can be deduced by passing to Cat\mathbf{Cat}-presheaves. For instance, N:AX SN:A \to X^S is an equivalence iff for each YKY \in K the functor K(Y,N):K(Y,A)K(Y,X S)K(Y,X) K(Y,S) K(Y,N):K(Y,A) \to K(Y, X^S) \cong K(Y,X)^{K(Y,S)} is an equivalence. So AA is monadic iff K(Y,A)K(Y,A) is for each YY.

IV. For a given object XX of KK, we can form the comma category Mnd(K)/X\mathbf{Mnd}(K)/X (we use the underlying functor) of monads over XX. One can ask, given a monad (A,R)(A,R) and E:AXE: A \to X, if there is a pushforward monad E *RE_{\ast} R on XX which is universal (any monad morphism (A,R)(X,S)(A,R) \to (X,S) factors through the canonical one (A,R)(X,E *R)(A,R) \to (X,E_{\ast} R)). Those (A,R,E)(A,R,E) for which this pushforward exists are called tractable.

For instance, we can try taking E *RE_\ast R to be the right Kan extension of ER:AXE R: A \to X along E:AXE: A \to X, and this (if exists) will give us a desired universal pushforward. When RR is unity, this is precisely what is called codensity monad. Observe that when EE has a left adjoint JJ, we can always take E *1 A=EJE_{\ast} {1_A} = E J, and this will satisfy the desired universal property. Thus codensity monads are monads one would get if E:AXE:A \to X actually had a left adjoint.

Let us restrict our attention to the category Mnd(X)\mathbf{Mnd}(X) which is the same as the inverse image of the underlying functor Mnd(K)K\mathbf{Mnd}(K) \to K over XX. The construction of algebras can be actually seen as a ‘semantics’ functor Sem:Mnd(X)Mnd(K)/XSem: \mathbf{Mnd}(X) \to \mathbf{Mnd}(K)/X, (X,S)(X S,1,E S)(X,S) \mapsto (X^S,1,E^S), and it will land in the full subcategory Tract(X)\mathbf{Tract}(X) of tractable objects. For each tractable object, forming the universal monad gives us the ‘structure’ functor Str:Tract(X)Mnd(X)Str: \mathbf{Tract}(X) \to \mathbf{Mnd}(X), (A,R,E)(X,E *R)(A,R,E) \mapsto (X,E_{\ast} R). SemSem is right adjoint to StrStr, and the counit of this adjunction is moreover an isomorphism.

V. For a 2-category KK, there are its duals K opK^{op}, K coK^{co}, and K coopK^{coop}. There is a big section of the paper which studies questions involving interpretations of monads and the construction of algebras in these dual 2-categories.

In K opK^{op} we again get monads (and so if SS is generated by an adjunction in K opK^{op}, same is true in KK), but the functors between them are different. Precisely, if we consider Mnd(K op) op\mathbf{Mnd}(K^{op})^{op} (so that the direction of 1-morphisms is the same as in KK), we get that a 1-morphism (X,S)(Y,T)(X,S) \to (Y,T) here is a monad opfunctor in KK: a 1-cell U:XYU: X \to Y with a 2-cell ϕ:USST\phi: U S \to S T, opposite direction. The category of algebras in this case is denoted X SX_S, and comes with canonical J S:XX SJ_S: X \to X_S. That’s the generalisation of Kleisli category.

Opfunctors often appear if one considers adjunctions: for two monads (X,S) and (Y,T) and an adjunction J:YX:UJ:Y \rightleftharpoons X:U, supplying the right adjoint UU with a 2-cell to make it into a monad functor is the same as supplying JJ in a 2-cell to make it into a monad opfunctor.

Monads in K coK^{co} and K coopK^{coop} by contrast are comonads in KK. Of more interest for consideration (for reasons explained below) is the 2-category Mnd(K coop) coop\mathbf{Mnd}(K^{coop})^{coop}, whose objects are comonads and morphisms are comonad opfunctors (the 2-cells are going in the same direction as 2-cells for monad functors). Again, when we have the construction of algebras for K coopK^{coop}, there is a universal object X SX_S for each comonad SS, with the opfunctor XX SX \to X_S.

If there is an adjunction J:XA:UJ:X \rightleftharpoons A:U, then we get a monad on XX but a comonad on AA. When we do the X SX^S construction for a monad, the fact that S=E SJ SS=E^S J^S gives us a comonad J SE SJ^S E^S on X SX^S. This allows to define a 2-functor ALG:Mnd(K)Mnd(K coop) coopALG: \mathbf{Mnd}(K) \to \mathbf{Mnd}(K^{coop})^{coop}, which sends (X,S)(X,S) to (X S,J SE S)(X^S, J^S E^S) (provided that KK admits the construction of algebras). Dually, there is COALG:Mnd(K coop) coopMnd(K)COALG: \mathbf{Mnd}(K^{coop})^{coop} \to \mathbf{Mnd}(K) (if, again, K coopK^{coop} is nice enough). A big calculation reveals that this is an adjunction: COALG:Mnd(K coop) coopMnd(K):ALG COALG:\mathbf{Mnd}(K^{coop})^{coop} \rightleftharpoons \mathbf{Mnd}(K):ALG which can be thought of lifting one of the construction of algebras adjunctions CoAlg:Mnd(K coop) coopMnd(K):Inc CoAlg:\mathbf{Mnd}(K^{coop})^{coop} \rightleftharpoons \mathbf{Mnd}(K):Inc (here CoAlgCoAlg is just a fancy name for the ‘coop’ of AlgAlg on K coopK^{coop}). Street hypothesises if one can use this lifting idea together with ‘2-triangle’ theorems to actually prove that if K coopK^{coop} admits algebras, then so does KK. One could hope that a version of 2-lifting theorem would obtain the right adjoint ALGALG as above from knowing the right adjoint IncInc to CoAlgCoAlg, and then apply the (dual of the) underlying functor Mnd(K coop) coopK\mathbf{Mnd}(K^{coop})^{coop} \to K after ALGALG, as to show that KK admits algebras for monads. That would be something special, however.

The other result mentioned in this section is when KK has a duality involution () op:KK co(-)^{op}:K \to K^{co}. In that case, KK admits construction of algebras whenever K opK^{op} does, and Alg(X,S)Alg(X op,S op) opAlg(X,S) \cong Alg(X^{op},S^{op})^{op}.

VI. A distributive law consists of two monads (X,S)(X,S) and (X,T)(X,T) together with a 2-cell λ:STTS\lambda: ST \to TS so that λ\lambda makes TT into a monad functor (X,S)(X,S)(X,S) \to (X,S) with η T\eta_T and μ T\mu_T becoming monad morphism transformations (equivalently, SS becomes a monad opfunctor on (X,T)(X,T)). An example here is given by

Mon:SetSetMon: Set \to Set, the monoid monad, and

Ab:SetSetAb: Set \to Set, the abelian group monad

(the usual distribution of ++ and ×\times gives a map AbMonMonAbAb Mon \to Mon \Ab). By writing out what Mnd(Mnd(K))\mathbf{Mnd}(\mathbf{Mnd}(K)) means, one can witness that distributive laws in KK are the objects of Mnd(Mnd(K))\mathbf{Mnd}(\mathbf{Mnd}(K)). Moreover, using the λ\lambda’s coming with each distributive law, one can define a natural transformation MndMndMnd\mathbf{Mnd}\mathbf{Mnd} \to \mathbf{Mnd}, which together with Inc:IdMndInc: Id \to \mathbf{Mnd} makes Mnd\mathbf{Mnd} into a (3-)monad on 22-Cat\mathbf{Cat}.

In addition, one can also consider the ‘opfunctor’ monad Mnd op=() opMnd() op\mathbf{Mnd}^{op} = (-)^{op} \mathbf{Mnd} (-)^{op}. Taking compositions like Mnd opMnd op\mathbf{Mnd}^{op} \mathbf{Mnd}^{op}, MndMnd op\mathbf{Mnd} \mathbf{Mnd}^{op} or Mnd opMnd\mathbf{Mnd}^{op} \mathbf{Mnd} again gives distributive laws (as objects), but different kinds of morphisms between them. One can ask if the resulting monads Mnd\mathbf{Mnd} and Mnd op\mathbf{Mnd}^{op} are related by a distributive law; however one can actually check that the law is a canonical isomorphism:

Mnd opMndMndMnd op.\mathbf{Mnd}^{op} \mathbf{Mnd} \cong \mathbf{Mnd} \mathbf{Mnd}^{op}.

VII. Essentially, the sole example of this paper is Cat\mathbf{Cat}. Using the fact that, for a monad (C,S)Mnd op(Cat)(C,S) \in \mathbf{Mnd}^{op}(\mathbf{Cat}), the category of algebras C SC_S is in fact what is known as Kleisli category, which certainly exists (its objects are the same as of CC and morphisms are maps of the form xSyx \to S y), we conclude that Cat,Cat op,Cat co,\mathbf{Cat},\mathbf{Cat}^{op},\mathbf{Cat}^{co}, and Cat coop\mathbf{Cat}^{coop} all admit the construction of algebras. A really nice result which follows is the statement that for a monad S:CCS: C \to C, C SC× Pr(C)Pr(C S) C^S \cong C \times_{Pr(C)} Pr(C_S) where Pr()=Fun(() op,Set)Pr(-)=Fun((-)^{op},Set) and Pr(C S)Pr(C)Pr(C_S) \to Pr(C) is induced by the canonical functor J S:CC SJ_S: C \to C_S. So we see that algebras for SS is a full subcategory of presheaves on Kleisli category which are representable when restricted to CC.

Finally, for VV-Cat\mathbf{Cat}, it is stated that the formal theory is applicable to this 2-category once a couple of properties are satisfied. Unfortunately, not much more is said about the enriched categories case in detail.

VIII. And that was it, (some of) the formal theory of monads! I must say that the 2-categorical content of that paper is really interesting, and one could ask if there is a way to proceed in the same manner in a higher (,2)(\infty,2)-categorical setting. Another thing is that, if one wishes to discuss monads in full, it is (as I presume) quite desirable to look beyond the formal theory for as many examples as possible. This is why I conclude my exposé with some references I know to the subjects that look interesting. Everyone is welcome to make her or his own list!

There is a follow-up of “The formal theory of monads”, called “The formal theory of monads, II”, in which the idea of X SX^S being a weighted limit is taken seriously, to the extent that the authors consider, for a 2-category KK, its completion EM(K)EM(K) with respect to these limits. The 1-interior of EM(K)EM(K) turns out to be the same as the one of Mnd(K)\mathbf{Mnd}(K), and moreover one can use EM(K)EM(K) to work with monads in a very useful way using mostly the universal property of this completion. The authors also study wreaths — the objects of EM(EM(K))EM(EM(K)), and in addition the paper is quite filled with examples for the notions presented.

The result everyone knows today as the Monadicity Theorem has a lot of applications. One of them which I like is the result that, given an (elementary) topos TT, the ‘maps into the classifier’ functor AΩ AA \mapsto \Omega^A from T opTT^{op} \to T is monadic. Because of this, TT has all finite colimits. On the other hand, when I talk to some (derived) algebraic geometers, they tell me that from their experience the only place where monadicity theorem comes close to be used fully and faithfully is Tannaka duality, and even there it can be avoided as was done in some first expositions. This might be subjective; however my search of any details on the question revealed a paper named The Formal Theory of Tannaka Duality, the author of which claims that it is inspired by Ross Street’s writeup! One might want to have a look for the detail.

Monads are strongly connected with algebraic theories (the latter term can actually be used here in a general sense). What is less known, probably, is that one can use monads themselves to describe some ‘ring-like’ objects. What I mention here is the theory of generalised commutative rings (which are some special monads on SetSet) by Durov, which appeared in his thesis, and can include such things as the field of one element as an example. One can then do a lot of algebraic geometry with this monads, up to K-theory and intersection stuff.

Monads do appear in higher categories. When working with model categories, one can work with weak monadic projections to treat Bousfield localisation (e.g. see Section 11.2 of Simpson’s book on Segal categories). Another thing is that it is often the case that one runs into a question if the category of algebras for a monad (or even a comonad) admits a model structure. For monads, one can see this, and for comonads, this and probably the recent one(!) . Finally, our dear host of this seminar has co-authored a paper which treats homotopy coherent adjunctions and monadicity theorem in quasi-categories, in a way much simpler than originally done by Jacob Lurie in his DAG II (the approach of Lurie still has some interesting flavour, coming from the treatment of algebraic structures via fibrations).

Posted at January 27, 2014 6:53 PM UTC

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

40 Comments & 1 Trackback

Re: Formal Theory of Monads (Following Street)

Thanks a lot for this summary and your very interesting remarks at the end.

I have a question about the phrasing of Theorem 6. Using your notation, Theorem 6 begins as follows:

When KK admits the construction of algebras, the semantics functor Sem has a left adjoint, […]

But Sem is only defined on the assumption that KK admits the construction of algebras, since its definition employs Alg. So is this just a redundant qualification at the beginning of the theorem? Should the theorem be read as saying: When Sem is defined as such, it always has a left adjoint? Or is there a way (which I cannot see, based on this paper) to define an analogue of Sem without assuming the construction of algebras, in which case the first phrase of Theorem 6 would not be redundant?

Posted by: Dimitris on January 27, 2014 9:59 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

I personally wasn’t aware of (or had at least forgotten about) Theorem 14, the theorem referred to in section VII above, that characterizes the Eilenberg-Mac Lane category C SC^S for a monad SS on a category CC as the full subcategory of the category of presheaves on the Kleisli category C SC_S that restrict to representable functors along the left adjoint CC SC \to C_S.

I’m wondering if we can use this result to recover the characterization of the image of the comparison functor C SC SC_S \to C^S from the Kleisli adjunction to the Eilenberg-Mac Lane adjunction: namely that the image consists of free algebras and all (not necessarily free) maps.

Note that this comparison functor is the map to the pullback C SC^S induced by the Kleisli adjunction: the leg C SCC_S \to C is given by the right adjoint, the leg C SPr(C S)C_S \to \text{Pr}(C_S) is given by the Yoneda embedding, and commutativity (up to isomorphism) is one expression of the adjunction CC SC \rightleftarrows C_S. Recall that the right adjoint C SCC_S \to C applies SS to objects and does the naive thing on maps.

Now we can see from the pullback diagram that C SC SC_S \to C^S is full: the composite C SC SPr(C S)C_S \to C^S \to \text{Pr}(C_S) is full as is the second factor (as a pullback of a full functor), and hence the first factor is full as well. But I don’t see a clear way to deduce that the objects in its image are free algebras. We do, of course, get this from the fact that the comparison functor C SC SC_S \to C^S commutes with the left adjoints, and the fact that CC SC \to C_S is surjective on objects, but I’m looking for something more categorical.

Posted by: Emily Riehl on January 28, 2014 1:44 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

But I don’t see a clear way to deduce that the objects in its image are free algebras. We do, of course, get this from the fact that the comparison functor C SC SC_S \to C^S commutes with the left adjoints, and the fact that CC SC \to C_S is surjective on objects, but I’m looking for something more categorical.

If “more categorical” means something like “more formal” or “more high-level”, then I have to say that this argument is already way more high-level than anything I could have imagined!

Is the issue that we don’t have a very high-level way to conclude that the left adjoint CC SC \to C_S is surjective on objects?

Also, the definition of “free algebra” that I’m working with is “an algebra of the form SXSX with structure map given by μ X\mu_X.” Is that what you had in mind? Or is there an alternative definition that doesn’t rely on the explicit description of C SC^S?

Posted by: Tim Campion on January 28, 2014 3:58 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

For a given monad (A,S)(A,S) in a general 22-category KK you can talk about SS-algebras in KK by taking an arbitrary 11-cell a:XAa \colon X \rightarrow A and requiring of a 2-cell SaaSa \Rightarrow a to satisfy the usual conditions. So in this setting a free algebra could be reproduced as one of the form SSaSaSSa \Rightarrow Sa in the standard way. Lack and Street briefly mention this in the beginning of ”The Formal Theory of Monads II”.

However, regarding Emily’s comment, I’m not sure if she’s asking for an alternative description in a general 22-category, or an alternative categorical description in Cat. The latter seems to me non-obvious even given this nice theorem, since in Cat we define free algebras as those that lie in the image of the left adjoint F SF^S and the fact that the image of KK is the full subcategory of these free algebras depends on the fact that KF S=F SK F_S = F^S which requires going down to the explicit description to establish as far as I can tell.

Posted by: Dimitris on January 28, 2014 4:47 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Yes, that’s what I meant.

But perhaps what I’m fishing for is silly. I suppose we get surjectivity of C SC SC_S \to C^S onto the objects in the image of CC SC \to C^S applying ob:CatSetob : \mathbf{Cat} \to \mathbf{Set} to the commuting triangle with the right adjoints.

I guess what I was really wondering is whether this characterization of the image C SC SC_S \to C^S is equivalent to this theorem.

Posted by: Emily Riehl on January 28, 2014 5:18 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

The embedding of C SC^S as presheaves on C SC_S is closely related to the Lawvere theory description of categories of algebras for finitary monads. In this case, C SC^S is the category of presheaves taking coproducts to products defined on a natural subcategory of C SC_S, namely the category of finitely-generated free algebras.

In contrast, the condition that Street uses to pick out C SC^S from the presheaf category is not a limit-preservation condition, but rather a representability condition. Now, representability of a presheaf is equivalent to limit-preservation under suitable conditions, but this case is a little more complicated because the representability condition involves precomposition with a functor.

Does anyone have a more precise idea of the relationship here? One awkward fact is that, as I alluded to above, a Lawvere theory is not the whole Kleisli category, but just a certain full subcategory. I think this issue should be addressable by working with a monad with arities. But I don’t think this makes it much clearer precisely why the representability condition here reduces to product-preservation under certain circumstances.

Posted by: Tim Campion on January 28, 2014 8:31 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

But you can take (the opposite of) the whole Kleisli category as the Lawvere theory (if the base is SetSet); of course, one also has to change the definition of model so that it is a functor that preserves all small products.

Posted by: Zhen Lin on January 28, 2014 10:48 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Good point – that should simplify things.

So the weird fact is that given a monad SS on a very nice category CC (at least C=SetC = \mathbf{Set} works), the following conditions on C S opFSet C_S^{\mathrm{op}} \overset{F}{\to} \mathbf{Set} coincide:

  • FF preserves (small) products

  • C opJ opC S opFSetC^{\mathrm{op}} \overset{J^{\mathrm{op}}}{\to} C_S^{\mathrm{op}} \overset{F}{\to} \mathbf{Set} is representable

(where J:CC SJ: C \to C_S is the usual free functor).

The question is: why?

Posted by: Tim Campion on January 28, 2014 11:24 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Since the free functor preserves coproducts, it suffices to show that a functor Set opSetSet^{op} \to Set that sends (small) coproducts in SetSet to products in SetSet is representable. But this can be checked straightforwardly.

More generally, if \mathcal{E} is a Grothendieck topos and opSet\mathcal{E}^{op} \to Set is a limit-preserving functor, then it is representable (and has a left adjoint).

Posted by: Zhen Lin on January 29, 2014 12:03 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Okay, so J opJ^{\mathrm{op}}, being a right adjoint, preserves limits. If FF preserves products, then FJ opF \circ J^{\mathrm{op}} preserves products. Then the claim is that any product-preserving functor Set opSet\mathbf{Set}^{\mathrm{op}} \to \mathbf{Set} automatically preserves all limits / is representable. This is a very special fact about Set\mathbf{Set}! It’s sort of miraculous because FF itself need not preserve all limits – otherwise we’d suspect FF of being representable…

The converse is not so clear: if FJ opF \circ J^{op} is representable, then FF preserves products. I suppose this can probably be checked directly? It’s hard to imagine there being some nice formal property of JJ that would allow us to conclude this because the formal property would have to distinguish between preserving products and preserving, say, equalizers (which FF need not preserve).

Posted by: Tim Campion on January 29, 2014 12:33 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

J opJ^{op} preserves products and is (essentially) surjective on objects, so if FJ opF J^{op} preserves products, then so does FF.

The difference between products and equalisers is just that the shape of the latter diagram has non-trivial morphisms.

Posted by: Zhen Lin on January 29, 2014 8:40 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Isn’t this just expressing the fact that for a monad SS over SetSet, its Eilenberg-Moore category of algebras C SC^S is equivalent to the category of algebras (in the sense of (small) product-preserving functors into SetSet) of some (infinitary) Lawvere theory, namely the Lawvere theory given by C S opC_S^{\text{op}}? Which is what we want, because we want the monadic and the functorial approach to coincide, at least over SetSet. I think the correspondence between finitary theories and finitary monads on SetSet is dealt with in Appendix A of Adamek/Rosicky/Vitale’s ”Algebraic Theories”, and if I remember correctly they use the Kleisli category in this manner to establish the correspondence. As Tim’s remarks indicate it seems unlikely that this correspondence will continue to hold in this explicit manner (i.e. with the opposite of the Kleisli category as the desired Lawvere theory) seeing as the result that every small product preserving functor SetSet opSet \rightarrow Set^{\text{op}} is representable depends (I think) crucially on the “special” fact that every set SS can be expressed as a coproduct of the terminal object SS times.

Posted by: Dimitris on January 29, 2014 7:05 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Isn’t this just expressing the fact that for a monad SS over SetSet, its Eilenberg-Moore category of algebras C SC^S is equivalent to the category of algebras (in the sense of (small) product-preserving functors into SetSet) of some (infinitary) Lawvere theory, namely the Lawvere theory given by C S opC_S^{\text{op}}? Which is what we want, because we want the monadic and the functorial approach to coincide, at least over SetSet. I think the correspondence between finitary theories and finitary monads on SetSet is dealt with in Appendix A of Adamek/Rosicky/Vitale’s ”Algebraic Theories”, and if I remember correctly they use the Kleisli category in this manner to establish the correspondence. As Tim’s remarks indicate it seems unlikely that this correspondence will continue to hold in this explicit manner (i.e. with the opposite of the Kleisli category as the desired Lawvere theory) seeing as the result that every small product preserving functor SetSet opSet \rightarrow Set^{\text{op}} is representable depends (I think) crucially on the “special” fact that every set SS can be expressed as a coproduct of the terminal object SS times.

Posted by: Dimitris on January 29, 2014 7:06 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Dimitris – I agree, that’s basically what it’s expressing. One way of looking at it is that we have two different ways of picking out “the category of algebras AlgT\mathrm{Alg} T of a Lawvere theory TT” as a full subcategory of [T,Set][T, \mathbf{Set}]: either by a continuity condition or by a representability condition.

I didn’t realize that the authors of Algebraic Theories made use of the representability criterion! They must have some argument similar to Zhen’s. Is this argument actually “standard”? I wonder how far back it goes– all the way to Lawvere?

Posted by: Tim Campion on January 30, 2014 6:32 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

I just learned something very neat related to this argument: Set op\mathbf{Set^{\mathrm{op}}} is not the only category (with products) such that all product-preserving functors out preserve limits. There is an old paper by Trnkova, When the product-preserving functors preserve limits, which gives several interesting examples. Some highlights:

  • The category Set 1\mathbf{Set}_{\geq 1} of nonempty sets.
  • The category Set *\mathbf{Set}_* of pointed sets.
  • The category Set inj\mathbf{Set}_{\mathrm{inj}} of sets and injections.
  • Best of all, the category Vect\mathbf{Vect} of vector spaces over a fixed field. I wonder if Vect op\mathbf{Vect}^{\mathrm{op}} works, too?

According to Trnkova, a necessary condition is that split monomorphisms be stable under pullback, and there is also a sufficient condition involving only (binary) intersections of split monos.

Posted by: Tim Campion on February 12, 2014 4:21 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Yes, this is a very nice characterization and somewhat surprising that this property of (preserves products \Rightarrow continuous) holds more generally. However I think that in the case of Vect we won’t in general get what we originally wanted, which was for the given functor to be representable, since Vect doesn’t have a small cogenerating set and so we cannot apply SAFT.

Posted by: Dimitris on February 13, 2014 3:11 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

That’s an interesting point about Vect\mathbf{Vect}.

It’s occurred to me that of course every product-preserving functor Vect opSet\mathbf{Vect}^{\mathrm{op}} \to \mathbf{Set} is representable, though, because every vector space is free: the Lawvere theory for vector spaces is Vect op\mathbf{Vect}^{\mathrm{op}}, and a product-preserving Set\mathbf{Set}-valued functor is a vector space, which is free; so the functor is representable.

Is there a name for this: an algebraic theory where every algebra is free? Are there other classic examples besides Vect\mathbf{Vect} (and Set\mathbf{Set}, I suppose)?

Posted by: Tim Campion on February 16, 2014 5:42 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Funnily enough, Set *\mathbf{Set}_* is another example, but Set 1\mathbf{Set}_{\ge 1} is not (because it has no initial object) and Set inj\mathbf{Set}_{inj} is not (because it has no terminal object).

I’m tempted to say that algebraic theory in which all models are free is “absolutely free” – in commutative algebra, there is the notion of an “absolutely flat ring”, which is a ring such that every module is flat. Here is an easy observation: an algebraic theory is absolutely free if and only if every parallel pair in the Kleisli category has a coequaliser that is preserved by the canonical embedding into the Eilenberg–Moore category. This suggests a connection with elimination of imaginaries.

Posted by: Zhen Lin on February 16, 2014 9:14 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

I did a little bit of googling on “absolutely free”, and unfortunately it looks like universal algebraists already use it in the following way: “The absolutely free Ω\Omega-algebra on the set XX is the free algebra of signature Ω\Omega subject to no relations.”

The weird thing about Set *\mathbf{Set}_{\ast} regarded as a Lawvere theory, is that it doesn’t have an object of which every other object is a power. So the algebras have infinitely many sorts – one for each prime, I suppose. On the other hand, Set * op\mathbf{Set}_{\ast}^{\mathrm{op}} does have every object a power of 2 (I think), and it seems very plausible that product-preserving functors Set * opSet\mathbf{Set}_{\ast}^{\mathrm{op}} \to \mathbf{Set} are all representable, i.e. that Set *\mathbf{Set}_{\ast}, regarded has a variety, has every algebra free. Even though Trnkova doesn’t discuss Set * op\mathbf{Set}_{\ast}^{\mathrm{op}}.

Regarding elimination of imaginaries – that’s something in model theory, right?

Posted by: Tim Campion on February 17, 2014 3:58 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Set *\mathbf{Set}_* was supposed to be an example of an algebraic theory in which all models are free. So Set * op\mathbf{Set}_*^{op} is a category for which product-preserving functors are representable. The reason for this is simple: given a set XX and an element xXx \in X, we have X={x}⨿(X{x})X = \{ x \} \amalg (X \setminus \{ x \}). Uniform elimination of imaginaries, very roughly speaking, says that the appropriate syntactic category has coequalisers for equivalence relations.
Posted by: Zhen Lin on February 17, 2014 8:12 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

one can use monads themselves to describe some ‘ring-like’ objects.

I heard about Durov’s thesis some times ago; such a pity that arithmetic geometry is absolutely out of my understanding! Can anybody make more precise this analogy?

I’d like to pose a naive question: the two “chapters” of the formal theory of monads can be considered rightly as the most possible abstract description of the subject. But what about a formal theory of operads? The only result I know in this direction is Kelly’s paper

G. M. Kelly, On the operads of J.P. May, Reprints in Theory and Applications of Categories, No. 13, 2005, pp. 1–13.

which is for sure a neat, elegant presentation of May’s classical idea in an extremely context-free way. Nevertheless it seems to divert from a “formal theory” in Street sense. Is such a development possible? If not, why? It would be wonderful to be capable to enucleate a notion of operad in a 2-category such that its induced monad is precisely a formal Street monad in said 2-category.

Kelly’s approach seems to rely on fairly intrinsic features of the ambient, like the fact that Cat\mathbf{Cat} harbors a “canonical” permutation groupoid \mathbb{N} we can exploit to endow the category Fun(N,𝒱)Fun(\mathbf{N},\mathcal{V}) with two interacting monoidal structures (the Day convolution \boxtimes, and a fairly more complicated, highly non-symmetric tensor (F,G) nF nGn(F,G)\mapsto \int^n F^{\boxtimes n}\otimes G n). I must admit my ignorance about this: for the moment I’m only sure that the analogy must be pushed further than an obvious re-interpretation.

Posted by: Fosco Loregian on January 28, 2014 1:29 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

The last section of Kelly’s paper considers changing the permutation groupoid to, what he calls, other domain categories. The N\mathbf{N} that he considers in that section gives plain (or non-Σ\Sigma) operads. He also considers replacing the domain category by S\mathbf{S}, which I think may be FinSetFinSet, allowing morphisms mnm \rightarrow n and not just automorphisms of each nn.

Nick Gurski and I recently considered the case wherein you replace the domain category with a category 𝔾\mathbb{G} having natural numbers as the objects (like in P\mathbf{P} or N\mathbf{N}) but where 𝔾(n)\mathbb{G}(n) is a group. (Link.) (If the G(n)G(n) fit into the structure of an operad then similar monoidal structures as those Kelly gives are required to show that these operads arise as monoids in [𝔾 op,Sets][\mathbb{G}^{op},\mathbf{Sets}].)

Posted by: Alex Corner on January 28, 2014 3:55 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

This is wonderful and elegant, but doesn’t catch what I had in mind (which is still a confuse idea). So nevermind, I’ll wait until I have read your paper to comment again.

For the moment, thank you!

Posted by: Fosco Loregian on January 28, 2014 5:15 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Yeah, I figured it wasn’t quite what you were thinking about. I tried for quite a while to put into words what I was thinking about having an operad in a 22-category but Mike’s comment about 22-toposes covered that nicely - making 𝒦\mathcal{K} sufficiently like Cat\mathbf{Cat}, that is.

Posted by: Alex Corner on January 28, 2014 10:42 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

I tried reading Durov’s thesis about a year and a half ago. I didn’t finish reading the whole thing, but by about halfway it seemed clear to me that Durov was not really considering monads per se but just finitary algebraic theories; at one point he even gives the correspondence between Lawvere theories and finitary monads on SetSet, and then uses this to define the notion of a sheaf of algebraic theories (or thereabouts).

Nonetheless, Durov’s idea is a very alluring one, motivated by phenomena in arithmetic geometry that suggest that we need a notion of (modules over) generalised rings, general enough to include objects like “the local ring at the infinite prime” etc. But there are other avenues to explore: for instance, one could try to treat suitable symmetric monoidal categories as generalisations of categories of quasicoherent sheaves on schemes, etc.

Posted by: Zhen Lin on January 28, 2014 4:09 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

One way to think about how finitary algebraic theories generalize rings is that a theory TT specifies a collection of “ways to form a linear combination of nn things” for each nn\in\mathbb{N}, together with a way to substitute linear combinations into each other.

If TT arises from an ordinary ring (or rig) RR, then a linear combination of nn things is determined by nn elements of RR, namely the coefficients of the linear combination, with substitution described using multiplication and addition in RR. An algebra for this theory is precisely an RR-module.

Note that all such linear combinations can be generated from (a) the unary linear combinations “multiplication by a scalar rRr\in R” and (b) the binary linear combination “addition”. However, a “generalized ring” could have, say, ternary “linear combination” operations that are not generated from unary and binary ones. One can define what it means for a theory to be “commutative” (generalizing commutativity of a rig), to have a zero element, to have an addition operation, etc.

Posted by: Mike Shulman on January 28, 2014 5:16 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

one could try to treat suitable symmetric monoidal categories as generalisations of categories of quasicoherent sheaves on schemes

There’s this thing called “2-algebraic geometry” where rings of functions are replaced by monoidal categories, and where it seems that regular functions are replaced by analytic functors. Is is the same thing you had in mind?

Joyal explained this stuff in Paris last summer; I’ll find out my notes of his talk.

Posted by: Fosco Loregian on January 28, 2014 5:23 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

No, not really. This is still within the realm of ordinary algebraic geometry; there are a few reconstruction theorems that tell us how to reconstruct a scheme from its category of quasicoherent sheaves (equipped with its symmetric monoidal closed structure), and there are some people working on the problem of understanding more general symmetric monoidal closed categories in a geometric fashion.

Posted by: Zhen Lin on January 28, 2014 6:18 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

You might be interested in the theory of generalized multicategories, although it’s not exactly what you’re describing. (Alex, I wonder whether your work with Nick fits into that framework?)

Another possible answer is that if KK has structure making it sufficiently like CatCat (e.g. it is a 2-topos), then you should be able to mimic Kelly’s definitions internally.

Posted by: Mike Shulman on January 28, 2014 5:11 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

if KK has structure making it sufficiently like Cat (e.g. it is a 2-topos), then you should be able to mimic Kelly’s definitions internally.

Indeed, I had in mind something similar. A blessing and a curse of categorical algebra is that you (almost) never invent anything from scratch!

At this point I can’t wait to hear about 2-toposes here in the Kan seminar…

Posted by: Fosco Loregian on January 28, 2014 5:38 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

This is not really on topic (whatever that means), but I wanted to respond to Mike. I have been thinking about this some recently, and the stuff Alex and I were doing definitely has a TT-multicategorical side to it. We were thinking about two things: operads whose sets were actually groups with a wreath-like condition on operadic composition (our current terminology for such a thing is an action operad, if you can do better let us know), and then the operads which were equivariant with respect to the groups appearing in the first sort. I can characterize action operads as clubs (= TT-operad for TT the free symmetric strict monoidal category 2-monad) satisfying some simple properties. I haven’t gotten around to thinking about lifting to Prof\mathbf{Prof} yet, but I suspect the hard calculations are already done in that paper with Alex. Instead I have been trying to come up with some nontrivial examples, about which I should probably write a post in case someone already knows something that I don’t (quite likely).

Posted by: Nick Gurski on January 29, 2014 10:29 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Emily reminded me that the meaning of the name “semantics-structure adjunction” is perhaps not so clear. Mike and I had some discussions about this once. Here is how I now think about it:

“A monad can be viewed as a sort of logical theory, and from this viewpoint the semantics functor sends it to its category of models; the study of the models of a logical theory is generally called its semantics. On the other hand, a monad can also be seen as a ‘type of structure’ with which objects of a category CC can be equipped. From this point of view, the structure functor sends a category AA over CC to the universal structure with which the objects of AA can be equipped.”

I don’t know if this coincides with Lawvere’s original motivation.

Since you also mentioned my paper on the formal theory of Tannaka duality towards the end I can’t resist giving a very brief outline of that. A key ingredient of the Tannakian formalism is that the goal is usually to study the interaction between (co)monads and coalgebras/comodules which satisfy some finiteness condition. It turns out that this finiteness condition can be expressed very naturally in the bicategory of modules (also known as distributors, profunctors, bimodules, relators,…). Namely, the “finite” objects correspond to maps, that is, 1-cells with right adjoints.

Instead of Eilenberg-Moore objects, I consider so called Tannaka-Krein objects, which satisfy a similar universal property but only for (co)actions on maps. Such objects do indeed exist in the bicategory of modules. Mimicking Street’s development of the formal theory of monads, TK-objects can be used to set up a “Tannakian” (bi)adjunction. The classical questions about reconstruction of coalgebras and recognition of categories of finite dimensional comodules are simply asking when the counit respective the unit of this adjunction is an equivalence.

Much of that paper is then devoted to the study of the interaction between the Tannakian adjunction and the monoidal structure of the bicategory of modules. The left biadjoint turns out to be strong monoidal, so the right adjoint inherits a weak monoidal structure. It follows that the whole biadjunction lifts to the bicategory of pseudomonoids. This provides a conceptual explanation for why monoidal structures of various flavours on the category of comodules induce bialgebra structures on the corresponding coalgebra.

I am quite certain that the basic theory of opmonoidal monads (respectively monoidal comonads) in a monoidal 2-category could similarly be deduced from a compatibility of the semantics-structure adjunction with the monoidal structure.

Posted by: Daniel Schaeppi on January 28, 2014 7:26 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Nice post Eduard, thanks!

One thing I wondered when reading the paper is how far you can push the idea that “monads are algebraic theories”. My background on this topic is fairly sketchy: I’m aware of the correspondence between monads on Set\mathbf{Set} and algebraic theories, but not much beyond that. It seems reasonable to think of monads on an arbitrary category (i.e. monads in Cat\mathbf{Cat}) as algebraic theories too, given the similarities between the Eilenberg-Moore category and categories of algebras for a theory. But does it still make sense to think of a monad in an arbitrary 2-category as an algebraic theory? Even when you can’t form Eilenberg-Moore objects? Perhaps I’m just being too pedantic and we should take this as a definition of algebraic theory, given the correspondence we have for Set\mathbf{Set}, but I’d be interested to know if there’s a deeper justification for it.

Posted by: Tom Avery on January 29, 2014 10:13 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

There are certainly monads which don’t look like algebraic theories on the face of it. For example, a monad in the 2-category Rel is exactly a preorder on a set, and has an EM-object iff it is an equivalence relation, in which case the EM-object is the set of equivalence classes of the relation.

Posted by: Alexander Campbell on January 29, 2014 11:54 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

On the other hand, RelRel is equivalent to the locally full sub-2-category of CatCat whose objects are powersets and whose morphisms are cocontinuous maps. Under this embedding, every monad has an EM-object, which is the preorder of downsets in the preorder that is the monad. Of course this is equivalent to another powerset exactly when the original preorder was an equivalence relation.

More generally, any 2-category KK can be embedded fully-and-faithfully in a 2-category KK' with EM-objects, by a functor which preserves and reflects EM-objects. Just take KK' to be the presheaf 2-category [K op,Cat][K^{op},Cat]. Put differently, if you like, you can consider a monad SS on an object XX in KK to be a collection of ordinary monads (i.e. “algebraic theories”) on the 2-categories K(Z,X)K(Z,X) which vary naturally in ZZ. (Eduard mentioned this process of “passing to CatCat-valued presheaves” in his post.) I admit that that may seem so tautological as to be unsatisfying, however. (-:

Posted by: Mike Shulman on January 29, 2014 4:25 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

Ah, that’s nice. So an arbitrary monad is at least “representably” an algebraic theory, whatever that means.

Posted by: Tom Avery on January 31, 2014 9:14 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

This is a great example. Do you know who first observed it?

Posted by: Emily Riehl on January 29, 2014 7:08 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

The identification of monads in Rel is made in Bénabou’s 1967 Bicategories paper (as early as it could have!). I don’t know a reference for the rest, but it’s not hard to guess once it’s recognised that the only adjunctions in Rel are ff of \dashv f^o for ff a function.

Posted by: Alexander Campbell on January 31, 2014 9:36 AM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

You mentioned, as motivation for the definition of monad morphism, that it’s what you need to induce a morphism between objects of algebras. That’s a good motivation, but I thought it would be worth mentioning a few others. One is that, as you said later on, monad morphisms are also the morphisms in EM(K)EM(K), although the 2-cells there differ. Another is that a monad in KK is equivalent to a lax 2-functor 1K1\to K or a strict (or pseudo) 2-functor BΔ +KB\Delta_+ \to K, and the monad morphisms and transformations are the lax natural transformations and modifications between such 2-functors. Yet another is that if KK is sufficiently cocomplete, then there is a 2-monad TT on KK whose algebras are monads in KK, and such that lax TT-morphisms and TT-transformations are respectively monad morphisms and monad transformations.

With the latter two motivations in mind, it becomes natural to say “lax monad morphism” and “colax monad morphism” rather than “monad functor” and “monad opfunctor” respectively. Personally I’ve never really liked the term “monad opfunctor” – it suggests that it’s the functor-ness that’s getting dualized (whatever that would mean) rather than the monad-ness.

Posted by: Mike Shulman on January 29, 2014 3:27 PM | Permalink | Reply to this

Re: Formal Theory of Monads (Following Street)

it becomes natural to say “lax monad morphism” and “colax monad morphism” rather than “monad functor” and “monad opfunctor”

Absolutely. When it comes to choosing a definition of morphism between monads, there’s a square that can commute up to equality, up to isomorphism, or just up to a connecting 2-cell in one direction or the other. It’s completely standard in such situations to use “(co)lax” for the last two possibilities.

If Ross had written his paper some years later, when this terminological system had become more established, I guess he would have called them “lax morphisms of monads” too.

Posted by: Tom Leinster on January 29, 2014 4:56 PM | Permalink | Reply to this
Read the post An Exegesis of Yoneda Structures
Weblog: The n-Category Café
Excerpt: Motivates the notion of Yoneda structure as an expression of basic notions of category theory in a natural 2-categorical language.
Tracked: March 24, 2014 5:35 AM

Post a New Comment