MONADS WITH ARITIES AND THEIR ASSOCIATED THEORIES

pefav - Steve Lack

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

30 pages

English

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

MONADS WITH ARITIES AND THEIR ASSOCIATED THEORIES CLEMENS BERGER, PAUL-ANDRE MELLIES AND MARK WEBER Abstract. After a review of the concept of “monad with arities” we show that the category of algebras for such a monad has a canonical dense generator. This is used to extend the correspondence between finitary monads on sets and Lawvere's algebraic theories to a general correspondence between monads and theories for a given category with arities. As application we determine arities for the free groupoid monad on involutive graphs and recover the symmetric simplicial nerve characterisation of groupoids. Introduction. In his seminal work [20] Lawvere constructed for every variety of algebras, de- fined by finitary operations and relations on sets, an algebraic theory whose n-ary operations are the elements of the free algebra on n elements. He showed that the variety of algebras is equivalent to the category of models of the associated algebraic theory. A little later, Eilenberg-Moore [12] defined algebras for monads (“triples”), and it became clear that Lawvere's construction is part of an equivalence between (the categories of) finitary monads on sets and algebraic theories respectively; for an excellent historical survey we refer the reader to Hyland-Power [15], cf. also the recent book by Adamek-Rosicky-Vitale [2]. In [8] the first named author established a formally similar equivalence between certain monads on globular sets (induced by Batanin's globular operads [6]) and certain globular theories, yet he did not pursue the analogy with algebraic theories any further.

eilenberg-moore category

correspondence between

et11 ?

algebraic theories

symmetric operads

pullback along

such choice

operads can

monad

Sujets

Hyland

Rosolini

Adamek

Monad (category theory)

Informations

Publié par	pefav
Nombre de lectures	11
Langue	English

Extrait

MONADS

WITH

ARITIES AND THEIR THEORIES

ASSOCIATED

´ ` CLEMENS BERGER, PAUL-ANDRE MELLIES AND MARK WEBER

Abstract.After a review of the concept of “monad with arities” we show that the category of algebras for such a monad has a canonical dense generator. This is used to extend the correspondence between ﬁnitary monads on sets and Lawvere’s algebraic theories to a general correspondence between monads and theories for a given category with arities. As application we determine arities for the free groupoid monad on involutive graphs and recover the symmetric simplicial nerve characterisation of groupoids.

Introduction.

In his seminal work [20] Lawvere constructed for every variety of algebras, de-ﬁned by ﬁnitary operations and relations on sets, an algebraic theory whosen-ary operations are the elements of the free algebra onnelements. He showed that the variety of algebras is equivalent to the category of models of the associated algebraic theory. A little later, Eilenberg-Moore [12] deﬁned algebras for monads (“triples”), and it became clear that Lawvere’s construction is part of an equivalence between (the categories of) ﬁnitary monads on sets and algebraic theories respectively; for an excellent historical survey we refer the reader to Hyland-Power [15], cf. also the recentbookbyAd´amek-Rosicky´-Vitale[2]. In [8] the ﬁrst named author established a formally similar equivalence between certain monads on globular sets (induced by Batanin’s globular operads [6]) and certain globular theories, yet he did not pursue the analogy with algebraic theories any further. The main purpose of this article is to develop a framework in which suchmonad/theory correspondences to our approach is the Centralnaturally arise. so-callednerve theoremwhich gives suﬃcient conditions under which algebras over a monad can be represented as models of an appropriate theory. For the general formulation we start with a dense generatorAof an arbitrary categoryE objects of. TheAare called thearitiesofE to the third. According named author [34] (on a suggestion of Steve Lack) a monadTonEwhich preserves the density presentation of the arities in a strong sense (cf. Deﬁnition 1.8) is called amonad with aritiesA. The associated theory ΘTis the full subcategory of the Eilenberg-Moore categoryETspanned by the freeT The-algebras on the arities. nerve theorem identiﬁes thenT-algebras with ΘT presheaves on Θ-models, i.e.T which typically take certain colimits in ΘT Deﬁnitionto limits in sets (cf. 3.1). The algebraic theories of Lawvere arise by takingEto be the category of sets, andA Section 3.5). Our(a skeleton of) the full subcategory of ﬁnite sets (cf.

Date: February 10, 2011. 1991Mathematics Subject Classiﬁcation.Primary 18C10, 18C15; Secondary 18D50, 18B40. Key words and phrases.Algebraic theory, density, arity, monad, operad, groupoid. 1

´ ` CLEMENS BERGER, PAUL-ANDRE MELLIES AND MARK WEBER

terminology is also motivated by another example; namely, ifEis the category of directed graphs,Athe full subcategory spanned by ﬁnite directed edge-paths, and Tfree category monad, the associated theory is the simplex category Δ, andthe the nerve theorem identiﬁes small categories with simplicial sets fulﬁlling certain exactness conditions, originally spelled out by Grothendieck [14] and Segal [28]. More generally, ifEis the category of globular sets,Athe full subcategory of globular pasting diagrams, andTthe freeω-category monad, the associated theory is Joyal’s cell category [16], and the nerve theorem identiﬁes smallω-categories with cellular sets fulﬁlling generalised Grothendieck-Segal conditions [8]. Inspired by these examples and by Leinster’s nerve theorem [22] for strongly cartesian monads on presheaf categories, the third named author [34] established a general nerve theorem for monads with arities on cocomplete categories. Recently the second named author [26] observed that there is no need of assuming cocom-pleteness and that the concepts of theory and model thereof carry over to this more general context. He sketched a 2-categorical proof of a general monad/theory cor-respondence on the basis of Street-Walter’s [32] axiomatics for Yoneda structures. The following text contains concise proofs of the nerve theorem and the resulting monad/theory correspondence. The ﬂexibility of our approach lies in the relative freedom for the choice of convenient arities: their density is the only requirement. Diﬀerent choices lead to diﬀerent classes of monads and to diﬀerent types of theories. Therank Wemonad is an example of one possible such choice. have been carefulof a to keep the formalism general enough so as to recover the known examples. We have also taken this opportunity to give a uniﬁed account of several key results of [8, 33, 34, 26], which hopefully is useful, even for readers who are familiar with our individual work. Special attention is paid to the free groupoid monad on involutive graphs for reasons explained below. The article is subdivided into four sections: Section 1 gives a new and short proof of the nerve theorem (cf. Theorem 1.10) based on the essential image-factorisation of strong monad morphisms. We show thatclassicalresultsofGabriel-Ulmer[13]andAda´mek-Rosick´y[1]concerning Eilenberg-Moore categories ofα-accessible monads inα-accessible categories can be considered as corollaries of our nerve theorem (cf. Theorem 1.13). Section 2 is devoted to alternative formulations of the concept of monad with arities. We show in Proposition 2.3 that monads with arities are precisely the monads (in the sense of Street [30]) of the 2-category of categories with arities, arity-respecting functors and natural transformations. In Proposition 2.5 arity-respecting functors are characterised via the connectedness of certain factorisation categories. We study in some detailstrongly cartesianmonads, i.e. cartesian monads which are local right adjoints, and recall from [33, 34] that they allow a calculus ofgeneric factorisations. This is used in Theorem 2.9 to show that every strongly cartesian monadTcomes equipped withcanonical aritiesAT shape of these canonical. The arities is essential for the behaviour of the associated class of monads. The monads induced byT-operadssense of Leinster [21] are monads with aritiesin the AT. Section 3 introduces the concept of theory appropriate to our level of generality, following [26]. The promised equivalence between monads and theories for a ﬁxed category with arities is established in Theorem 3.4. This yields as a special case the correspondence between ﬁnitary monads on sets and Lawvere’s algebraic theories. We introduce the general concept of ahomogeneous theory, and obtain in Theorem 3.10, for each strongly cartesian monadT(whose arities have no symmetries),

MONADS WITH ARITIES AND THEIR ASSOCIATED THEORIES

a correspondence betweenT-operads and ΘT-homogeneous theories. yields This in particular the correspondence [8, 4] between Batanin’s globularω-operads and Θω-homogeneous theories where Θωdenotes Joyal’s cell category. In Section 3.14 we show thatsymmetric operadscan be considered as Γ-homogeneous theories, where the category Γ of Segal [29] is directly linked with the algebraic theory of commutative monoids. This is related to recent work by Lurie [23] and Batanin [7]. Section 4 studies thefree groupoid monadon the category of involutive graphs. This example lies qualitatively in between the two classes of monads with arities which have been discussed so far, namely theα-accessible monads onα-accessible categories (with arities theα-presentable objects) and the strongly cartesian mon-ads on presheaf categories (endowed with their own canonical arities). Indeed, the category of involutive graphs is a presheaf category, but the free groupoid monad is not cartesian (though ﬁnitary). In Theorem 4.15 we show that the ﬁnite connected acyclic graphs (viewed as involutive graphs) endow the free groupoid monad with arities, and that this property may be used to recover Grothendieck’s symmetric simplicial characterisation of groupoids [14] as an instance of the nerve theorem. Let us brieﬂy mention some further developments and potential applications. – Our methods should be applicable in an enriched setting, in the spirit of what has been done for algebraic theories by Nishizawa-Power [27]. Ideally, the 2-category of categories with arities (cf. 2.1) could be replaced with an enriched version of it. – The monad/theory correspondence of Section 3 strongly suggests a combina-torial formulation ofMorita equivalencebetween monads with same arities. Such a conceptwouldinduceatheory/varietydualityastheoneestablishedbyAd´amek-Lawvere-Rosick´y[3]foridempotent-completealgebraictheories. – Our notion ofhomogeneous theorycaptures the notion ofoperadin two sig-niﬁcant cases: globular operads (cf. 3.12) and symmetric operads (cf. 3.14). The underlying conceptual mechanism needs still to be clariﬁed. – A future extension of our framework will contain a formalism ofcahgnofe-ri-aty functors. A most interesting example is provided by the symmetrisation functors of Batanin [7] which convert globularn 3.14).-operads into symmetric operads (cf. – The treatment in Section 4 of the free groupoid monad on involutive graphs is likely to extend in a natural way to the freen-groupoid monad on involutive n-globular sets. This is closely related to recent work by Ara [4, 5]. – The notion of monad with arities sheds light on the concept ofside eﬀectsin programming languages. It should provide the proper algebraic foundation for a presentation oflocal stores [15, 26].in an appropriate presheaf category, cf. Acknowledgements:the organisers of the Category Theory ConferenceWe thank CT2010 in Genova, especially Giuseppe Rosolini, for the stimulating atmosphere of this conference, which has been at the origin of this article. We are grateful to Jiri Adamek, Dimitri Ara, Michael Batanin, Brian Day, Martin Hyland, Steve ´ Lack, Georges Maltsiniotis and Eugenio Moggi for helpful remarks and instructive discussions. Notation and terminology: ForAll categories are supposed to be locally small. a monadTon a categoryE, theEilenberg-MooreandKleislicategories ofTare denotedETandETrespectively. An isomorphism-reﬂecting functor is calledcon-b servative. The category of set-valued presheaves onAis denotedA. For a functor b b j:A → Band right adjoints to the restriction functor, the left j∗:B → Aare denotedj!andj∗respectively, and calledleftandright Kan extensionalongj.