Monads and theories

John Bourke; Richard Garner

doi:10.1016/j.aim.2019.05.016

Monads and theories

Bourke, John;Garner, Richard

2018-05-11 00:00:00

JOHN BOURKE AND RICHARD GARNER Abstract. Given a locally presentable enriched category E together with a small dense full subcategory A of arities, we study the relationship between monads on E and identity-on-objects functors out of A, which we call A- pretheories. We show that the natural constructions relating these two kinds of structure form an adjoint pair. The ﬁxpoints of the adjunction are characterised on the one side as the A-nervous monads—those for which the conclusions of Weber’s nerve theorem hold—and on the other, as the A-theories which we introduce here. The resulting equivalence between A-nervous monads and A-theories is best possible in a precise sense, and extends almost all previously known monad–theory correspondences. It also establishes some completely new correspondences, including one which captures the globular theories deﬁning Grothendieck weak ω-groupoids. Besides establishing our general correspondence and illustrating its reach, we study good properties of A-nervous monads and A-theories that allow us to recognise and construct them with ease. We also compare them with the monads with arities and theories with arities introduced and studied by Berger, Melli` es and Weber. 1. Introduction Category theory provides two approaches to classical universal algebra. On the one hand, we have ﬁnitary monads on Set and on the other hand, we have Lawvere theories. Relating the two approaches we have Linton’s result [26], which shows that the category of ﬁnitary monads on Set is equivalent to the category of Lawvere theories. An essential feature of this equivalence is that it respects semantics, in the sense that the algebras for a ﬁnitary monad coincide up to equivalence over Set with the models of the associated theory, and vice versa. There have been a host of generalisations of the above story, each dealing with algebraic structure borne by objects more general than sets. In many of these [32, 31, 22, 23], one starts on one side with the monads on a given category that preserve a speciﬁed class of colimits. This class speciﬁes, albeit indirectly, the arities of operations that may arise in the algebraic structures encoded by such monads, and from this one may deﬁne, on the other side, corresponding notions of theory and model. These are subtler than in the classical setting, but Date: 3rd June 2020. 2000 Mathematics Subject Classiﬁcation. Primary:18C10, 18C20. Both authors gratefully acknowledge the support of Australian Research Council Discovery Project DP160101519; the second author also acknowledges Australian Research Council Future Fellowship FT160100393. arXiv:1805.04346v2 [math.CT] 2 Jun 2020 2 JOHN BOURKE AND RICHARD GARNER once the correct deﬁnitions have been found, the equivalence with the given class of monads, and the compatibility with semantics, follows much as before. The most general framework for a monad–theory correspondence to date involves the notions of monad with arities and theory with arities. In this setting, the permissible arities of operations are part of the basic data, given as a small, dense, full subcategory of the base category. The monads with arities were introduced ﬁrst, in [35], as a setting for an abstract nerve theorem. Particular cases of this theorem include the classical nerve theorem, identifying categories with simplicial sets satisfying the Segal condition of [33], and also Berger’s nerve theorem [8] for the globular higher categories of [7]. More saliently, when Weber’s nerve theorem is specialised to the settings appropriate to the monad–theory correspondences listed above, it becomes exactly the fact that the functor sending the algebras for a monad to the models of the associated theory is an equivalence. This observation led [29] and [9] to introduce theories with arities, and to prove, by using Weber’s nerve theorem, their equivalence with the monads with arities. The monad–theory correspondence obtained in this way is general enough to encompass all of the instances from [32, 31, 22, 23]. Our own work in this paper has two motivations: one abstract and one concrete. Our abstract motivation is a desire to explain the apparently ad hoc design choices involved in the monad–theory correspondences outlined above. For indeed, while these choices must be carefully balanced in order to obtain an equivalence, there is no reason to believe that diﬀerent careful choices might not yield more general or more expressive results. Our concrete motivation comes from the study of the Grothendieck weak ω-groupoids introduced by Maltsiniotis [27], which, by deﬁnition, are models of a globular theory in the sense of Berger [8]. Globular theories describe algebraic structure on globular sets with arities drawn from the dense subcategory of globular cardinals; see Example 8(v) below. However, globular theories are not necessarily theories with arities, and in particular, those capturing higher groupoidal structures are not. As such, they do not appear to one side of any of the monad–theory correspondences described above. The ﬁrst goal of this paper is to describe a new schema for monad–theory correspondences which addresses the gaps in our understanding noted above. In this schema, once we have ﬁxed the process by which a theory is associated to a monad, everything else is forced. This addresses our ﬁrst, abstract motivation. The correspondence obtained in this way is in fact best possible, in the sense that any other monad–theory correspondence for the same kind of algebraic structure must be a restriction of this particular one. In many cases, this best possible correspondence coincides with one in the literature, but in others, our correspondence goes beyond what already exists. In particular, an instance of our schema will identify the globular theories of [8] with a suitable class of monads on the category of globular sets. This addresses our second, concrete motivation. The further goal of this paper is to study the classes of monads and theories that arise from our correspondence-schema. We do so both at a general level, where we will see that both the monads and the theories are closed under essentially all the constructions one could hope for; and also at a practical level, where we MONADS AND THEORIES 3 will see how these general constructions allow us to give expressive and intuitive presentations for the structure captured by a monad or theory. To give a fuller account of our results, we must ﬁrst describe how a typical monad–theory correspondence arises. As in [35], the basic setting for such a correspondence can be encapsulated by a pair consisting of a category E and a small, full, dense subcategory K : A ,→ E . For example, the Lawvere theory– ﬁnitary monad correspondence for ﬁnitary algebraic structure on sets is associated to the choice of E = Set and A = F the full subcategory of ﬁnite cardinals. Given E and K : A ,→ E , the goal is to establish an equivalence between a suitable category of A-monads and a suitable category of A-theories. The A-monads will be a certain class of monads on E ; while the A-theories will be a certain class of identity-on-objects functors out of A. We are being deliberately vague about the conditions on each side, as they are among the seemingly ad hoc design choices we spoke of earlier. But regardless of this, the monad–theory correspondence itself always arises through application of the following two constructions. Construction A. For an A-monad T on E , the associated A-theory Φ(T) is the identity-on-objects functor J : A → A arising from the (identity-on-objects, T T fully faithful) factorisation J V T T (1.1) A −−→ A −−→ E T T of the composite F K : A → E → E . Here F is the free functor into the Kleisli T T T category E , so A is equally the full subcategory of E with objects those of A. T T T Construction B. For an A-theory J : A → T , the associated A-monad Ψ(T ) is obtained from the category of concrete T -models, which is by deﬁnition the pullback op // Mod (T ) [T , Set] op [J ,1] (1.2) U N =E (K−,1) op // E [A , Set] . T op Since U is a pullback of the strictly monadic [J , 1], it will be strictly monadic so long as it has a left adjoint. The assumption that E is locally presentable ensures that this is the case, and so we can take Ψ(T ) to be the monad whose algebras are the concrete T -models. There remains the problem of choosing the appropriate conditions on a monad or theory for it to be an A-monad or A-theory. Of course, these must be carefully balanced so as to obtain an equivalence, but this still seems to leave too many degrees of freedom; one might hope that everything could be determined from E and A alone. The main result of this paper shows that this is so: there are notions of A-monad and A-theory which require no further choices to be made, and which rather than being plucked from the air, may be derived in a principled manner. The key observation is that Constructions A and B make sense when given as input any monad on E , or any “A-pretheory”—by which we mean simply an 4 JOHN BOURKE AND RICHARD GARNER identity-on-objects functor out of A. When viewed in this greater generality, these constructions yield an adjunction oo (1.3) Mnd(E ) Preth (E ) // A between the category of monads on E and the category of A-pretheories. Like any adjunction, this restricts to an equivalence between the objects at which the counit is invertible, and the objects at which the unit is invertible. Thus, if we deﬁne the A-monads and A-theories to be the objects so arising, then we obtain a monad–theory equivalence. By construction, it will be the largest possible equivalence whose two directions are given by Constructions A and B. Having deﬁned the A-monads and A-theories abstractly, it behooves us to give tractable concrete characterisations. In fact, we give a number of these, allowing us to relate our correspondence to existing ones in the literature. We also investigate further aspects of the general theory, and provide a wide range of examples illustrating the practical utility of our results. Before getting started, we conclude this introduction with a more detailed outline of the paper’s contents. In Section 2, we begin by introducing our basic setting and notions. We then construct, in Theorem 6, the adjunction (1.3) between monads and pretheories. In Section 3, with this abstract result in place, we introduce a host of running examples of our basic setting. To convince the reader of the expressive power of our notions, we construct, via colimit presentations, speciﬁc pretheories for a variety of mathematical structures. In Section 4 we obtain our main result by characterising the ﬁxpoints of the monad–theory adjunction: the A-monads and A-theories described above. The A-monads are characterised as what we term the A-nervous monads, since they are precisely those monads for which Weber’s nerve theorem holds. The A- theories turn out to be precisely those A-pretheories for which each representable is a model; in the motivating case where E = Set and A = F, they are exactly the Lawvere theories. With these characterisations in place, we obtain our main Theorem 19, which describes the “best possible” equivalence between A-theories and A-nervous monads. Section 5 develops some of the general results associated to our correspondence- schema. We begin by showing that our monad–theory correspondence commutes, to within isomorphism, with the taking of semantics on each side. We also prove that the functors taking semantics are valued in monadic right adjoint functors between locally presentable categories. The ﬁnal important result of this section states that colimits of A-nervous monads and A-theories are algebraic, meaning that the semantics functors send them to limits. Section 6 is devoted to exploring what the A-nervous monads and A-theories amount to in our running examples. In order to understand theA-nervous monads, we prove the important result that they are equally the colimits, amongst all monads, of free monads on A-signatures. We also introduce the notion of a saturated class of arities as a setting in which, like in [32, 31, 22, 23], theA-nervous monads can be characterised in terms of a colimit-preservation property. With MONADS AND THEORIES 5 these results in place, we are able to exhibit many of these existing monad–theory correspondences as instances of our general framework. In Section 7, we examine the relationship between the monads and theories of our correspondence, and the monads with arities and theories with arities of [35, 29, 9]. In particular, we see that every monad with arities A is an A- nervous monad but that the converse implication need not be true: so A-nervous monads are strictly more general. Of course, the same is also true on the theory side. We also exhibit a further important point of diﬀerence: colimits of monads with arities, unlike those of nervous monads, need not be algebraic. This means that there is no good notion of presentation for monads or theories with arities. Finally, in Section 8, we give a number of proofs deferred from Section 6. 2. Monads and pretheories 2.1. The setting. In this section we construct the monad–pretheory adjunction oo (2.1) Mnd(E ) ⊥ Preth (E ) . // A The setting for this, and the rest of the paper, involves two basic pieces of data: (i) A locally presentable V -category E with respect to which we will describe the monad–pretheory adjunction; and (ii) A notion of arities given by a small, full, dense sub-V -category K : A ,→ E . We will discuss examples in Section 2.1 below, but for now let us clarify some of the terms appearing above. While in the introduction, we focused on the unenriched context, we now work in the context of category theory enriched over a symmetric monoidal closed category V which is local ly presentable as in [13]. In this context, a local ly presentable V -category [18] is one which is cocomplete as a V -category, and whose underlying ordinary category is locally presentable. We recall also some notions pertaining to density. Given a V -functor K : A → E op with small domain, the nerve functor N : E → [A ,V ] is deﬁned by N (X ) = K K E (K –, X ). We call a presheaf in the essential image of N a K -nerve, and we op write K -Ner(V ) for the full sub-V -category of [A ,V ] determined by these. We say that K is dense if N is fully faithful; whereupon N induces an K K equivalence of categories E ' K -Ner(V ). Finally, we call a small sub-V -category A of a V -category E dense if its inclusion functor K : A ,→ E is so. 2.2. Monads. We write Mnd(E ) for the (ordinary) category whose objects are V - monads onE , and whose maps S → T areV -transformations α : S ⇒ T compatible with unit and multiplication. For each T ∈ Mnd(E ) we have the V -category T T of algebras U : E → E over E , but also the Kleisli V -category F : E → E T T under E , arising from an (identity-on-objects, fully faithful) factorisation F F (2.2) // E E T 6 JOHN BOURKE AND RICHARD GARNER T T of the free V -functor F : E → E ; concretely, we may take E to have objects those of E , hom-objects E (A, B) = E (A, TB), and composition and identities derived using the monad structure of T. Each monad morphism α : S → T induces, functorially in α, V -functors α and α ﬁtting into diagrams T S // E E E F F S T (2.3) }} !! T S "" }} U U // E E E ; S T here α sends an algebra a : TA → A to a◦ α : SA → A and is the identity on homs, while α is the identity on objects and has action on homs given by the postcomposition maps α ◦ (–) : E (A, B) → E (A, B). In fact, every V -functor S T T S ∗ E → E over E or V -functor E → E under E is of the form α or α for a S T ! unique map of monads α—see, for example, [30]—and in this way, we obtain ful ly faithful functors Alg Kl op (2.4) Mnd(E ) −−→ V -CAT/E and Mnd(E ) −−→ E/V -CAT . 2.3. Pretheories. An A-pretheory is an identity-on-objects V -functor J : A → T with domain A. We write Preth (E ) for the ordinary category whose objects are A-pretheories and whose morphisms are V -functors commuting with the maps from A. While the A-pretheory is only fully speciﬁed by both pieces of data T and J , we will often, by abuse of notation, leave J implicit and refer to such a pretheory simply as T . Just as any V -monad has a V -category of algebras, so any A-pretheory has a V -category of models. Generalising (1.2), we deﬁne the V -category of concrete T -models Mod (T ) by a pullback of V -categories as below left; so a concrete T - op model is an object X ∈ E together with a chosen extension of E (K –, X ) : A → V op op op along J : A → T . The reason for the qualiﬁer “concrete” will be made clear in Section 5.2 below, where we will identify a more general notion of model. op [H ,1] P P T S op op op // // // Mod (T ) [T ,V ] Mod (S ) [S ,V ] [T ,V ] c c op op (2.5) U [J ,1] U [J ,1] T S N N K K op op // // E [A ,V ] E [A ,V ] Remark 1. Avery considers a notion very similar to our A-pretheories under the name prototheories [4, Deﬁnition 4.1.1]. The diﬀerences are that Avery’s prototheories A → T are not enriched, and the hom-sets of T need not be small. He also deﬁnes a category of (concrete) models for a prototheory, relative to a op given functor E → [A ,C] called an aritation. When this functor is the nerve op N : E → [A , Set], his category of models agrees with our Mod (T ). K c Any A-pretheory map H : T → S gives a functor H : Mod (S ) → Mod (T ) c c over E by applying the universal property of the pullback left above to the commuting square on the right. In this way, we obtain a semantics functor: Mod op (2.6) Preth (E ) −−−−→ V -CAT/E . A MONADS AND THEORIES 7 However, unlike (2.4), this is not always fully faithful. Indeed, in Example 10 below, we will see that non-isomorphic pretheories can have isomorphic categories of concrete models over E . 2.4. Monads to pretheories. We now deﬁne the functor Φ : Mnd(E ) → Preth (E ) in (2.1). As in Construction A of the introduction, this will take the V -monad T to the A-pretheory J : A → A arising as the ﬁrst part of an (identity-on-objects, T T fully faithful) factorisation of F K : A → E , as to the left in: T T J J T T // // A A A A T T (2.7) V K K T K T T F // // E E E E . Since the comparison W : E → E is fully faithful, we can also view J as T T T arising from an (identity-on-objects, fully faithful) factorisation as above right; the relationship between the two is that K = W ◦V . Both perspectives will be T T T used in what follows, with the functor K : A → E of particular importance. T T To deﬁne Φ on morphisms, we make use of the orthogonality of identity-on- objects V -functors to fully faithful ones; this asserts that any commuting square of V -functors as below, with F identity-on-objects and G fully faithful, admits a unique diagonal ﬁller J making both triangles commute. // A C >> F G // B D Explicitly, J is given on objects by Ja = Ha, and on homs by −1 K (G ) a,b Ha,Hb B(a, b) −−−→ D(Ka, Kb) = D(GHa, GHb) −−−−−−−−→ C(Ha, Hb) . In particular, given a map α : S → T of Mnd(E ), this orthogonality guarantees the existence of a diagonal ﬁller in the diagram below, whose upper triangle we take to be the map Φ(α) : Φ(S) → Φ(T) in Preth (E ): // A A 66 T J V S T // // A E E . S S T 2.5. Pretheories to monads. Thus far we have not exploited the local presentab- ility of E . It wil l be used in the next step, that of constructing the left adjoint to Φ : Mnd(E ) → Preth (E ). We ﬁrst state a general result which, independent of local presentability, gives a suﬃcient condition for an individual pretheory to have a reﬂection along Φ. Here, by a reﬂection of an object c ∈ C along a functor U : B → C, we mean a representation for the functor C(c, U –) : B → Set. 8 JOHN BOURKE AND RICHARD GARNER Theorem 2. A pretheory J : A → T admits a reﬂection along Φ whenever the forgetful functor U : Mod (T ) → E from the category of concrete models has a T c left adjoint F . In this case, the reﬂection ΨT is characterised by an isomorphism ΨT ∼ E Mod (T ) over E , or equal ly, by a pul lback square ΨT op // E [T ,V ] op ΨT [J ,1] (2.8) op // E [A ,V ] . To prove this result, we will need a preparatory lemma, relating to the notion of discrete isoﬁbration: this is a V -functor U : D → C such that, for each f : c Ud 0 0 0 in C, there is a unique f : c d in D with U (f ) = f . T T Example 3. For any V -monad T on C, the forgetful V -functor U : C → C is a discrete isoﬁbration. Indeed, if x : Ta → a is a T-algebra and f : b = a in C, −1 then y = f ◦ x◦ Tf : Tb → b is the unique algebra structure on b for which f : (b, y) → (a, x) belongs to C . In particular, for any identity-on-objects V - functor F : A → B between small V -categories, the functor [F, 1] : [B,V ] → [A,V ] has a left adjoint and strictly creates colimits, whence is strictly monadic. It is therefore a discrete isoﬁbration by the above argument. Lemma 4. Let U : A → B be a discrete isoﬁbration and α : F ⇒ G : X → B an invertible V -transformation. The displayed projections give isomorphisms between liftings of F through U , liftings of α through U , and liftings of G through U : GG A A ?? ?? α ¯ ¯ ¯ dom U cod F # G U ←−−− −−→ U (( F X B G // // X B X B . Proof. Given G : X → A as to the right, there is for each x ∈ X a unique lifting ∼ ∼ ¯ ¯ ¯ of the isomorphism α : Fx UGx to one α ¯ : Fx Gx. There is now a unique = = x x ¯ ¯ ¯ ∼ ¯ way of extending x 7→ Fx to aV -functor F : X → A so that α ¯ : F G; namely, by −1 ¯ ¯ ¯ ¯ taking the action on homs to be F = A(α ¯ , α ¯ )◦G : X (x, y) → A(Fx, Fy). x,y x y x,y In this way, we have found a unique lifting of α through U whose codomain is the given lifting of G through U . So the right-hand projection is invertible; the −1 argument for the left-hand one is the same on replacing α by α . We can now give: Proof of Theorem 2. U has a left adjoint by assumption, and—as a pullback of op op op the strictly monadic [J , 1] : [T ,V ] → [A ,V ]—strictly creates coequalisers for U -absolute pairs. It is therefore strictly monadic. Taking ΨT = U F to T T T ΨT ∼ be the induced monad, we thus have an isomorphism E = Mod (T ) over E . It remains to exhibit isomorphisms Mnd(E )(ΨT , S) Preth (E )(T , ΦS) nat- ural in S. We do so by chaining together the following sequence of natural MONADS AND THEORIES 9 bijections. Firstly, by full ﬁdelity in (2.4), monad maps α : ΨT → S correspond S ΨT naturally to functors α : E → E rendering commutative the left triangle in α α 1 2 S ΨT S op // // E E E [T ,V ] op (2.9) [J ,1] S ΨT U U op // E E [A ,V ] . ΨT Since E is deﬁned by the pullback (2.14), such functors α correspond naturally to functors α rendering commutative the square above right. Next, we observe that there is a natural isomorphism in the triangle below left U 3 S S op // // E E E [T ,V ] (2.10) ∼ op N N N S K S [J ,1] F K F K ~~ ~~ op op [A ,V ] [A ,V ] S S S with components the adjointness isomorphisms E (Ka, U b) = E (F Ka, b). Since op op J is identity-on-objects, [J , 1] is a discrete isoﬁbration by Example 3, whence by Lemma 4 there is a natural bijection between functors α as in (2.9) and ones α as in (2.10). We should now like to transpose this last triangle through the following natural isomorphisms (taking X = A,T ): S op op S (2.11) V -CAT(E , [X ,V ]) = V -CAT(X , [E ,V ]) . S S However, since E is large, the functor category [E ,V ] will not always exist as a V -category, and so (2.11) is ill-deﬁned. To resolve this, note that N S F K is, by its deﬁnition, pointwise representable; whence so too is α , since J is identity-on-objects. We may thus transpose the right triangle of (2.10) through the legitimate isomorphisms S op op S (2.12) V -CAT(E , [X ,V ]) = V -CAT(X , [E ,V ] ) pwr rep where on the left we have the category of pointwise representable V -functors, and on the right, the legitimate V -category of representable V -functors E → V . In this way, we establish a natural bijection between functors α and functors α 3 4 rendering commutative the left square in: op J J op op // // A T A T op S op α α α (α ) 4 J 6 5 (F K) 5 zz zz S op S S // // (E ) [E ,V ] A E . rep S Y K op Now orthogonality of the identity-on-objects J and the fully faithful Y draws the correspondence between functors α and functors α satisfying α ◦J = F K 4 5 5 as left above. Finally, since A ﬁts in to an (identity-on-objects, fully faithful) factorisation of F K , orthogonality also gives the correspondence, as right above, between functors α and functors α satisfying α ◦ J = J , as required. 5 6 6 S 10 JOHN BOURKE AND RICHARD GARNER We now show that the assumed local presentability of E ensures that every pretheory has a reﬂection along Φ : Mnd(E ) → Preth (E ), which consequently has a left adjoint. The key result about locally presentable categories enabling this is the following lemma. Lemma 5. Consider a pul lback square of V -categories // A B (2.13) U V // C D in which G and V are right adjoints between local ly presentable V -categories and V is strictly monadic. Then U and F are right adjoints between local ly presentable V -categories and U is strictly monadic. Proof. Since V is strictly monadic, it is a discrete isoﬁbration, and so its pullback against G is, by [14, Corollary 1], also a bipullback. By [10, Theorem 6.11] the 2-category of locally presentable V -categories and right adjoint functors is closed under bilimits in V -CAT, so that both U and F are right adjoints between locally presentable categories. Finally, since U is a pullback of the strictly monadic V , it strictly creates coequalisers for U -absolute pairs. Since it is already known to be a right adjoint, it is therefore also strictly monadic. With this in place, we can now prove: Theorem 6. Let E be local ly presentable. Then Φ : Mnd(E ) → Preth (E ) has a left adjoint Ψ : Preth (E ) → Mnd(E ), whose value at the pretheory J : A → T Ψ(T ) is characterised by an isomorphism E = Mod (T ) over E , or equal ly, by a pul lback square Ψ(T ) op // E [T ,V ] op Ψ(T ) (2.14) [J ,1] op // E [A ,V ] . Proof. Let J : A → T be a pretheory. The pullback square (2.5) deﬁning Mod (T ) is a pullback of a right adjoint functor between locally presentable categories along a strictly monadic one: so it follows from Lemma 5 that U : Mod (T ) → E is a right adjoint, whence the result follows from Theorem 2. Remark 7. In Avery’s study of prototheories, he establishes a structure–semantics op adjunction [4, Theorem 4.4.8] of the form Proto (E ) CAT/E , where here CAT is the category of large categories. By restricting to the locally small prototheories to the left and to the strictly monadic functors to the right of this adjunction, one can recover, via (2.4), the unenriched case of our adjunction (2.1). 3. Pretheories as presentations In the next section, we will describe how the monad–pretheory adjunction (2.1) restricts to an equivalence between suitable subcategories of A-theories and of MONADS AND THEORIES 11 A-nervous monads. However, the results we have so far are already practically useful. The notion of A-pretheory provides a tool for presenting certain kinds of algebraic structure, by exhibiting them as categories of concrete T -models for a suitable pretheory in a manner reminiscent of the theory of sketches [6]. Equivalently, via the functor Ψ, we can see A-pretheories as a way of presenting certain monads on E . 3.1. Examples of the basic setting. Before giving examples of algebraic structures presented by pretheories, we ﬁrst describe a range of examples of the basic setting of Section 2.1 above. Examples 8. We begin by considering the unenriched case where V = Set. (i) Taking E = Set and A = F the full subcategory of ﬁnite cardinals captures the classical case of ﬁnitary algebraic structure borne by sets; so examples like groups, rings, lattices, Lie algebras, and so on. (ii) Taking E a locally ﬁnitely presentable category and A = E a skeleton of the full subcategory of ﬁnitely presentable objects, we capture ﬁnitary algebraic structure borne by E -objects. Examples when E = Cat include ﬁnite product, ﬁnite colimit, and monoidal closed structure; for E = CRng, we have commutative k-algebra, diﬀerential ring and reduced ring structure. (iii) We can replace “ﬁnitary” above by “λ-ary” for any regular cardinal λ. For example, when λ = ℵ , this allows for the structure of poset with joins of ω-chains [28] when E = Set, and for countable product structure when op E = Cat. When E = [O(X ) , Set] for some space X , and λ is suitably chosen, it also permits sheaf or sheaf of rings structure. (iv) Let G be the category freely generated by the graph 0 1, so that op E = [G , Set] is the category of directed multigraphs, and let A = Δ be op the full subcategory of [G , Set] on graphs of the form // // // [n] := 0 1 ··· n for n > 0. op Δ is dense in [G , Set] because it contains the representables [0] and [1]. This example captures structure borne by graphs in which the operations build vertices and arrows from paths of arrows: for example, the structures of categories, involutive categories, and groupoids. (v) The globe category G is freely generated by the graph σ σ σ // // // 0 // 1 // 2 // ··· τ τ τ subject to the coglobular relations σσ = στ and τσ = ττ . This means that m−n m−n for each m > n, there are precisely two maps σ , τ : n m, which by abuse of notation we will write simply as σ and τ . op The category E = [G , Set] is the category of globular sets; it has a dense subcategory A = Θ , ﬁrst described by Berger [8], whose objects have been termed globular cardinals by Street [34]. The globular cardinals include the representables—the n-globes Y n for each n—but also shapes such as the 12 JOHN BOURKE AND RICHARD GARNER globular set with distinct cells as depicted below. // // (3.1) • • • @@ The globular cardinals can be parametrised in various ways, for instance using trees [7, 8]; following [27], we will use tables of dimensions—sequences ~n = (n , . . . , n ) of natural numbers of odd length with n > n < n . 1 k 2i−1 2i 2i+1 Given such a table ~n and a functor D : G → C, we obtain a diagram Dn Dn Dn 2 4 k−1 Dτ Dσ Dτ Dσ Dτ Dσ . . . || || "" || "" "" Dn Dn Dn Dn Dn 1 3 5 k−2 k whose colimit in C, when it exists, will be written as D(~n), and called the op D-globular sum indexed by ~n. Taking D = Y : G → [G , Set], the category op Θ of globular cardinals is now deﬁned as the full subcategory of [G , Set] spanned by the Y -globular sums. For example, the globular cardinal in (3.1) corresponds to the Y -globular sum Y (1, 0, 2, 1, 2). This example captures algebraic structures on globular sets in which the operations build globes out of diagrams with shapes like (3.1); these include strict ω-categories and strict ω-groupoids, but also the (globular) weak ω-categories and weak ω-groupoids studied in [7, 25, 3]. We now turn to examples over enriched bases. (vi) Let V be a locally ﬁnitely presentable symmetric monoidal category whose ﬁnitely presentable objects are closed under the tensor product (cf. [18]). By taking E = V and A = V a skeleton of the full sub-V -category of ﬁnitely presentable objects, we capture V -enriched ﬁnitary algebraic structure on V -objects as studied in [32]. When V = Cat this means structure on categories C built from functors and natural transformations C → C for ﬁnitely presentable I : which includes symmetric monoidal or ﬁnite limit structure, but not symmetric monoidal closed or factorization system structure. Similarly, when V = Ab, it includes A-module structure but not commutative ring structure. (vii) Taking V as before, taking E to be any locally ﬁnitely presentable V - category [18] and taking A = E a skeleton of the full subcategory of ﬁnitely presentable objects in E , we capture V -enriched ﬁnitary algebraic structure on E -objects as studied in [31]. As before, there is the obvious generalization from ﬁnitary to λ-ary structure. (viii) This example builds on [23]. Let V be a locally presentable symmetric monoidal closed category, and consider a class of V -enriched limit-types Φ with the property that the free Φ-completion of a small V -category is again small. A V -functor F : C → V with small domain is called Φ-ﬂat if its op cocontinuous extension Lan F : [C ,V ] → V preserves Φ-limits, and a ∈ V is Φ-presentable if V (a, –) : V → V preserves colimits by Φ-ﬂat weights. MONADS AND THEORIES 13 Suppose that if C is smal l and Φ-complete, then every Φ-continuous F : C → V is Φ-ﬂat; this is Axiom A of [23]. Then by Proposition 3.4 and §7.1 of ibid., we obtain an instance of our setting on taking E = V and A = V a skeleton of the full sub-V -category of Φ-presentable objects. A key example takes V = E = Cat and Φ the class of ﬁnite products; whereupon V is the subcategory F of ﬁnite cardinals, seen as discrete cat- egories. This example captures strongly ﬁnitary [19] structure on categories involving functors and transformations C → C; this includes monoidal or ﬁnite product structure, but not ﬁnite limit structure. (ix) More generally, we can take E = Φ-Cts(C,V ), the V -category of Φ-continuous functors C → V for some small Φ-complete C, and take A to be the full image op of the Yoneda embedding Y : C → Φ-Cts(C,V ). This example is appropriate to the study of “Φ-ary algebraic structure on E -objects”—subsuming most of the preceding examples. 3.2. Pretheories as presentations. We will now describe examples of pretheories and their models in various contexts; in doing so, it will be useful to avail ourselves of the following constructions. Given a pretheory A → T and objects a, b ∈ T , to adjoin a morphism f : a → b is to form the V -category T [f ] in the pushout square to the left of: ha,bi hf,gi // // 2 T 2 + 2 T (3.2) ι hid,idi ¯ι ¯ι f f =g // // 2 T [f ] 2 T [f =g] . Here, ι : 2 → 2 is the inclusion of the free V -category on the set {0, 1} into the free V -category 2 = {0 → 1} on an arrow. Since ι is identity-on-objects, its pushout ¯ι may also be chosen thus, so that we may speak of adjoining an arrow to a pretheory J : A → T to obtain the pretheory J [f ] = ¯ι◦ J : A → T [f ]. op Recall from (2.5) that a concrete T -model comprises X ∈ E and F ∈ [T ,V ] op for which F ◦ J = E (K –, X ) : A → V . Thus, by the universal property of the pushout (3.2), a concrete T [f ]-model is the same as a concrete T -model (X, F ) together with a map [f ] : E (Kb, X ) → E (Ka, X ) in V . Similarly given parallel morphisms f, g : a b in the underlying category of T we can form the pushout above right. In this way we may speak of adjoining an equation f = g to a pretheory J : A → T to obtain the pretheory J [f =g] = ¯ι◦J : A → T [f =g]. In this case, we see that a concrete T [f =g]-model is a concrete T -model (X, F ) such that Ff = Fg : E (Kb, X ) → E (Ka, X ). Example 9. In the context of Examples 8(i) appropriate to classical ﬁnitary algebraic theories— so V = E = Set and A = F—we will construct a pretheory J : F → M whose category of concrete models is the category of monoids. We start from the initial pretheory id : F → F whose concrete models are simply sets, and construct from it a pretheory J : F → M by adjoining morphisms 1 1 (3.3) m : 1 → 2 and i : 1 → 0 14 JOHN BOURKE AND RICHARD GARNER representing the monoid multiplication and unit operations, and also morphisms (3.4) m1, 1m : 2 3 and i1, 1i : 2 1 which will be necessary later to express the monoid equations. Note that our directional conventions mean that the input arity of these operations is in the codomain rather than the domain. It follows from the preceding remarks that a concrete M -model is a set X equipped with functions 2 3 2 [m] : X → X , [i] : 1 → X , [m1], [1m] : X X , [i1], [1i] : 1 X interpreting the morphisms adjoined above. We now adjoin to M the eight equations necessary to render commutative the following squares in M : m id i id // // // // 1 2 1 1 1 0 1 1 ι ι ι ι ι ι ι 1 1 1 1 1 ! 1 1 m1 1m i1 1i (3.5) // // // // 1 + 1 2 + 1 1 + 1 1 + 2 1 + 1 1 1 + 1 1 OO OO OO OO OO OO OO OO ι ι ι ι ι ι 2 2 2 2 2 id 2 ! id m id i // // // // 1 1 1 2 1 1 1 0 where ι , ι and ! are the images under J of the relevant coproduct injections or 1 2 1 maps from 0 in F; together with three equations which render commutative: m m m // // // 1 2 1 2 1 2 (3.6) 1m i1 1i 1 1 m1 // 2 3 1 1 . A concrete model for the resulting theory J : F → M is a concrete M -model op op (X, F ) for which F : M → Set sends each diagram in (3.5) and (3.6) to a 3 2 commuting one. Commutativity in (3.5) forces [m1] = [m]× id : X → X and so on; whereupon commutativity of (3.6) expresses precisely the monoid axioms, so that concrete M-models are monoids, as desired. Extending this analysis to morphisms we see that Mod (M) is isomorphic to the category of monoids and monoid homomorphisms. Example 10. In the same way we can describe F-pretheories modelling any of the categories of classical universal algebra—groups, rings and so on. Note that the same structure can be presented by distinct pretheories: for instance, we could extend the pretheoryM of the preceding example by adjoining a further morphism 4 3 m11 : 3 → 4 and two equations forcing it to become [m]× 1× 1 : X → X in any model; on doing so, we would not change the category of concrete models. However, in M, all of the maps 3 → 4 belong to F while in the new pretheory, m11 does not. This non-canonicity will be rectiﬁed by the theories introduced in Section 4 below; in particular, Corollary 24 implies that, to within isomorphism, there is at most one F-theory which captures a given type of structure. op Example 11. In the situation of Examples 8(iv), where E = [G , Set] is the category of directed graphs and A = Δ , we will describe a pretheory Δ → C 0 0 whose concrete models are categories. The construction is largely identical to the example of monoids above. Starting from the initial Δ -pretheory, we adjoin 0 MONADS AND THEORIES 15 composition and unit maps m : [1] → [2] and i : [1] → [0] as well as the morphisms 1m, m1 : [2] [3] and i1, 1i : [2] [1] required to describe the category axioms. We now adjoin the necessary equations. First, we have four equations ensuring that composition and identities interact appropriately with source and target: σ τ σ τ // // // // [0] [1] [0] [1] [0] [1] [0] [1] σ m τ m i i id id ι ι 1 2 // // [1] [2] [1] [2] [0] [0] where here we write σ, τ : [0] [1] for the two endpoint inclusions, and ι , ι 1 2 for the two colimit injections into [1] + [1] = [2]. We also require analogues τ σ of the eight equations of (3.5) and three equations of (3.6). The modiﬁcations are minor: replace n by [n], the coproduct inclusions ι : n → n + m ← m : ι 1 2 by the pushout inclusions ι : [n] → [n] + [m] ← [m] : ι , the ﬁrst appearance 1 τ σ 2 of ! : 0 → 1 by σ : [0] → [1] and its second appearance by τ : [0] → [1]. After adjoining these six morphisms and ﬁfteen equations, we ﬁnd that the concrete models of the resulting pretheory Δ → C are precisely smal l categories. We can extend this pretheory to one for groupoids. To do so, we adjoin a morphism c : [1] → [1] modelling the inversion plus the further maps 1c : [2] → [2] and c1 : [2] → [2] required for the axioms. Now four equations must be adjoined to force the correct interpretation of 1c and c1, plus the two equations for left and right inverses. On doing so, the resulting pretheory Δ → G has as its concrete models the smal l groupoids. Example 12. In the situation of Examples 8(v), where E is the category of globular sets and A = Θ is the full subcategory of globular cardinals, one can similarly construct pretheories whose concrete models are strict ω-categories or strict ω-groupoids. For instance, one encodes binary composition of n-cells along a k-cell boundary (for k < n) by adjoining morphisms m : Y (n) → Y (n, k, n) n,k to Θ . In fact, all of the standard ﬂavours of globular weak ω-category and weak ω-groupoid can also be encoded using Θ -pretheories; see Examples 44(v) below. Example 13. Consider the case of Examples 8(viii) where V = E = Cat and A = F, the full subcategory of ﬁnite cardinals (seen as discrete categories). We will describe an F-pretheory capturing the structure of a monoidal category. In doing so, we exploit the fact that our pretheories are no longer mere categories, but 2-categories; so we may speak not only of adjoining morphisms and equations between such, but also of adjoining an (invertible) 2-cel l —by taking a pushout of the inclusion 2 + 2 → D of the parallel pair 2-category into the free 2-category 2 2 on an (invertible) 2-cell—and similarly of adjoining an equation between 2-cel ls. To construct a pretheory for monoidal categories, we start essentially as for monoids: freely adjoining the usual maps m, i, m1, 1m, i1, 1i to the initial pretheory, but now also morphisms m11, 1m1, 11m : 3 → 4 and 1i1 : 3 → 2 needed for the monoidal category coherence axioms; thus, ten morphisms in all. 16 JOHN BOURKE AND RICHARD GARNER We now add the 8× 2 = 16 equations asserting that each of the morphisms beyond m and i has the expected interpretation in a model, plus the equation 1m◦ m11 = m1◦ 11m : 2 → 4. This being done, we next adjoin invertible 2-cells // 22 22 2 2 1 2 m m KS i1 1i m α m1 // // // 1 1 1 1 2 3 1 1 1m expressing the associativity and unit coherences, as well as the invertible 2-cells m1 1m 22 22 // // 3 3 2 3 2 3 1m m1 KS 1i1 1i1 ρ1 m1 α1 m11 1m 1α 1m1 1λ // // // // 2 2 2 2 3 4 3 4 1 1 1m1 11m which will be needed to express the coherence axioms. Finally, we must adjoin equations between 2-cells: the 2× 4 = 8 equations ensuring that α1, 1α, 1λ and ρ1 have the intended interpretation in any model, plus two equations expressing the coherence axioms: m1 m1 // // 2 3 2 3 >> >> >> m m11 m m11 m1 α1 1m // // m α (3.7) 1 2 4 = 1 3 1m1 4 >> >> >> m1 1m 1α m m 11m 11m // // 2 3 2 3 1m 1m 2 2 id id @@ @@ m m m1 ρ1 // (3.8) 1 3 1i1 2 = 1 id 2 . @@ DD EE 1λ 1m m m id id 2 2 All told, we have adjoined ten morphisms, seventeen equations between morph- isms, seven invertible 2-cells, and nine equations between 2-cells to obtain a pretheory J : F → MC whose concrete models are precisely monoidal categories. 4. The monad–theory correspondence In this section, we return to the general theory and establish our “best pos- sible” monad–theory correspondence. This will be obtained by restricting the adjunction (2.1) to its ﬁxpoints: the objects on the left and right at which the counit and the unit are invertible. The categories of ﬁxpoints are the largest It may be prima facie unclear why this is necessary; after all, if 1m, m11, m1 and 11m have the intended interpretations in a model, then it is certainly the case that they will verify this equality. Yet this equality is not forced to hold in the pretheory, and we need it to do so in order for (3.7) to type-check. MONADS AND THEORIES 17 subcategories on which the adjunction becomes an adjoint equivalence, and it is in this sense that our monad–theory correspondence is the best possible. 4.1. A pullback lemma. The following lemma will be crucial in characterising the ﬁxpoints of (2.1) on each side. Note that the force of (2) below is in the “if” direction; the “only if” is always true. Lemma 14. A commuting square in V -CAT // A B H K // C D with G ful ly faithful and H, K discrete isoﬁbrations is a pul lback just when: (1) F is ful ly faithful; and (2) An object b ∈ B is in the essential image of F if and only if Kb is in the essential image of G. Proof. If the square is a pullback, then F is fully faithful as a pullback of G. As ∼ ∼ for (2), if Kb Gc in D then since K is an isoﬁbration we can ﬁnd b b in B = = 0 0 with Kb = Gc; now by the pullback property we induce a ∈ A with Fa = b so that b Fa as required. Suppose conversely that (1) and (2) hold. We form the pullback P of K along G and the induced map L as below. // P B (4.1) !! // C D P is fully faithful as a pullback of G, and F is so by assumption; whence by standard cancellativity properties of fully faithful functors, L is also fully faithful. In fact, discrete isoﬁbrations are also stable under pullback, and also have the same cancellativity property; this follows from the fact that they are the exactly the maps with the unique right lifting property against the inclusion of the free V -category on an object into the free V -category on an isomorphism. Consequently, in (4.1), Q is a discrete isoﬁbration as a pullback of K , and H is so by assumption; whence by cancellativity, L is also a discrete isoﬁbration. If we can now show L is also essentially surjective, we will be done: for then L is a discrete isoﬁbration and an equivalence, whence invertible. So let (b, c) ∈ P . Since Kb = Gc, by (2) we have that b is in the essential image of F . So there ∼ ∼ is a ∈ A and an isomorphism β : b = Fa. Now Kβ : Gc = Kb = KFa = GHa so by full ﬁdelity of G there is γ : c Ha with Gγ = Kβ; and so we have (β, γ) : (b, c) La exhibiting (b, c) as in the essential image of L, as required. 4.2. A-theories. We ﬁrst use the pullback lemma to describe the ﬁxpoints of (2.1) on the pretheory side. 18 JOHN BOURKE AND RICHARD GARNER Deﬁnition 15. An A-pretheory J : A → T is said to be an A-theory if each op T (J –, a) ∈ [A ,V ] is a K -nerve. We write Th (E ) for the full subcategory of Preth (E ) on the A-theories. In the language of Section 5.2 below, a pretheory T is an A-theory just op when each representable T (–, a) : T → V is a (non-concrete) T -model. When V = E = Set and A = F, an A-pretheory is an A-theory precisely when it is a Lawvere theory; see Examples 44(i) below. Theorem 16. An A-pretheory J : A → T is an A-theory if and only if the unit component η : T → ΦΨT of (2.1) is invertible. Proof. The unit η : T → ΦΨT is obtained by starting with α = 1 : ΨT → ΨT T 0 and chasing through the bijections of Theorem 6 to obtain α = η . Doing this, 6 T we quickly arrive at α equal to P , the projection in the depicted pullback square op P J ΨT op op op // // E [T ,V ] A T op op op ΨT α [J ,1] (J ) 4 U ΨT (4.2) op xx ss op op ΨT op ΨT // // // E [A ,V ] (A ) (E ) [E ,V ] ΨT rep op (K ) Y ΨT ΨT ΨT op deﬁning E . Now α : E → [T ,V ] is obtained by lifting an isomorphism op through [J , 1] and so we have α P . We obtain α by transposing α through 3 4 3 t ΨT op ∼ op ΨT the isomorphism (–) : V -CAT(E , [T ,V ]) = V -CAT(T , [E ,V ] ) dis- pwr rep played in (2.12). The relationships between α , α and the unit component 4 5 η = α are depicted in the commutative diagram above right. T 6 The identity-on-objects unit η = α will be invertible just when it is fully T 6 faithful which, since K is fully faithful, will be so just when α is fully faithful. ΨT 5 op t t Now, since P α = (α ) = (Y ◦ α ) = N , and P is fully faithful, as the 3 4 α 5 5 ΨT op pullback of the fully faithful N , it follows that N : E → [T ,V ] is also K α fully faithful. As a consequence, α is fully faithful just when there exists a factorisation to within isomorphism: ΨT op (4.3) Y N ◦ G : T → E → [T ,V ] . Indeed, in one direction, if α is fully faithful then the canonical natural transform- ation Y ⇒ N ◦ α is invertible. In the other, given a factorisation as displayed, α 5 G is fully faithful since N and Y are. Moreover we have isomorphisms ΨT op op ΨT ∼ ∼ ∼ E (α b, –) [T ,V ](Y b, N –) [T ,V ](N Gb, N –) E (Gb, –) = = = 5 α α α 5 5 5 natural in b. So by Yoneda, α = G and so α is fully faithful since G is so. 5 5 This shows that η is invertible just when there is a factorisation (4.3). Since N is fully faithful this in turn is equivalent to asking that each Y b = T (–, b) lies in the essential image of α , or equally in the essential image of the isomorphic P . As the left square of (4.2) is a pullback, Lemma 14 asserts that this is, in turn, op equivalent to each [J , 1](Y b) = T (J –, b) being in the essential image of N ; which is precisely the condition that J is an A-theory. MONADS AND THEORIES 19 4.3. A-nervous monads. We now characterise the ﬁxpoints on the monad side. In the following deﬁnition, A , J and K are as in (2.7). T T T Deﬁnition 17. A V -monad T on E is called A-nervous if (i) The fully faithful K : A → E is dense; T T op op (ii) A presheaf X ∈ [A ,V ] is a K -nerve if and only if X ◦ J is a K -nerve. T T T We write Mnd (E ) for the full subcategory of Mnd(E ) on the A-nervous monads. T T T Note that the adjointness isomorphisms E (K J X, Y ) = E (F KX, Y ) = T T T T T E (KX, U Y ) for the adjunction F a U give a pseudo-commutative square T op // E [A ,V ] (4.4) op T ∼ [J ,1] U = T op // E [A ,V ] ; op as a result of which, [J , 1] maps K -nerves to K -nerves. Thus the force of clause (ii) of the preceding deﬁnition lies in the if direction. Theorem 18. The counit component ε : ΨΦT → T of (2.1) at a monad T on E is invertible if and only if T is A-nervous. Proof. ε is obtained by taking α = 1 : J → J and proceeding in reverse T 6 T T order through the series of six natural isomorphisms in the proof of Theorem 6. T op Doing this, we quickly reach α = N . Then α : E → [(A ) ,V ] is obtained 3 K 2 T by lifting the natural isomorphism ϕ of (4.4) through the discrete isoﬁbration op [J , 1], yielding a commutative square as left below. T op 1 // T ΨΦT E [(A ) ,V ] // E E op (4.5) [J ,1] ΨΦT K '' op // E [A ,V ] E . T ΨΦT The map α : E → E is the unique map to the pullback, and α = ε the 1 0 T corresponding morphism of monads. It follows that ε is invertible if and only the square to the left of (4.5) is a pullback. Both vertical legs are discrete isoﬁbrations and N is fully faithful, so by Lemma 14 this happens just when, op ﬁrstly, α is fully faithful, and, secondly, X ∈ [A ,V ] is in the essential image of α if and only if XJ is a K -nerve. But as α N , and natural isomorphism 2 T 2 K does not change either full ﬁdelity or essential images, this happens just when T is A-nervous. 4.4. The monad–theory equivalence. Putting together the preceding results now yields the main result of this paper. Theorem 19. The adjunction (2.1) restricts to an adjoint equivalence oo (4.6) Mnd (E ) ⊥ Th (E ) A // A between the category of A-nervous monads and the category of A-theories. 20 JOHN BOURKE AND RICHARD GARNER Proof. Any adjunction restricts to an adjoint equivalence between the objects with invertible unit and counit components respectively, and Theorems 16 and 18 identify these objects as the A-theories and the A-nervous monads. Note that there is an asymmetry between the conditions found on each side. On the one hand, the condition characterising the A-theories among the A- pretheories is intrinsic, and easy to check in practice. On the other hand, the condition deﬁning an A-nervous monad refers to the associated pretheory, and is non-trivial to check in practice. Indeed, one of the main points of [35, 9] is to provide a general set of suﬃcient conditions under which a monad can be shown to be A-nervous. In the sections which follow, we will provide a number of more tractable characterisations of the A-theories and A-nervous monads; the crucial fact which drives all of these is that the adjunction (2.1) is in fact idempotent. Recall that an adjunction L a R : D → C is idempotent if the monad RL on C is idempotent, and that this is equivalent to asking that the comonad LR is idempotent, or that any one of the natural transformations Rε, εL, ηR and Lη is invertible. Theorem 20. The adjunction (2.1) is idempotent. Proof. We show for each T ∈ Mnd(E ) that the unit η : ΦT → ΦΨΦT is ΦT invertible. By Theorem 16, this is equally to show that J : A → A is an A- T T op ∼ theory, i.e., that each A (J –, J a) ∈ [A ,V ] is a K -nerve. But A (J –, J a) = T T T T T T T T T T T E (F K –, F Ka) = E (K –, U F Ka) = E (K –, TKa) as required. Exploiting the alternative characterisations of idempotent adjunctions listed above, we immediately obtain the following result, which tells us in particular that a monad T is A-nervous if and only if it can be presented by some A-pretheory. Corollary 21. A monad T on E is A-nervous if and only if T ΨT for some A-pretheory J : A → T ; while an A-pretheory J : A → T is an A-theory if and only if T ΦT for some monad T on E . The next result also follows directly from the deﬁnition of idempotent adjunc- tion. Corollary 22. The ful l subcategory Mnd (E ) ⊆ Mnd(E ) is coreﬂective via ΨΦ, while the ful l subcategory Th (E ) ⊆ Preth (E ) is reﬂective via ΦΨ. A A 5. Semantics In the next section, we will explicitly identify the A-nervous monads and A-theories for the examples listed in Section 2.1. Before doing this, we study further aspects of the general theory, namely those related to the taking of semantics. 5.1. Interaction with the semantics functors. We begin by examining the in- teraction of our monad–theory correspondence with the semantics functors of Section 2. In fact, we begin at the level of the monad–pretheory adjunction (2.1). MONADS AND THEORIES 21 Proposition 23. There is a natural isomorphism θ as on the left in: op op Ψ Φ op op op op // // Preth (E ) Mnd(E ) Mnd(E ) Preth (E ) A A θ θ ks +3 Mod Alg Alg Mod c c "" || "" || V -CAT/E V -CAT/E . op op Let θ be its mate under the adjunction Φ a Ψ , as right above. The component of θ at T ∈ Mnd(E ) is invertible if and only if T is A-nervous. Proof. For the ﬁrst claim, Theorem 6 provides the necessary natural isomorphisms ΨT θ : E → Mod (T ) over E . For the second, if we write as before ε : ΨΦT → T T c T for the counit component of (2.1) at T ∈ Mnd(E ), then the T-component of θ ∗ T ΨΦT is the composite θ ◦ (ε ) : E → E → Mod (ΦT ) over E . Since θ is c ΨT ΨT T invertible and since Alg is fully faithful, θ will be invertible just when ε is so; T T that is, by Theorem 18, just when T is A-nervous. From this and the fact that each monad ΨT is A-nervous, it follows that an A- pretheory T and its associated theory ΦΨT have isomorphic categories of concrete models. By contrast, the passage from a monad T to its A-nervous coreﬂection ΨΦT may well change the category of algebras. For example, the power-set monad on Set, whose algebras are complete lattices, has its F-nervous coreﬂection given by the ﬁnite-power-set monad, whose algebras are ∨-semilattices. However, if we restrict to A-nervous monads and A-theories, then the situation is much better behaved. Theorem 24. The monad–theory equivalence (4.6) commutes with the semantics functors; that is, we have natural isomorphisms: op op Ψ Φ op op op op // // Th (E ) Mnd (E ) Mnd (E ) Th (E ) A A A A θ θ ks +3 (5.1) Mod Alg Alg Mod c c !! }} !! }} V -CAT/E V -CAT/E . op op Moreover, both Mod : Th (E ) → V -CAT/E and Alg : Mnd (E ) → V -CAT/E c A A are ful ly faithful functors. Proof. The ﬁrst statement follows from Proposition 23. For the second, note op that Alg : Mnd (E ) → V -CAT/E is obtained by restricting the fully faithful op Alg : Mnd(E ) → V -CAT/E along a full embedding, and so is itself fully faithful. op op It follows that Mod = Alg◦Ψ : Th (E ) → V -CAT/E is also fully faithful. c A op Full ﬁdelity of Mod : Th (E ) → V -CAT/E means that an A-theory is c A determined to within isomorphism by its category of concrete models over E . This rectiﬁes the non-uniqueness of pretheories noted in Example 10 above. 5.2. Non-concrete models. In Section 2.3 we deﬁned a concrete model of an A- op pretheoryT to be an object X ∈ E endowed with an extension ofE (K –, X ) : A → op V to a functor T → V . In the literature, one often encounters a looser notion of model for a theory, in which an underlying object in E is not provided. In our 22 JOHN BOURKE AND RICHARD GARNER setting, this notion becomes the following one: by an (unqualiﬁed) T -model, we op op op mean a functor F : T → V whose restriction FJ : A → V is a K -nerve. op The T -models span a full sub-V -category Mod(T ) of [T ,V ]. Recalling from op Section 2.1 that K -Ner(V ) denotes the full sub-V -category of [A ,V ] on the K -nerves, we may also express Mod(T ) as a pullback as to the right in: ++ op // // Mod (T ) Mod(T ) [T ,V ] (5.2) op U W [J ,1] T T op // // E K -Ner(V ) [A ,V ] . On the other hand, Mod (T ) is the pullback around the outside, and so there is a canonical induced map Mod (T ) → Mod(T ) as displayed. By the usual cancellativity properties, the left square above is now also a pullback. Moreover, op W is an isoﬁbration, as a pullback of the discrete isoﬁbration [J , 1], and N : E → K -Ner(V ) is an equivalence. Since equivalences are stable under pullback along isoﬁbrations, we conclude that: Proposition 25. The comparison Mod (T ) → Mod(T ) in (5.2) is an equivalence. Taking non-concrete models gives rise to a semantics functor landing in V -CAT/K -Ner(V ) which, like before, is not fully faithful on A-pretheories, but is so on the subcategory of A-theories. Note that the “underlying K -nerve” of a T -model is more natural than it might seem, being the special case of the functor Mod(T ) → Mod(S ) induced by a morphism of A-pretheories for which S is the initial pretheory. However, in the following result, for simplicity, we view the semantics functors for T -models as landing simply in V -CAT. Theorem 26. The monad–theory equivalence (4.6) commutes with the non-concrete semantics functors in the sense that we have natural transformations op op Ψ Φ op op op op // // Th (E ) Mnd (E ) Mnd (E ) Th (E ) A A A A θ θ ks +3 Mod Alg Alg Mod !! }} !! }} V -CAT V -CAT whose components are equivalences in V -CAT. Proof. First postcompose the natural isomorphisms (5.1) with the forgetful functor V -CAT/E → V -CAT. Then paste with the natural transformation op Mod ⇒ Mod : Th (E ) → V -CAT coming from the previous proposition. c A 5.3. Local presentability and algebraic left adjoints. Next in this section, we consider the categorical properties of the V -categories and V -functors in the image of the semantics functors. We begin with the case of pretheories. Proposition 27. (i) If J : A → T is an A-pretheory then Mod (T ) is local ly presentable and U : Mod (T ) → E is a strictly monadic right adjoint. T c (ii) If H : T → S is a map of A-pretheories, then H : Mod (S ) → Mod (T ) is c c a strictly monadic right adjoint. MONADS AND THEORIES 23 Proof. (i) follows from Lemma 5 and the description in (2.5) of Mod (T ) → E as a pullback. For (ii), applying the standard cancellativity properties to the pullbacks deﬁning Mod (S ) and Mod (T ) yields a pullback square c c op // Mod (S ) [S ,V ] op [H ,1] op // Mod (T ) [T ,V ] . op Since [H , 1] is strictly monadic and P is a right adjoint between locally presentable categories, the result follows again from Lemma 5. Composing with the equivalence Mod (T ) ' Mod(T ) of Proposition 25, this result immediately implies the local presentability of the category Mod(T ) of non-concrete models. Likewise, in the non-concrete setting, the analogue of Proposition 27 remains true on replacing “strict monadicity” by “monadicity” throughout. On the other hand, taken together with Proposition 23, it immedi- ately implies the corresponding result for nervous monads. We state this here as: Proposition 28. (i) If T is an A-nervous monad then E is local ly presentable, T T and U : E → E is a strictly monadic right adjoint. ∗ S T (ii) If α : T → S is a map of A-nervous monads, then α : E → E is a strictly monadic right adjoint. 5.4. Algebraic colimits of monads and theories. To conclude this section, we examine the interaction of the semantics functors with colimits. We begin with the op more-or-less classical case of the semantics functor for monads Alg : Mnd(E ) → V -CAT/E . In general, Mnd(E ) need not be cocomplete. Indeed, when V = E = Set, it does not even have all binary coproducts; see [5, Proposition 6.10]. However many colimits of monads do exist, and an important point about these is that, in the terminology of [16], they are algebraic. That is, they are sent to limits by op the semantics functor Alg : Mnd(E ) → V -CAT/E . To prove this, we use the following lemma, which is a mild variant of the standard result that right adjoints preserve limits. Lemma 29. Let C be a complete (ordinary) category with a strongly generating class of objects X and consider a functor U : A → C. If each x ∈ X admits a reﬂection along U then U preserves any limits that exist in A. Proof. As X is a strong generator, the functors C(x, –) with x ∈ X jointly reﬂect isomorphisms, and so jointly reﬂect limits. Accordingly U preserves any limits that are preserved by C(x, U –) for each x ∈ X . But each C(x, U –) is representable and so preserves all limits; whence U preserves any limits that exist. In the setting of Set-enriched categories the following result, expressing the algebraicity of colimits of monads, is a special case of Proposition 26.3 of [16]. op Proposition 30. Alg : Mnd(E ) → V -CAT/E preserves limits. 24 JOHN BOURKE AND RICHARD GARNER Proof. The V -functors F : X → E with small domain form a strong generator for V -CAT/E . Moreover, it is shown in [12, Theorem II.1.1] that each such F op has a reﬂection along Alg : Mnd(E ) → V -CAT/E given by its codensity monad Ran (F ) : E → E . The result thus follows from Lemma 29. We now adapt the above results concerning Mnd(E ) to the cases of Preth (E ), Mnd (E ) and Th (E ). In Theorem 38 below, we will see that these categories A A are locally presentable; in particular, and by contrast with Mnd(E ), they are cocomplete. It is also not diﬃcult to prove the cocompleteness directly. op Proposition 31. Each of the semantics functors Alg : Mnd (E ) → V -CAT/E , op op Mod : Preth (E ) → V -CAT/E and Mod : Th (E ) → V -CAT/E preserves c A c A limits. Proof. These three functors are isomorphic to the respective composites: op Alg incl op op (5.3) Mnd (E ) −−−−→Mnd(E ) −−→ V -CAT/E op Alg op op (5.4) Preth (E ) −−−→Mnd(E ) −−→ V -CAT/E op Alg op op (5.5) Th (E ) −−−→Mnd(E ) −−→ V -CAT/E ; for (5.3) this is clear, while for (5.4) and (5.5) it follows from Proposition 23. The common second functor in each composite is limit-preserving by Proposition 30, while the ﬁrst functor is limit-preserving in each case since it is the opposite of a left adjoint functor—by Corollary 22, Theorem 6 and Theorem 19 (taken together with Corollary 22) respectively. We leave it to the reader to formulate this result also for non-concrete models. 6. The monad–theory correspondence in practice In this section, we return to the examples of our general setting described in Section 2.1, with the goal of describing as explicitly as possible what the A-nervous monads, the A-theories, and the corresponding models look like in each case. By way of these descriptions, we will re-ﬁnd many of the monad–theory correspondences existing in the literature as instances of our main Theorem 19. To obtain our explicit descriptions, we will require some further results which characterise A-theories and A-nervous monads in particular situations. We begin this section by describing these results. 6.1. Theories in the presheaf context. A number of the examples of our basic op setting described in Section 3.1 arise in the following manner. We take E = [C ,V ] a presheaf category, and take A to be any full subcategory of E containing the representables. In this situation, we then have a factorisation I K op // // (6.1) C A [C ,V ] = E op of the Yoneda embedding. The Yoneda lemma implies that Y : C → [C ,V ] is dense, whereupon by Theorem 5.13 of [17], both I and K are too. In particular, K provides an instance of our basic setting; we will call this the presheaf context. Each of Examples 8(i), (iv), (v), (vi), and (viii) arise in this way. MONADS AND THEORIES 25 ∼ ∼ op Lemma 32. In the presheaf context, we have N = K and N = Ran . I K I op Moreover, a functor F : A → V is a K -nerve just when it is the right Kan op op op extension of its restriction along I : C → A . Proof. For the ﬁrst isomorphism we calculate that op op ∼ ∼ (6.2) N (x) = A(I –, x) = [C ,V ](KI –, Kx) = [C ,V ](Y –, Kx) = Kx by full ﬁdelity of K and the Yoneda lemma. For the second, since Lan K a N Y K op op op op and [I , 1] a Ran op it suﬃces to show Lan K [I , 1] : [A ,V ] → [C ,V ]. I Y op Since both are cocontinuous, it suﬃces to show (Lan K )Y [I , 1]Y , which op ∼ ∼ follows since (Lan K )Y K N = [I , 1]Y using full ﬁdelity of Y and (6.2). = = Y I op op Finally, since I is fully faithful, F : A → V is a right Kan extension along op I just when it is the right Kan extension of its own restriction. Thus the ﬁnal op claim follows using the isomorphism N Ran . K I In this setting, we have practically useful characterisations of the A-theories and their (non-concrete) models. Proposition 33. Let J : A → T be an A-pretheory in the presheaf context (6.1). op op op (i) A functor F : T → V is a T -model just when FJ : A → V is the right op op op Kan extension of its restriction along I : C → A ; (ii) J : A → T is itself an A-theory just when it is the pointwise left Kan extension of its restriction along I : C → A. Proof. (i) follows immediately from Lemma 32 since, by deﬁnition, F is a T - op model just when FJ is a K -nerve. For (ii), note that by Proposition 4.46 of [17], J : A → T is the pointwise left Kan extension of its restriction along op I just when, for each x ∈ T , the functor T (J –, x) : A → V is the right Kan op extension of its restriction along I . By Lemma 32, this happens just when each T (J –, x) is a K -nerve—that is, just when J is a A-theory. We can sharpen these results using Day’s notion of density presentation [11]. The density of an ordinary functor K : C → D is often introduced as the assertion that each object of D is the colimit of a certain diagram in the image of K . It is this perspective that the notion of density presentation generalises. A family of colimits Φ in the ordinary category D is a class of diagrams (D : J → D) each of which has a colimit in D. In the enriched case, a family i i i∈I op of colimits Φ in theV -categoryD is a class of pairs (W ∈ [J ,V ], D : J → D) i i i i∈I such that each weighted colimit W ? D exists in D. In either case, a full replete i i subcategory B of D is closed in D under Φ-colimits if it contains the (weighted) colimit of any D in Φ whenever it contains each vertex of D . We say that D i i is the closure of B under Φ-colimits if the only replete full subcategory of D containing B and closed under Φ-colimits is D itself. Now given a fully faithful K : C → D, we say that a colimit in D is K -absolute if it is preserved by N , or equivalently, by each representable D(Kx, –) : D → V . If D is the closure of C under a family Φ of K -absolute colimits then Φ is said to be a density presentation for K . The nomenclature is justiﬁed by Theorem 5.19 of [17], which, among other things, says that the fully faithful K has a density presentation just when it is dense. 26 JOHN BOURKE AND RICHARD GARNER We will make use of density presentations in the presheaf context (6.1) with respect not to the dense K , but to the dense I . By Lemma 32 we have N = K , and so the I -absolute colimits are in this case those preserved by K : A → E . We will see numerous instances of this situation in Section 6.3 below; we give a couple of examples now to clarify the ideas. Examples 34. (i) Example 8(i) corresponds to the presheaf context I K // // 1 F Set , and here I has a density presentation given by all ﬁnite copowers of 1 ∈ F; these are I -absolute since K preserves them. In fact, F has all ﬁnite cop- roducts and these are preserved by K , so that there is a larger density presentation given by al l ﬁnite coproducts in F. (ii) Example 8(iv) yields the presheaf context below, wherein I has a density presentation given by the wide pushouts [n] [1] + [1] + . . . + [1]: [0] [0] [0] I K op // // G Δ [G , Set] . 1 0 1 The reason we care about density presentations is the following result, which comprises various parts of Theorem 5.29 of [17]. Proposition 35. Let K : C → D be ful ly faithful and dense. The fol lowing are equivalent: (i) F : D → E is the pointwise left Kan extension of its restriction along K ; (ii) F sends Φ-colimits to colimits for any density presentation Φ of K ; (iii) F sends K -absolute colimits to colimits. Combined with Proposition 33, this yields the desired sharper characterisation of the A-theories and their models. Theorem 36. Let J : A → T be an A-pretheory in the presheaf context (6.1), and let Φ be a density presentation for I . op op op (i) A functor F : T → V is a T -model just when FJ : A → V sends Φ-colimits in A to limits in V ; (ii) J : A → T is an A-theory just when it sends Φ-colimits to colimits. 6.2. Nervous monads, signatures and saturated classes. We now turn from char- acterisations for A-theories to characterisations for A-nervous monads. We know from Corollary 21 that a monad is A-nervous just when it is isomorphic to ΨT for some A-pretheory J : A → T , and the examples in Section 3 make it an intuitively reasonable idea that these are the monads which can be “presented by operations and equations with arities from A”. Our ﬁrst characterisation result makes this idea precise by exhibiting the category of A-nervous monads as monadic over a category of signatures. We defer the proof of this result to Section 8. Deﬁnition 37. The category Sig (E ) of signatures is the categoryV -CAT(obA,E ). We write V : Mnd(E ) → Sig (E ) for the functor sending T to (Ta) . a∈A A MONADS AND THEORIES 27 Theorem 38. V : Mnd(E ) → Sig (E ) has a left adjoint F : Sig (E ) → Mnd(E ) A A taking values in A-nervous monads. Moreover: (i) The restricted functor V : Mnd (E ) → Sig (E ) is monadic; (ii) A monad T ∈ Mnd(E ) is A-nervous if and only if it is a colimit in Mnd(E ) of monads in the image of F ; (iii) Each of Mnd (E ), Preth (E ) and Th (E ) is local ly presentable. A A A The idea behind this result originates in [20]. A signature Σ ∈ Sig (E ) speciﬁes for each a ∈ A an E -object Σa of “operations of input arity a”. The free monad F Σ on this signature has as its algebras the Σ-structures: objects X ∈ E endowed with a function E (a, X ) → E (Σa, X ) for each a ∈ A. The above result implies that a monad T ∈ Mnd(E ) is A-nervous just when it admits a presentation as a coequaliser F Γ F Σ T—that is, a presentation by a signature Σ of basic operations together with a family Γ of equations between derived operations. We now turn to our second characterisation result for A-nervous monads. This is motivated by the fact, noted in the introduction, that in many monad–theory correspondences the class of monads can be characterised by a colimit-preservation property. To reproduce this result in our setting, we require a closure property of the arities in the subcategory A which, roughly speaking, says that substituting A-ary operations into A-ary operations again yields A-ary operations. Deﬁnition 39. An endo-V -functor F : E → E is called A-induced if it is the pointwise left Kan extension of its restriction along K . We call A a saturated class of arities if A-induced endofunctors of E are closed under composition. Example 40. In the case of K : F ,→ Set, there is a density presentation for K given by al l ﬁltered colimits in Set, so that by Proposition 35, an endofunctor Set → Set is F-induced just when it preserves ﬁltered colimits. Thus F ,→ Set is a saturated class of arities. Example 41. More generally, if Φ is a class of enriched colimit-types and K : A → E exhibits E as the free cocompletion of A under Φ-colimits, then there is a density presentation of K given by all Φ-colimits, and an endofunctor of E is K -induced just when it preserves Φ-colimits. Thus A is a saturated class of arities. Example 42. Let K : A ,→ Set be the inclusion of the one-object full subcategory A on the two-element set 2 = {0, 1}. Since the dense generator 1 of Set is a retract of 2, and taking retracts does not change categories of presheaves, A is dense in Set. We claim it does not give a saturated class of arities. To see this, note ﬁrst that (–) : Set → Set is A-induced, being a left Kan 2 2 extension along K of the representableA(2, –) : A → Set. We claim that (–) ◦(–) is not A-induced. For indeed, by the Yoneda lemma, any X ∈ [A, Set] has an epimorphic cover by copies of the unique representable A(2, –). Since left Kan extension preserves epimorphisms, each Lan (X ) admits an epimorphic cover by 2 2 2 4 copies of (–) . But (–) ◦ (–) = (–) can admit no such cover, since the identity map on 4 does not factor through 2, and so cannot be A-induced. The proof of the following result will again be deferred to Section 8 below. 28 JOHN BOURKE AND RICHARD GARNER Theorem 43. Let A be a saturated class of arities in E . The fol lowing are equivalent properties of a monad T ∈ Mnd(E ): (i) T is A-nervous; (ii) T : E → E is A-induced; (iii) T : E → E preserves Φ-colimits for any density presentation Φ of K . 6.3. The monad–theory equivalence in practice. We now apply our characterisa- tion results to the examples of Section 2.1. In many cases, the explicit descriptions we obtain of the A-nervous monads, the A-theories, and their models will allow us to reconstruct a familiar monad–theory correspondence from the literature. Examples 44. As before, we begin with the unenriched examples where V = Set. (i) The case E = Set and A = F corresponds to the instance of the presheaf context described in Examples 34(i). Applied to the density presentations for I given there, Theorem 36 tells us that an F-pretheory J : F → T is an F- theory just when it preserves ﬁnite copowers of 1, or equally (using the larger density presentation) all ﬁnite coproducts. It thus follows that the F-theories op are the Lawvere theories of [24]. Moreover a functor F : T → Set is a T - op op model if and only if FJ : F → Set preserves ﬁnite products. Since, in this op case, J also reﬂects ﬁnite coproducts, this happens just when F : T → Set is itself ﬁnite-product-preserving, that is, just when F is a model of the Lawvere theory T . On the other hand, by Example 40, F is a saturated class of arities, and the F-induced endofunctors are the ﬁnitary ones; so by Theorem 43, a monad on Set is F-nervous just when it is ﬁnitary. Theorem 19 thus specialises to the classical ﬁnitary monad–Lawvere theory correspondence, while Theorem 26 recaptures its compatibility with semantics. (ii) When E is locally ﬁnitely presentable and A = E , the category of K -nerves op is, by [13, Kollar 7.9], the full subcategory of [E , Set] on the ﬁnite-limit- preserving functors. So an E -pretheory J : E → T is an E -theory just when f f f op each T (J –, a) : E → Set preserves ﬁnite limits. By the Yoneda lemma, this happens just when J preserves ﬁnite colimits, so that the E -theories are precisely [31]’s Lawvere E -theories. The concrete T -models in this setting are exactly the models of [31, op Deﬁnition 2.2]. The general T -models are those functors F : T → Set op op for which FJ : E → Set is a K -nerve, i.e., ﬁnite-limit-preserving; these are the more general models of [22, Deﬁnition 12], and the correspondence between the two notions in Proposition 25 recaptures Proposition 15 of ibid. On the monad side, since K : E → E exhibits E as the free ﬁltered-colimit completion of E , Example 41 and Theorem 43 imply that E is a saturated f f class, and that the E -nervous monads are the ﬁnitary ones. So in this case, Theorem 19 and Corollary 24 reconstruct (the unenriched version of) the monad–theory correspondence given in [31, Theorem 5.2]. (iii) More generally, when E is locally λ-presentable and A = E is a skeleton of the full subcategory of λ-presentable objects, the E -theories are those pretheories J : E → T which preserve λ-small colimits; the T -models are λ MONADS AND THEORIES 29 op op functors F : T → Set for which FJ preserves λ-small limits; and the E -nervous monads are those whose endofunctor preserves λ-ﬁltered colimits. op (iv) When E = [G , Set] and A = Δ , we are in the presheaf context of Ex- amples 34(ii). For the density presentation for I given there, Theorem 36 tells us that a pretheory J : Δ → T is a Δ -theory just when it preserves 0 0 the wide pushouts [n] = [1] + [1] + . . . + [1]. Moreover, a functor [0] [0] [0] op X : T → Set is a T -model just when it sends each of these wide pushouts to a limit in Set. This is precisely the Segal condition of [33]; in elementary terms, it requires the invertibility of each canonical map (6.3) Xn −→ X 1× X 1× ···× X 1 . X 0 X 0 X 0 In Corollary 49 below we will see that Δ is not a saturated class of arities, and so we have no more direct characterisations of the Δ -nervous monads than is given by Corollary 21 or Theorem 38. However, Example 11 provides us with natural examples of Δ -nervous monads: namely, the monads T op and T for categories and for groupoids on [G , Set]. As was already noted in [35], the nervosity of T recaptures the classical nerve theorem relating categories and simplicial sets. Indeed, the Δ -theory associated to T is the ﬁrst part of the (bijective-on-objects, fully faithful) factorisation J K T T Δ −−→ Δ −−→ Cat of the composite F K : Δ → Cat. The interposing object here is the T 0 topologist’s simplex category Δ, with K the standard inclusion into Cat. Thus, to say that T is Δ -nervous is to say that: op (a) The classical nerve functor N : Cat → [Δ , Set] is fully faithful; op (b) The essential image of N comprises those X ∈ [Δ , Set] for which XJ is a K -nerve. This much is already done in [35], but our use of density presentations allows for a small improvement. To say that XJ is a K -nerve in (b) is equally to say that X is a T -model, or equally that X satisﬁes the Segal condition expressed by the invertibility of each (6.3). This is a mild sharpening of [35], where the “Segal condition” is left in the abstract form given in (b) above. In a similar way, the nervosity of the monad T for small groupoids captures the “symmetric nerve theorem”. This states that the functor op Gpd → [F , Set] sending a groupoid to its symmetric nerve—indexed by the category of non-empty ﬁnite sets—is fully faithful, and characterises the essential image once again as the functors satisfying the Segal condition (6.3). op (v) With E = [G , Set] and A = Θ , we are now in the presheaf context I K op // // G Θ [G , Set] . I has a density presentation given by the I -globular sums (n , . . . , n ) = 1 k (n ) + +(n ) +. . . + (n ) in Θ ; whence by Theorem 36, a pretheory 1 3 k 0 (n ) (n ) 2 k−1 J : Θ → T is a Θ -theory when it preserves these I -globular sums—that is, 0 0 30 JOHN BOURKE AND RICHARD GARNER op when it is a globular theory in the sense of [8] . A functor F : T → Set is a T -model when it sends I -globular sums to limits, thus when each map X~n −→ Xn × Xn × . . .× Xn 1 3 Xn Xn Xn k 2 4 k−1 is invertible. Once again, Θ is not a saturated class of arities, and so there is no direct characterisation of the Θ -nervous monads; however, their interaction with Θ -theories is important in the literature on globular approaches to higher category theory, as we now outline. Globular theories can describe structures on globular sets such as strict or weak ω-categories and ω-groupoids. For the strict variants, we pointed out in Section 3.2 that these may be modelled by Θ -pretheories; and since reﬂecting a pretheory T into a theory ΦΨT does not change the models, it is immediate that there are Θ -theories modelling these structures too. The original deﬁnition of globular weak ω-category was given by Batanin in [7]; he deﬁnes them be globular sets equipped with algebraic structure controlled by a globular operad. Globular operads can be understood as certain cartesian monads on globular sets. Berger [8] introduced globular theories and described the passage from a globular operad T to a globular theory Θ just as in Section 2.4 above. In our language, his Theorem 1.17 states exactly that each globular operad T is Θ -nervous, so that algebras for the globular operad are the same as models of the associated theory Θ . In particular, Batanin’s weak ω-categories are the models of a globular theory . On the other hand, Grothendieck weak ω-groupoids [27] are, by deﬁnition, models for certain globular theories called coherators. We now proceed to our examples over a more general base for enrichment V . (vi) With V = E a locally ﬁnitely presentable symmetric monoidal category and with A = V , we are in the presheaf context I K // // I V V , wherein I has a density presentation given by the class of all ﬁnite tensors— tensors by ﬁnitely presentable objects of V . Thus by Theorem 36, the V - theories are the pretheories J : V → T which preserve ﬁnite tensors, which are precisely the Lawvere V -theories of [32, Deﬁnition 3.1]. Furthermore, op like in (i), a functor F : T → V is a T -model just when it preserves ﬁnite cotensors, just as in Deﬁnition 3.2 of ibid. On the other hand, V → V exhibits V as the free ﬁltered-colimit completion of V ; whence by Example 41 it is a saturated class of arities, and by Theorem 43 the V -nervous monads are again the ﬁnitary ones. So Theorems 19 and 26 specialise to Theorems 4.3, 3.4 and 4.2 of [32]. The deﬁnition of globular theory in [8] has the extra condition, satisﬁed in most cases, that J be a faithful functor. As an aside, we note that a complete understanding of those globular theories corresponding to globular operads was obtained in Theorem 6.6.8 of [2]. See also Section 3.12 of [9]. MONADS AND THEORIES 31 (vii) Now taking E to be any locally ﬁnitely presentable presentable V -category and A = E , we may argue as in (ii) to recapture the fully general enriched monad–theory correspondence of [31], and its interaction with semantics. (viii) Now suppose we are in the situation of Examples 8(viii), provided with a class Φ of enriched colimit-types satisfying Axiom A of [23]. With E = V and A = V , we are now in the presheaf context I K // // I V V . By [17, Theorem 5.35], I has a density presentation given by Φ-tensors (i.e., tensors by objects in Φ) while by [23, Theorem 3.1], K exhibits V as the free Φ-ﬂat cocompletion of V . Arguing as in the preceding parts, we see op that V -theories are pretheories J : V → T which preserve Φ-tensors, that op T -models are Φ-tensor-preserving functors F : T → V , and that a monad is V -nervous if its underlying endofunctor preserves Φ-ﬂat colimits. This sharpens slightly the results obtained in [23] in the special case E = V . (ix) Finally, in the situation of Examples 8(ix), we ﬁnd that the A-theories are the Φ-colimit preserving pretheories J : A → T ; that the T -models op op are functors F : T → V such that FJ preserves Φ-limits; and that a monad is A-nervous just when it preserves Φ-ﬂat colimits. In this way, our Theorems 19 and 26 reconstruct Theorems 7.6 and 7.7 of [23]. 7. Monads with arities and theories with arities In the introduction, we mentioned the general framework for monad–theory correspondences obtained in [35, 9]. Similar to this paper, the basic setting involves a category E and a small, dense subcategory K : A ,→ E ; given these data, one deﬁnes notions of monad with arities A and theory with arities A, and proves an equivalence between the two that is compatible with semantics. In this section, we compare this framework with ours by comparing the classes of monads and of theories. We will see that our setting yields strictly larger classes of monads and theories which are better-behaved in practically useful ways. On the other hand, in the more restrictive setting of [35, 9], checking that a monad or theory is in the required class may give greater combinatorial insight into the structure which it describes. 7.1. Monads with arities versus nervous monads. In [35, 9] the authors work in the unenriched setting; the introduction to [9] states that the results “should be applicable” also in the enriched one. To ease the comparison to our results, we take it for granted that this is true, and transcribe their framework into the enriched context without further comment. Another diﬀerence is that we assume local presentability of E while [35] assumes only cocompleteness, and [9] not even that. Given a small dense subcategory, there is no readily discernible diﬀerence between cocompleteness and local present- ability ; however, cocompleteness is substantively diﬀerent from nothing, so that Indeed, if there were, then it would negate the large cardinal axiom known as Vopˇ enka’s principle [1, Chapter 6]. 32 JOHN BOURKE AND RICHARD GARNER in this respect [9]’s results are more general than ours. However all known applications are in the context of a locally presentable E , and so we do not lose much in restricting to this context. In conclusion, when we make our comparison we will work in exactly the same general setting as in Section 2.1, and now have: Deﬁnition 45. [35, Deﬁnition 4.1] An endofunctor T : E → E is said to have op arities A if the composite V -functor N T : E → [A ,V ] is the left Kan extension of its own restriction along K . A monad T ∈ Mnd(E ) is a monad with arities A if its underlying endofunctor has arities A. We consider the following way of restating this to be illuminating. Proposition 46. An endofunctor T : E → E has arities A if and only if it sends K -absolute colimits to K -absolute colimits. In particular, each endofunctor with arities A is A-induced. Proof. By Proposition 35, T has arities A just when N T sends K -absolute colimits to colimits. Since N is fully faithful, it reﬂects colimits, and so T has arities A just when T sends K -absolute colimits to colimits which are preserved by N —that is, to K -absolute colimits. For the second claim, recall from Deﬁnition 39 that an endofunctor T : E → E is A-induced if it is the left Kan extension of its own restriction to A, or equivalently, by Proposition 35, when it sends K -absolute colimits to colimits. Recall also that we call a class of arities A saturated when A-induced endo- functors are closed under composition. Example 42 shows that this condition is not always satisﬁed. In light of the preceding result, the endofunctors with arities A can be seen as a natural subclass of the A-induced endofunctors for which composition-closure is always veriﬁed. The reason that Weber introduced monads with arities was in order to prove his nerve theorem [35, Theorem 4.10], which in our language may be restated as: Theorem 47. Monads with arities A are A-nervous. One may reasonably ask whether the classes of monads with arities and A- nervous monads in fact coincide. In many cases, this is true; in particular, in the situation of Example 41, where K : A → E exhibits E as the free Φ-cocompletion of A for some class of colimit-types Φ. Indeed, this condition implies that a monad T is A-nervous precisely when T sends Φ-colimits to Φ-colimits; since Φ-colimits are K -absolute, this in turn implies that N T sends Φ-colimits to colimits, and so is the left Kan extension of its own restriction along K . So in this case, every A-nervous monad has arities A; so in particular, the two notions coincide in each of Examples 8(i), (ii), (iii), (vi), (vii), (viii) and (ix). However, they do not coincide in general. That is, in some instances of our basic setting, there exist monads which are A-nervous but do not have arities A. We give three examples of this. The ﬁrst two arise in the setting of Example 8(iv), and concern the monads for groupoids and involutive graphs respectively. op Proposition 48. The monad T on Grph = [G , Set] whose algebras are groupoids is Δ -nervous but does not have Δ -induced underlying endofunctor. It fol lows 0 0 that T does not have arities Δ . 0 MONADS AND THEORIES 33 Proof. From Example 11 we know that T is Δ -nervous. To see that T is not Δ -induced, consider the graph X with vertices and arrows as to the left in: // [0] [1] r s (7.1) a −→ b ←− c τ s // [1] X . This X is equally the K -absolute pushout right above; so if T were Δ -induced then it would preserve this pushout. But T [1] + T [1] is the graph T [0] −1 −1 r s oo // 1 1 a a // b oo c c 99 dd r s −1 wherein, in particular, there is no edge a → c; while in TX we have s ◦r : a → c. So the pushout is not preserved. This shows that T is not Δ -induced and so, by Proposition 46, that T does not have arities Δ . Since the above result exhibits a Δ -nervous monad whose underlying endo- functor is not Δ -induced, we can apply Theorem 43 to deduce: Corollary 49. K : Δ ,→ Grph is not a saturated class of arities. Our second example, originally due to Melli` es [29, Appendix III], shows that even monads with Δ -induced endofunctor need not have arities Δ . In this 0 0 example, we call a graph s, t : X X involutive if it comes endowed with an 1 0 order-2 automorphism i : X → X reversing source and target, i.e., with si = t 1 1 (and hence also ti = s). op Proposition 50. The monad T on Grph = [G , Set] whose algebras are involutive graphs is Δ -nervous and has Δ -induced underlying endofunctor, but does not 0 0 have arities Δ . Proof. The value of T at s, t : X X is given by hs, ti,ht, si : X +X X . It 1 0 1 1 0 follows that T is cocontinuous and so certainly Δ -induced. To see it does not have arities Δ , consider again the graph (7.1) and its K -absolute pushout presentation. op If this were preserved by N T : Grph → [Δ , Set] then, on evaluating at [2], the maps Grph([2], T [1]) Grph([2], TX ) given by postcomposition with Tr and Ts would be jointly surjective. To show this is not so, consider the map f : [2] → TX picking out the composable pair (r : a → b, i(s) : b → c). Since neither Tr nor Ts are surjective on objects, the bijective-on-objects f cannot factor through either of them. This shows that T does not have arities Δ . Our ﬁnal example shows that not even free monads on A-signatures—which are A-nervous by Theorem 38 above—need necessarily have arities A. Proposition 51. Let V = E = Set and let A be the one-object ful l subcategory on a two-element set. The free monad on the terminal A-signature does not have A-induced underlying endofunctor and therefore does not have arities A. 34 JOHN BOURKE AND RICHARD GARNER Proof. The algebras for the free monad T on the terminal signature are sets equipped with a binary operation. Elements of the free T-algebra on X are binary trees with leaves labelled by elements of X , yielding the formula n+1 TX = C × X n∈N where C is the nth Catalan number. In particular, T contains at least one coproduct summand (–) and so, as in Example 42, is not A-induced; in particular, by Proposition 46, it does not have arities A. 7.2. Theories with arities A versus A-theories. The paper [9] introduced theories with arities A. These are A-pretheories J : A → T for which the composite op [J ,1] Lan op op op (7.2) [A ,V ] −−−→ [T ,V ] −−−−→ [A ,V ] takes K -nerves to K -nerves. This functor takes the representable A(–, x) to T (J –, x), so that in this language, we may describe the A-theories as the prethe- ories for which (7.2) takes each representable to a K -nerve. It follows that: Proposition 52. Theories with arities A are A-theories. Proof. It suﬃces to observe that each representable A(–, x) is a K -nerve since A(–, x) = E (K –, Kx) = N (Kx). Theorem 3.4 of [9] establishes an equivalence between the categories of monads with arities A and of theories with arities A. The functor taking a monad with arities to the corresponding theory with arities is deﬁned in the same way as the Φ of Section 2.4, and so it follows that: Proposition 53. The equivalence of monads with arities A and theories with arities A is a restriction of the equivalence between A-nervous monads and A-theories. In particular, there exist A-theories which are not theories with arities A; it is this statement which was veriﬁed in in [29, Appendix III]. 7.3. Colimits of monads with arities. In Theorem 38 we saw that the A-nervous monads are the closure of the free monads on A-signatures under colimits in Mnd(E ). Since colimits of monads are algebraic, this allows us to give intuitive presentations for A-nervous monads as suitable colimits of frees. The pretheory presentations of Section 3 can be understood as particularly direct descriptions of such colimits. Since not every A-nervous monad has arities A, the monads with arities are not the colimit-closure of the frees on signatures. We already saw one explanation for this in Proposition 51: the free monads on signatures need not have arities. However, this leaves open the possibility that the monads with arities A are the colimit-closure of some smaller class of basic monads—which would allow for the same kind of intuitive presentation as we have for A-nervous monads. The following result shows that even this is not the case. Theorem 54. Monads with arities A need not be closed in Mnd(E ) under colimits. MONADS AND THEORIES 35 Proof. We saw in Proposition 50 that, when E = Grph and A = Δ , the monad T for involutive graphs does not have arities Δ . To prove the result it will therefore suﬃce to exhibit T as a colimit in Mnd(Grph) of a diagram of monads with arities Δ . This diagram will be a coequaliser involving a pair of monads P and Q, whose respective algebras are: • For P: graphs X endowed with a function u : X → X ; 1 0 • For Q: graphs X endowed with an order-2 automorphism i : X → X . 1 1 We construct this coequaliser of monads in terms of the categories of algebras. The category Grph of involutive graphs is an equaliser in CAT as to the left in: E // // ε T Q P // // //// Grph Grph // Grph P // Q T where the functors F and G send a Q-algebra (X, i) to the respective P-algebras (X, si) and (X, t). Since each of these functors commutes with the the forgetful functors to Grph, we have an equaliser of forgetful functors in CAT/Grph. Since op the functor Alg : Mnd(Grph) → CAT/Grph is fully faithful, this equaliser must be the image of a coequaliser diagram in Mnd(Grph) as right above. It remains to show that in this coequaliser presentation both P and Q have arities Δ . By Proposition 35, this means showing that N P and N Q 0 K K send K -absolute colimits to colimits, or equally, that each Grph([n], P –) and Grph([n], Q–) sends K -absolute colimits to colimits. To see this, we calculate P and Q explicitly. On the one hand, the free P-algebra on a graph X is obtained by freely adjoining an element u(f ) to X for each f ∈ X . On the other hand, 0 1 the free Q-algebra on X is obtained by freely adjoining an element i(f ) ∈ X for each f ∈ X . Thus we have PX = X + X · [0] and QX = X + X · [1] 1 1 where we use · to denote copower. Since each [n] ∈ Grph is connected, and since each hom-set Gph([n], [m]) has cardinality max(0, m− n + 1), we conclude that Grph([0], X ) + Grph([1], X ) if n = 0; Grph([n], PX ) = Grph([n], X ) if n > 0. (7.3)  Grph([0], X ) + 2· Grph([1], X ) if n = 0; Grph([n], QX ) = Grph([1], X ) + Grph([1], X ) if n = 1; Grph([n], X ) if n > 1. Now by deﬁnition, N sends K -absolute colimits to colimits, whence also each Grph([n], –) : Grph → Set. The functors with this property are closed under colimits in [Grph, Set], and so (7.3) ensures that each Grph([n], P –) and Grph([n], Q–) sends K -absolute colimits to colimits as desired. It is not even clear to us if the category of monads with arities A is always cocomplete. The argument for local presentability of Mnd (E ) in Theorem 38 does not seem to adapt to the case of monads with arities, and no other obvious argument presents itself. In any case, the preceding result shows that, even if the category of monads with arities does have colimits, they do not always 36 JOHN BOURKE AND RICHARD GARNER coincide with the usual colimits of monads, and, in particular, are not always algebraic. This dashes any hope we might have had of giving a sensible notion of presentation for monads with arities. 8. Deferred proofs 8.1. Identifying the monads. In this section, we complete the proofs of the results deferred from Section 6 above, beginning with Theorem 38. Recall that the category Sig (E ) of signatures is the (ordinary) category V -CAT(obA,E ), and that V : Mnd(E ) → Sig (E ) is the functor sending T to (Ta) . a∈A Proposition 55. V : Mnd(E ) → Sig (E ) has a left adjoint F which takes values in A-nervous monads. Proof. We can decompose V as the composite V V 1 2 Mnd(E ) −−→ V -CAT(E,E ) −−→ Sig (E ) where V takes the underlying endofunctor, and V is given by evaluation at each 1 2 a ∈ obA. Since V is equally given by restriction along obA → A → E , it has a left adjoint F given by pointwise left Kan extension, with the explicit formula: F (Σ) = E (Ka, –)· Σa : E → E , a∈A where · denotes V -enriched copower. So it suﬃces to show that the free monad on each endofunctor F (Σ) exists and is A-nervous. By [16, Theorem 23.2], such a F (Σ) T 2 ∼ free monad T is characterised by the property that E E over E , where on the left we have the V -category of algebras for the mere endofunctor F (Σ). Thus, F (Σ) to complete the proof, it suﬃces by Theorem 6 to exhibit E as isomorphic to the V -category of concrete models of some A-pretheory. op To this end, we let B be the col lage of the V -functor N Σ : obA → [A ,V ]. Thus B is the V -category with object set obA + obA and the following hom- objects, where we write `, r : obA → obB for the two injections: 0 0 0 0 B(`a , `a) = A(a , a) B(ra , ra) = (obA)(a , a) 0 0 0 B(`a , ra) = E (Ka , Σa) B(ra , `a) = 0 . Let ` : A → B and r : obA → B be the two injections into the collage, and now form the pushout J : A → T of h`, ri : A + obA → B along h1, ιi : A + obA → A. Since h`, ri is identity-on-objects, so is J : A → T , and so we have an A-pretheory. F (Σ) 2 ∼ To conclude the proof, it now suﬃces to show that E Mod (T ) over E . By the universal property of the collage and the pushout, to give a functor H : T → X is equally to give a functor F = HJ : A → X together with V -natural transformations α : E (K –, Σa) ⇒ X (F –, Fa) for each a ∈ obA. In particular, op taking X = V and F = E (K –, X ), we see that a concrete T -model structure on X ∈ E is given by an obA-indexed family of V -natural transformations α : E (K –, Σa) ⇒ [E (Ka, X ),E (K –, X )] or equally under transpose, by a family of maps op E (Ka, X ) → [A ,V ](E (K –, Σa),E (K –, X )) . MONADS AND THEORIES 37 By full ﬁdelity of N , the right-hand side above is isomorphic to E (Σa, X ), and so concrete T -model structure on X is equally given by a family of maps E (Ka, X ) → E (Σa, X ). Finally, using the universal properties of copowers and coproducts, this is equivalent to giving a single map α ¯ : E (Ka, X )· Σa → X a∈A exhibiting X as an F (Σ)-algebra. We thus have a bijection over E between F (Σ) objects of E and objects of Mod (T ). A similar analysis shows that a morphism A → E (X, Y ) in V lifts through the monomorphism Mod (T )((X, α), (Y, β)) → E (X, Y ) if and only if it lifts through F (Σ) 2 ¯ the monomorphism E ((X, α ¯), (Y, β)) → E (X, Y ). It follows that we have an F (Σ) 2 ∼ isomorphism of V -categories E = Mod (T ) over E as desired. In proving the rest of Theorem 38, the following lemma will be useful. Lemma 56. Let C ⊆ C be replete, ful l, colimit-closed sub-V -categories of C; for 1 2 example, they could be coreﬂective. If V : C → D has a left adjoint F taking values in C , and the restriction V| : C → D is monadic, then C = C . 1 2 1 2 Proof. Since F takes values in C ⊆ C , the left adjoint to V| : C → D is still 1 2 1 given by F . So monadicity of V| means that each X ∈ C can be written as a coequaliser in C , and hence also in C, of objects in the image of F . Since im F ⊆ C and since C is closed in C under colimits, it follows that X ∈ C . 1 1 1 Theorem 38. V : Mnd(E ) → Sig (E ) has a left adjoint F : Sig (E ) → Mnd(E ) A A taking values in A-nervous monads. Moreover: (i) The restricted functor V : Mnd (E ) → Sig (E ) is monadic; (ii) A monad T ∈ Mnd(E ) is A-nervous if and only if it is a colimit in Mnd(E ) of monads in the image of F ; (iii) Each of Mnd (E ), Preth (E ) and Th (E ) is local ly presentable. A A A op Proof. We begin with (i). Let H : Preth (E ) → V -CAT(obA, [A ,V ]) be the functor sending a pretheory J : A → T to the family of presheaves (T (J−, Ja)) . a∈A Since an A-pretheory is a theory just when each of these presheaves is a K -nerve, we have a pullback square as to the right in: // // Mnd (E ) Th (E ) Preth (E ) A A A V P H (8.1) = op // // V -CAT(obA,E ) V -CAT(obA, K -Ner) V -CAT(obA, [A ,V ]) . N ◦(–) op Since K -Ner ,→ [A ,V ] is replete, this square is a pullback along a discrete isoﬁbration, and so by [14, Corollary 1] also a bipullback. On the other hand, to the left, we have a pseudocommuting square as witnessed by the isomorphisms: T T T (PJ )(A) = A (J –, J A) = E (F K –, F KA) = E (K –, TKA) = N (TKA) . T T T T Since both horizontal edges of this square are equivalences, it is also a bipullback. To show the required monadicity, we must prove that V creates V -absolute coequalisers. Since the large rectangle is a bipullback—as the pasting of two 38 JOHN BOURKE AND RICHARD GARNER bipullbacks—it suﬃces to show that H creates H -absolute coequalizers. As the deﬁnition of H depends only on A and not E , we lose no generality in proving op this if we assume that E = [A ,V ] and K = Y . In this case, every presheaf on A is a K -nerve, and so the horizontal composites in (8.1) are equivalences; and op so, ﬁnally, it suﬃces to prove that V is monadic when E = [A ,V ] and K = Y . Note that, in this case, A is a saturated class of arities: for indeed, by op op the universal property of free cocompletion, a functor F : [A ,V ] → [A ,V ] is A-induced if and only if it is cocontinuous. It thus follows from Proposi- tion 58 below that the restriction V : Mnd (E ) → Sig (E ) of V to cocontinuous c c monads is monadic; so we will be done if Mnd (E ) = Mnd (E ). In this case, c A Ψ : Preth (E ) → Mnd (E ) sends J : A → T to a monad which is isomorphic A A op op op to that induced by the adjunction Lan : [A ,V ] [T ,V ] : [J , 1], and so Mnd (E ) ⊆ Mnd (E ). To obtain equality, we apply Lemma 56. We have that: A c • Mnd (E ) and Mnd (E ) are coreﬂective in Mnd(E ) by Corollary 22 and A c Lemma 57 respectively; • V : Mnd(E ) → Sig (E ) has a left adjoint taking values in Mnd (E ); • The restriction V : Mnd (E ) → Sig (E ) is monadic; c c and so Mnd (E ) = Mnd (E ). This proves monadicity of V in the special case A c op E = [A ,V ], whence also, by the preceding argument, in the general case. In order to prove (ii), we let C be the colimit-closure in Mnd(E ) of the image of F . Since Mnd (E ) contains this image and is colimit-closed, we have C ⊆ Mnd (E ) ⊆ Mnd(E ). Thus, applying Lemma 56 to this triple and 1 A V : Mnd (E ) → Sig (E ) gives Mnd (E ) = C as desired. A A 1 Finally we prove (iii). The monadicity of V above implies that of P and hence op also of H (by taking E = [A ,V ]). Since ﬁltered colimits of A-pretheories can be computed at the level of underlying graphs, the forgetful H preserves them; which is to say that Preth (E ) is ﬁnitarily monadic over the locally presentable op V -CAT(obA, [A ,V ]), whence locally presentable by [13, Satz 10.3]. So in the right-hand and the large bipullback squares in (8.1), the bottom and right sides are right adjoints between locally presentable categories. Since by [10, Theorem 2.18], the 2-category of locally presentable categories and right adjoint functors is closed under bilimits in CAT, we conclude that each Th (E ) and each Mnd (E ) is also locally presentable. 8.2. Saturated classes. We now turn to the deferred proof of Theorem 43. Recall the context: an endo-V -functor F : E → E is called A-induced when the pointwise left Kan extension of its restriction along K , and A is a saturated class of arities if A-induced endofunctors of E are composition-closed. We begin by recording the basic properties of this situation. We write A-End(E ) and A-Mnd(E ) for the full subcategories of End(E ) = V -CAT(E,E ) and Mnd(E ) on, respectively, the A-induced endofunctors, and the monads with A-induced underlying endofunctor. MONADS AND THEORIES 39 Lemma 57. A-End(E ) is coreﬂective in End(E ) = V -CAT(E,E ) via the coreﬂector R(F ) = Lan (FK ), as on the left in: R R oo oo (8.2) A-End(E ) > End(E ) A-Mnd(E ) > Mnd(E ) . // // I I If A is a saturated class, then A-End(E ) is right-closed monoidal, and the core- ﬂection left above lifts to the corresponding categories of monads as on the right. Proof. Restriction and left Kan extension along the fully faithful K exhibits A-End(E ) as equivalent to V -CAT(A,E ), whence locally presentable. Since restriction along K is a coreﬂector of End(E ) into V -CAT(A,E ), it follows that R(F ) = Lan (FK ) is a coreﬂector of End(E ) into A-End(E ). If A is saturated then A-End(E ) is monoidal under composition. Since each endofunctor (–)◦ F of End(E ) is cocontinuous, and A-End(E ) is closed in End(E ) under colimits, each endofunctor (–)◦ F of A-End(E ) is cocontinuous, and so has a right adjoint by local presentability. Thus A-End(E ) is right-closed monoidal. Furthermore, the inclusion of A-End(E ) into End(E ) is strict monoidal, whence by [15, Theorem 1.5] the coreﬂection to the left of (8.2) lifts to a coreﬂection in the 2-category MONCAT of monoidal categories, lax monoidal functors and monoidal transformations. Applying the 2-functor MONCAT(1, –) : MONCAT → CAT yields the coreﬂection to the right of (8.2). The key step towards establishing Theorem 43 above is now: Proposition 58. The left adjoint F of V : Mnd(E ) → Sig (E ) takes values in A-induced monads; furthermore, the restriction of V to A-Mnd(E ) is monadic. Proof. For any T ∈ Mnd(E ), its A-induced coreﬂection ε : IR(T) → T has as underlying map in End(E ) the component Lan (TK ) → T of the counit of the adjunction given by restriction and left Kan extension along K . Since K is fully faithful, the restriction of this map along K is invertible, whence in particular, V ε : V IR ⇒ V : Mnd(E ) → Sig (E ) is invertible. So η : id ⇒ V F factors through V ε : V IRF ⇒ V F whence, by adjointness, id : F ⇒ F factors through ε . Therefore each F (Σ) is a retract of IRF (Σ); since A-Mnd(E ) is closed under colimits in Mnd(E ), it is retract-closed and so each F (Σ) belongs to A-Mnd(E ). It remains to prove that the restriction of V to A-Mnd(E ) is monadic. To do so, we decompose this restriction as V V 1 2 A-Mnd(E ) −−→ A-End(E ) −−→ Sig (E ) , where V forgets the monad structure and V is given by precomposition with 1 2 obA → A → E , and apply the following result, which is [21, Theorem 2]: Theorem. Let M be a right-closed monoidal category, and V : M → N a monadic functor for which there exists a functor : M×N → N with natural isomorphisms X V Y V (X ⊗ Y ). If the forgetful functor V : Mon(M) → M has a left adjoint, then the composite V V : Mon(M) → N is monadic. 2 1 40 JOHN BOURKE AND RICHARD GARNER Indeed, by Lemma 57, A-End(E ) is a right-closed monoidal category, and A-Mnd(E ) the category of monoids therein. Under the equivalence A-End(E ) ' V -CAT(A,E ), we may identify V with precomposition along obA → A. It is thus cocontinuous, and has a left adjoint given by left Kan extension; whence is monadic. Now since V V has a left adjoint and V is monadic, it follows that V 2 1 2 1 also has a left adjoint. Finally, we have a functor : A-End(E )× Sig (E ) → Sig (E ) A A deﬁned by (F, G) 7→ FG, and this clearly has the property that M (FG) = F M (G). So applying the above theorem yields the desired monadicity. We are now ready to prove: Theorem 43. Let A be a saturated class of arities in E . The fol lowing are equivalent properties of a monad T ∈ Mnd(E ): (i) T is A-nervous; (ii) T : E → E is A-induced; (iii) T : E → E preserves Φ-colimits for any density presentation Φ of K . Proof. For (i) ⇔ (ii), the monadicity of V : A-Mnd(E ) → Sig (E ) veriﬁed in the previous proposition implies, as in the proof of Theorem 38(iii), that A-Mnd(E ) is the colimit-closure in Mnd(E ) of the free monads on signatures. Since Mnd (E ) is also this closure, we have Mnd (E ) = A-Mnd(E ) as desired. For (ii) ⇔ (iii), we apply Proposition 35. References [1] Adamek, ´ J., and Rosicky, ´ J. Local ly presentable and accessible categories, vol. 189 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1994. [2] Ara, D. Sur les ∞-groupo¨ ıdes de Grothendieck et une variante ∞-cat´ egorique. PhD thesis, Universit´ e Paris VII, 2010. [3] Ara, D. On the homotopy theory of Grothendieck ∞-groupoids. Journal of Pure and Applied Algebra 217 (2013), 1237–1278. [4] Avery, T. Structure and semantics. PhD thesis, University of Edinburgh, 2017. [5] Barr, M. Coequalizers and free triples. Mathematische Zeitschrift 116 (1970), 307–322. [6] Barr, M., and Wells, C. Toposes, triples and theories, vol. 278 of Grundlehren der Mathematischen Wissenschaften. Springer, 1985. [7] Batanin, M. Monoidal globular categories as a natural environment for the theory of weak n-categories. Advances in Mathematics 136 (1998), 39–103. [8] Berger, C. A cellular nerve for higher categories. Advances in Mathematics 169 (2002), 118–175. [9] Berger, C., Mellies, P.-A., and Weber, M. Monads with arities and their associated theories. Journal of Pure and Applied Algebra 216 (2012), 2029–2048. [10] Bird, G. Limits in 2-categories of local ly-presented categories. PhD thesis, University of Sydney, 1984. [11] Day, B. On closed categories of functors II. In Category Seminar (Sydney, 1972/1973), vol. 420 of Lecture Notes in Mathematics. Springer, 1974, pp. 20–54. [12] Dubuc, E. J. Kan extensions in enriched category theory, vol. 145 of Lecture Notes in Mathematics. Springer, 1970. [13] Gabriel, P., and Ulmer, F. Lokal pr¨ asentierbare Kategorien, vol. 221 of Lecture Notes in Mathematics. Springer, 1971. [14] Joyal, A., and Street, R. Pullbacks equivalent to pseudopullbacks. Cahiers de Topologie et Geom´ etrie Diﬀ´ erentiel le Cat´ egoriques 34 (1993), 153–156. MONADS AND THEORIES 41 [15] Kelly, G. M. Doctrinal adjunction. In Category Seminar (Sydney, 1972/1973), vol. 420 of Lecture Notes in Mathematics. Springer, 1974, pp. 257–280. [16] Kelly, G. M. A uniﬁed treatment of transﬁnite constructions for free algebras, free monoids, colimits, associated sheaves, and so on. Bul letin of the Australian Mathematical Society 22 (1980), 1–83. [17] Kelly, G. M. Basic concepts of enriched category theory, vol. 64 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1982. Republished as: Reprints in Theory and Applications of Categories 10 (2005). [18] Kelly, G. M. Structures deﬁned by ﬁnite limits in the enriched context I. Cahiers de Topologie et Geom´ etrie Diﬀ´ erentiel le Cat´ egoriques 23 (1982), 3–42. [19] Kelly, G. M., and Lack, S. Finite-product-preserving functors, Kan extensions and strongly-ﬁnitary 2-monads. Applied Categorical Structures 1 (1993), 85–94. [20] Kelly, G. M., and Power, A. J. Adjunctions whose counits are coequalizers, and presentations of ﬁnitary enriched monads. Journal of Pure and Applied Algebra 89 (1993), 163–179. [21] Lack, S. On the monadicity of ﬁnitary monads. Journal of Pure and Applied Algebra 140 (1999), 65–73. [22] Lack, S., and Power, J. Gabriel-Ulmer duality and Lawvere theories enriched over a general base. Journal of Functional Programming 19 (2009), 265–286. [23] Lack, S., and Rosicky, J. Notions of Lawvere theory. Applied Categorical Structures 19 (2011), 363–391. [24] Lawvere, F. W. Functorial semantics of algebraic theories. PhD thesis, Columbia Univer- sity, 1963. Also Proc. Nat. Acad. Sci. U.S.A. 50 (1963), 869–872. Republished as: Reprints in Theory and Applications of Categories 5 (2004). [25] Leinster, T. Operads in higher-dimensional category theory. Theory and Applications of Categories 12 (2004), 73–194. [26] Linton, F. E. J. Some aspects of equational categories. In Conference on Categorical Algebra (La Jol la, 1965). Springer, 1966, pp. 84–94. [27] Maltsiniotis, G. Grothendieck ∞-groupoids, and still another deﬁnition of ∞-categories. Unpublished, available as https://arxiv.org/abs/1009.2331, 2010. [28] Markowsky, G. Chain-complete posets and directed sets with applications. Algebra Universalis 6, 1 (1976), 53–68. [29] Mellies, ` P.-A. Segal condition meets computational eﬀects. In 25th Annual IEEE Sym- posium on Logic in Computer Science LICS 2010. IEEE Computer Society Press, 2010, pp. 150–159. [30] Meyer, J.-P. Induced functors on categories of algebras. Mathematische Zeitschrift 142 (1975), 1–14. [31] Nishizawa, K., and Power, J. Lawvere theories enriched over a general base. Journal of Pure and Applied Algebra 213 (2009), 377–386. [32] Power, J. Enriched Lawvere theories. Theory and Applications of Categories 6 (1999), 83–93. [33] Segal, G. Classifying spaces and spectral sequences. Institut des Hautes Etudes Scienti- ﬁques. Publications Math´ ematiques 34 (1968), 105–112. [34] Street, R. The petit topos of globular sets. Journal of Pure and Applied Algebra 154 (2000), 299–315. [35] Weber, M. Familial 2-functors and parametric right adjoints. Theory and Applications of Categories 18 (2007), 665–732. Department of Mathematics and Statistics, Masaryk University, Kotla ´rsk ˇ a ´ 2, Brno 61137, Czech Republic E-mail address: bourkej@math.muni.cz Department of Mathematics, Macquarie University, NSW 2109, Australia E-mail address: richard.garner@mq.edu.au

http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Mathematics arXiv (Cornell University)

http://www.deepdyve.com/lp/arxiv-cornell-university/monads-and-theories-3YgGWQ3WBn

Monads and theories

Loading next page...

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

ISSN: 0001-8708
eISSN: ARCH-3343
DOI: 10.1016/j.aim.2019.05.016
Publisher site: See Article on Publisher Site

Abstract

Journal

Mathematics – arXiv (Cornell University)

Published: May 11, 2018

References

Locally Presentable and Accessible Categories

Adámek

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Monads and theories

Monads and theories

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Monads and theories

Monads and theories

References

Abstract

Journal

Recommended Articles

References

Our policy towards the use of cookies