M O N A D L I K ES T R U C T U R E S IN 2 C A T E G O R I E S AND S O F TA D J U N C T I O N S By PETER STONE B.A., Cambridge University, 1965 M . S c , Memorial University of Newfoundland, 1973 A THESIS SUBMITTED IN P A R T I A L F U L F I L M E N T OF THE REQUIREMENTS FOR THE D E G R E E OF DOCTOR OF PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES (Mathematics) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH C O L U M B I A October 1989 © Peter Stone, 1989 In presenting degree freely this at the thesis in partial University of British available for reference and copying of department publication this or of thesis by this for his thesis or her The University of British Vancouver, Canada Date DE-6 (2/88) 1 2 * . Gdk- study. I further Columbia purposes the requirements gain agree that may representatives. for financial of of Columbia, I agree that scholarly permission. Department fulfilment shall be It not the be Library permission granted is for by the an advanced shall make it for extensive head understood that allowed without of my copying or my written (ii) Abstract One of the fundamental concepts of ordinary category theory is that of an adjunction. There are analogous notions in 2-category theory one of which is the "soft adjunction" of this thesis. In order to construct examples which exhibit the full generality of this phenomena two constructions for modifying soft adjunctions are described: an "attaching procedure" and a "lifting procedure". These two procedures are shown to be inverses of each other in an suitable sense. A special type of "commutative monad" structure on an object of a 2-category is described and it is shown that this structure can be modelled by the category of finite ordinals and all functions in the same way that the ordinary monad structure can be modelled by the category of finite ordinals and non-decreasing functions. By a standard argument for such a situation where there are 2-category objects with structure a certain "strict" adjunction" is obtained; that is, an adjunction which is essentially the same as an adjunction in ordinary category theory. Starting with a slightly extended version of this strict adjunction examples of soft adjunctions are obtained by means of the attaching and lifting procedures. The relationship between the the various soft adjunctions which arise is investigated. (iii) Contents Abstract (") Acknowledgements ( ) Introduction i v 1 I . Soft A d j u n c t i o n s H.2-Monads m. The Lifting Construction ° 4 7 107 I V . Commutative Monads 175 V . Composite M o n a d s 230 V I . T h e L i f t e d Q u a s i - A dj u n c t i o n s 291 V I I . T h e k , m Soft A d j u n c t i o n s a n d t h e i r L i f t i n g s 372 Bibliography 422 (iv) Acknowledgements I would like to thank my supervisor John MacDonald for his advice and encouragement during the preparation of this thesis. I am indebted to Art Stone for pointing out therichstructure which can arise from a soft adjunction. The idea of what I have called the lifting construction is due to him and comprises the first, or inductive step, in the possible construction of an "inner tower" for a soft adjunction. The formulation of the coequalizer hypothesis and the details of the lifting construction in the form I have given it constitute original work as does the theory connected with commutative monads and their application to provide the examples of soft adjunctions and liftings. 1 Introduction The notion of a category arose as an abstraction of the idea of a mathematical system consisting of mathematical objects such as groups or topological spaces together with mappings between these objects which preserve the structure in a suitable sense, for example, group homomorphisms in the case of groups and continuous functions in the case of groups or topological spaces respectively. Attention is then centred on the properties of the mappings or "morphisms" which for the abstract notion of a category can be pictured as arrows between the objects of the category which, in turn, are simply regarded points. There is an associative composition rule for the morphisms and an identity morphism for each object which serves as a unit element with respect to composition. The method of algebraic topology is to attempt to transfer problems in the category of topological spaces (with a specified base point) and homotopy classes of continuous mappings to a more amenable problem in an algebraic category of some kind such as the category of groups, graded groups or R-modules. The translation process involves a mapping between categories or "functor" such as the fundamental group functor or (co)homology functors. In general, a functor between two categories is an assignment of an object of the second category to each object of thefirstcategory together with an assignment of a morphism of the second category to each morphism of thefirstcategory such that composition and identities are preserved. In the case of cohomology the direction of the arrows is reversed, giving examples of "contravariant" functors. They can be regarded as genuine functors via the notion opposite category obtained by reversing the arrows in a given category. Taking categories as objects and functors as morphisms and using the evident composition rule for functors, we obtain a category Cat. In order to avoid the usual logical contradictions we could suppose that the categories involved are "small" in the sense that their sets of objects and morphisms are elements of somefixed"universe" 2 [CWM; 1,6]. Thefirstachievement of category theory was to give a framework for describing the phenomena of naturality. Thus a basic notion in category theory is that of a natural transformation between two "parallel" functors; that is, two functors going between the same pair of categories. Thus cohomology operations are examples of natural transformations and the canonical mapping from a vector space to its double dual is a natural transformation from the identity functor on the category of vector spaces over a given field to the double dual functor. In these examples the natural transformation between the two functors consists of a family of morphisms in the image category of the two functors the "action" of which commutes with the action of the images under the two functors of any morphism in the source category. The general notion of a natural transformation is obtained by framing this commutativity condition in abstract terms [CWM; 1,4]. Natural transformations may be regarded as a second kind of arrow going between the functors which are the "ordinary" arrows in the category Cat. This leads to the concept of a 2-category which, in the abstract, is a system obtained by introducing a second kind of arrow between the original arrows of the underlying category for which two composition rules are specified: vertical and horizontal composition [CWM; 11,5]. The original objects are now the objects or 0-cells of the 2-category while the first and second types of arrows are respectively the 1-cells and 2-cells of the 2-category. The study of 2-categories is now a well-establishedfieldwith the motivation comingfromapplications to (higher) homotopy theory and recent incentives in the direction of theoretical computer science. In 2-category theory one is led to consider the notion of a (strict)2-functor between two 2-categories as an obvious generalisation of the concept of a functor. One of the main problems in thefieldof 2-categories is that offindinga "good" way to translate the basic (l-)category notion of an adjunction involving ordinary functors to the context of 2-categories and 2-functors. There is an obvious generalisation in the "strict" sense in which commutativity conditions for morphisms in the 1-category definition are transferred directly to commutativity conditions for both 1-cells and 2-cells. However this does not take account of the full richness of the structure in a 2-category which allows for the possibility of replacing strict commutativity conditions by relaxed notions in which the requirements for diagrams to commute "on the nose" are replaced by the presence of 2-cells in the 3 relevant diagrams. J.W.Gray described a variety of notions of adjunction for 2-categories in [ADL]. The "soft adjunctions"of this thesis are Gray's adjunctions weak quasi adjunctions. More recently, B Jay considered local in the context of bicategories [LAD] of which soft adjunctions are a special case. His local adjunctions are a generalisation of a concept considered by M. Bunge [ERA]. Possible lines of investigation which could provide evidence of the likelihood of a particular notion of adjunction for 2-categories being "useful" are as follows: (i) Check whether such an adjunction has equivalent formulations analogous to those for an adjunction in 1-category theory; namely a description using hom-sets, a description by means of a suitable kind of universal property and an equational description. (ii) Look for non-degenerate instances of the phenomena which arise "naturally". (iii) Investigate whether certain standard results involving adjunctions in 1-category theory such as those relating adjunctions to monads and properties with respect to limit preservation have appropriate analogues in the new context JX. MacDonald and A. Stone have investigated soft adjunctions with respect to thefirstpoint of view [SAD], while this thesis is concerned with the second point of view. The third point of view is the subject of some on-going work by J.L.MacDonalcL Art Stone and the author. The main part of the thesis is concerned with constructions on (strict) 2-monads.In 1-category theory the notion of a monad provides aframeworkfor the description of certain categories whose objects are "sets with structure" as algebras for an appropriate monad [CWM; VTJ. In the context of 2-categories 2-monads arise in situations where one considers the possibility of adding some "algebraic like" structure to the objects of a 2- category so that these "objects with structure" can be regarded as algebras for an appropriate 2-monad. The 2-monads discussed in this thesis are of a particularly simple kind in which the endo-2-functor of the 2-monad has the form "tensor with D" where D is a strict monoidal category. 2-monads and tensor products (a particular kind of indexed colimit) are dealt with in chapter II. Three particular choices for D are considered throughout the thesis: the simplicial category, which is the category offiniteordinals and non-decreasing functions, the 4 category of finite ordinals and all functions and a quotient category of the category of finite ordinals obtained by identifying all the morphisms in each hom-set to a single morphism. These three categories model respectively monad, commutative monad and idempotent monad structures on an object of a 2-category as algebras for the corresponding 2-monad. The combinatorial investigations involving the category of finite ordinals in relation to commutative monads are considered in chapter IV. When a commutative monad structure is given on an object of a 2-category, for each k>l one can define a "k-fold composite monad" for which the endo-l-cell is the k-fold composite t of the endo-l-cell t of the k original monad. Generalising the standard results connecting monads with adjunctions via the category of Eilenberg-Moore algebras to the context of 2-categories by introducing "Eilenberg-Moore objects" as a particular type of lax limit [FTM], it is shown in chapter V that, for a given commutative monad, there is an adjunction between any pair of Eilenberg-Moore objects associated with the k-fold and m-fold composite monads, where l<k<m. Certain commutativity relationships between these adjunctions are also derived. These constructions are then particularised to the generic commutative monad defined on the modelling category; that is, the category of finite ordinals. Instances of soft adjunctions occur involving various 2-functors going between a suitable base 2-category such as Cat and a 2-category having commutative monads in the base category as objects. In particular, for each k>l there is a 2-functor from the second 2-categorytothe first whose value at a commutative monad is the Eilenberg-Moore object for the associated k-fold composite monad. Chapters VI and VII contain the relevant constructions making use of two procedures for modifying soft adjunctions which are described in chapters I and Ul, namely an "attaching procedure" and a "lifting procedure", the ideas for which are due to Art Stone. In chapter n i it is shown that these processes are inverses of each other in a suitable sense. The basis for the attaching construction is the notion of a "natural adjunction" (or natural family of adjunctions) between a pair of 2-functors. In the applications of the attaching procedure in chapters VI and VII the natural adjunctions involved are derived from adjunctions constructed in chapter V. The lifting construction can be applied to a soft adjunction when a suitable "coequalizer hypothesis" is satifisfied. Since the construction is roughly analogous to 5 Beck's construction of an adjoint for the comparison functor for monads this is perhaps not too surprising. A large part of the technical details of chapter VI are concerned with verifying the coequalizer hypothesis for the particular soft adjunction under consideration. The main result of chapter VI is that the k-fold Eilenberg-Moore 2-functor has a quasi-left-adjoint. A quasiadjunction is a special type of soft adjunction in which certain "natural" 2-cells or "modifications" arising in the description of a soft adjunction, namely the "vertical unit" and" vertical counit" of the soft adjunction, are isomorhisms. The soft adjunctions in chapter VII give a clear demonstration of the non-uniqueness of soft left adjoints and softrightadjoints since .for example, if l<k<m, each m-fold Eilenberg-Moore 2-functor is shown to have the constructed quasi-left-adjoint for the k-fold Eilenberg-Moore 2-functor as a soft left adjoint. In the final result of chapter VII non-uniqueness also arises in the context of the (horizontal) unit and counit for a given quasi adjoint pair of 2-functors, namely the quasi-adjoint pair mentioned above. As afinalremark concerning regarding the treatment of soft adjunctions here, I should point out that, for the sake of simplicity and to make the thesis as self-contained as possible, I have made use of only an equational description of a soft adjunction and not used either the hom-set description or the description involving soft universal properties which appear in [SAD]. 6 I. Soft Adjunctions 2-Categories In order to investigate the (external) algebraic properties of such notions in category theory as those of adjunctions and monads, one is led to the concept of a 2-category which axiomatizes the algebraic structure of Cat, the category of all small categories, when natural transformations are also included. An ordinary category (1-category) consists of two kinds of entities: objects and morphisms, where each morphism can be thought of as an arrow between two objects. Then the operation of composition (g,f) i > g°f is a "partially defined" (that is, not everywhere defined) binary operation on the morphisms which gives the composite morphism g°f for a pair of morphisms ( f ,g) such that the domain (or source) of g is the same as the codomain (or target) of f. A 2-category consists of three kinds of entities: objects or 0-cells (for example, the categories in Cat), morphisms or 1-cells (for example, the functors in Cat ) and 2-cells (for example, the natural transformations in Cat). A 2-cell is a second kind of arrow <f :f > g going between two 2-cell f and g with the same domain A and codomain B. f g Thus the 2-cell <p has the domain f and codomain g . There are two composition rules for 2-cells. In Cat the vertical composition of two natural transformations is defined "pointwise" in the target category. This gives a composition rule which can be pictured as follows. Horizontal composition of natural transformations can be pictured as follows, f f V of C g H g' (HRZ) 9'° 9 The domain and codomain of <p'°<p are given by the usual composition of functors while <p'°<f is defined to be the natural transformation whose value at an object a of the category A is the morphism of C given by the diagonal of the square gf a S'f a g'f a g' <f a g? a gf'a g'f a a which commutes by naturality of <f>'. If we dispense, temporarily, with 1-cells by regarding them as identity 2-cells, we can give the following description of a 2-category. A 2-category A is a category in which each hom-set A( A ,B) is itself a category, such that for all objects A ,B ,C the composition rule A(B,C) x A(A.B) (*f>',f) *• A(A,C) I is a bifunctor, that is, a functor of two variables. This is the > horizontal f ' o f composition which can be pictured as in diagram (HRZ). The category composition within each hom-set category A( A ,B) gives the composition, vertical which can be pictured as in diagram (VRT). Both composition rules are required to be associative, as indeed they are in Cat, and since horizontal composition is a bifunctor, in the situation 8 we have the interchange law > B of a general 2-category A, there is an identity 2-cell For each 1-cell f: A f f which acts as a two-sided identity for vertical composition. For each 0-cell A there is an identity 1-cell 1A:A > A, and hence an identity 2-cell lA which acts as a two-sided identity for horizontal composition. For the sake of simplicity, and to avoid foundational problems, we shall assume that the hom-sets A( A ,B) are small categories. If we denote by A ( A ,B) the set of objects of the category A( A ,B), the sets 0 A ( A ,B) are the hom-sets of a category A whose objects are the 0-cells of A and whose morphisms are the 0 0 1- cells of A. The composition A (B,C)x A (A,B)i 0 0 > A (A,C) 0 coincides with the horizontal composition on identity 2-cells. Note that we have previously abused this notation by writing Cat for both the 2-category of all small categories, which includes natural transformations as 2- cells, and also for the category Cat . 0 In the context of enriched category theory a 2-category theory is just a Cat-category, where (abusing notation again) we assume that Cat has the evident structure as a cartesian closed 9 category. If we use the previously mentioned identification of 1-cells with identity 2-cells, the diagram f represents the 2-cell is ^'otp = . If D Then, by the interchange law, the 2-cell g°ip°f. (g'<xp) a (<p'of) = f f 9 g' (<f'°g) o (f'otp). Where there is no danger of confusion we shall denote horizontal composition by juxtaposition — vp'oip = ip'*p. In the preceding diagrams we have represented 2-cells by "double arrows" ; however, sometimes we shall find it convenient to depict vertical composition by diagrams of the form T f • Q where we are regarding 2-cells as morphisms in a hom-set category A( A ,B) and so are representing them by "single arrows". A 2-functor F : A > X between 2-categories A and X preserves identities and both composition rules. In detail, F consists of a functor F : A 0 0 > X for which each function A ( A ,B) 0 0 given by the restriction of F extends to a functor 0 F A > B :A(A,B) > X(FA.FB) such that the horizontal composition is still preserved; that is, the diagram » X (FA,FB) 0 10 •* A(B,C) x A (A,B) F A(A,C) ^A,C B, C x A, B F X(FA,FC) X(FB. FC) x X(FA, FB) commutes for all objects A ,B ,C of A. For example, for each object A of A we have the hom-set 2-functor A( A, _ ) : A 1 -cell g:B > C, A(A,g) = g*:A(A,B) > Cat. For a » A( A, C) is the functor given by g*(f)= g°^p and for a 2-cell g we have a natural transformation A(A,oc) = a : g* * g'* given by oc*( f) = oc°f: g°f » g'°f. We can have 2-functors which change the direction or variance of 1-cells and/or 2-cells. These can be brought under the previous description by considering appropriate "opposite" 2-categories where we change the "direction" of either 1-cells or 2-cells or both. We omit the details. For example, the hom-set 2-functor A( _ , A ) : A not the 2-cells. For a 1-cell g: B g*(ip) = <pog > C, A( g,A) - g*:A( CA) and for a 2-cell oc :g A(ot,A)= ot*:g* Let F ,6: A • Cat reverses the direction of the 1-cells but > g' between 1-cells g,g':B > (g' )* is given by oc*(f) = f°oc: f°g > A( B ,A) is the functor given by » C the natural transformation > f°g'. > X be two 2-functors. A para-natural transformation <P : F family of 1-cells of X cpA: FA * GA indexed by the objects A of A, together with a family of 2-cells cpf cpB°Ff : indexed by the 1-cells f:A » Gf°cpA > B of A as depicted in the diagram > G consists of a Gf Ff FB •* GB cpB such that the following conditions are satisfied. (PN1) »f is a 2-cell of A between 1-cells f,f :A Ifoc:f > B , then cpf o(cpBocpA) = (Goc° cpA) • cpf, that is, cpA FA FA Ff Gf cpf FB GB <PB cp( 1A) = * I D : A FA 'FA cpf FB > * A cpA • GA *(1) A = id FA 'GA GA cpA (PN3) Given 1-cells f:A -» B andg:B > C in A, (Gg° cpf) o (cpg o Ff) = cp(gof), that is, <PA Gf Ff (PN2) GA cpB <PA FA F(g of ) GA G(g cp ( g o f ) FC of ) GC cpC By reversing the direction of the 2-cells in this definition we obtain the notion of an allo-natural We shall be concerned mainly with para-natural transformations so we omit the definition. transformation. The terminology here is differentfromthat used in most of the literature where the prefixes lax, op-lax, quasi and op-quasi have been used. If cp f is the identity 2-cell for each 1 -cell f: A » B of A, we say that cp is a Stated more simply, a strictly natural transformation cp : F transformation. 1-cells cpA: FA strictly natural » G consists of a family of » GA, indexed by the objects of A, such that cpA FA •* GB for each 2-cell oc : f Let cp F : F ,G ,H: A » f' of A between 1 -cells f,f': A > G and 0: G > X. Then the composite > B. » H be para-natural transformations between 2-functors para-natural transformation 0 ocp: F > H is defined on objects of A in terms of horizontal composition of 1-cells in X by (0 °cp )A = 0A o cpA. For a 1-cell f: A > B in A, the 2-cell (0 °cp )f is defined to be the "pasting composite" 2-cell Ff Gf FB GB <PB 0f 0B Hf HB It is easy to see that 0 °cp satisfies the three conditions (PN1), (PN2) and (PN3). We shall usually retain the symbol " °" for this composition of para-natural transformations since we reserve juxtaposition for a different operation described later. (See lemma 1.) Let F ,G: A modification a: cp > X be two 2-functors and let cp, 0 : F • 0 consists of a family of 2-cells aA: cpA such that for each lrcell f: A » G be two para-natural transformations. A » 0A, indexed by the objects of A, » B of A Operations of horizontal and vertical composition of modifications can be defined in the obvious way. Thus, given 2-functors F ,G: A > X, para-natural transformations and modifications, as shown in the diagram cp 14 a o b: cp > r is defined by ( a • b)A = aA • bA. Given 2-functors F ,G ,H: A > X, para-natural transformations and modifications as shown in the diagram a' o a : cp' o cp <P cp' 0 0' > 0' o 0 is defined by ( a ' ° a)A = a'A ° aA. The interchange law a ' o a = (0 o ) • ( a ' o cp) = ( a o 0) o (cp 1 1 8 1 o ) a holds. By analogy with the situation for functors and natural transformations in Cat, if we are given a strictly natural transformation cp H : » H' between the 2-functors H and H' together with 2-functors F and G as shown in the diagram H B cp rf we can define a strictly natural transformation GcpF :GHF object of A. More generally, if cp : H > GH'F by (GcpF)A = G( cp( FA)) where A is an » H' is a para-natural transformation, we can extend this definition to obtain a para-natural transformation GcpF :GHF > GH'F where, for a 1-cell f :A——* B of A, (GcpF)f = G( cp( Ff)). We shall usually omit the parentheses in such an expression. Thus Gcp Ff is the 2-cell pictured in the diagram GHFA GHFf GHFB Gcp FA GH' FA GH Ff 1 G* Ff GH' FB Gcp FB 15 Given 2-functors and para-natural transformations F F' the diagram of para-natural transformations F'F *'F G' F F'cp G'cp F'G (p'G G'G does not necessarily commute, although it does if cp is strictly natural. Indeed, evaluating at an object A of A, 1 we have a 2-cell cp' cpA in the diagram F' FA F'cpA cp'FA cp'cpA F'GA G' FA G'cpA G'GA cp'GA Proposition 1 In the situation above cp 'dp cp 'G ° F'cp : Proof: For each object A of A, > G'cp o cp'F is a modification. 16 17 G' FA G'cp A cp'FA F' FA G'GA G' Ff cp'Ff F' Ff G'cpf G' FB cp' FB F' FB G'cp B fcp'cpB F'cpB G' Gf G'GB cp'GB F'GB • Monads and Adjunctions in 2-Categories A Ti: 1 monad (B ,t , T i , u ) in a 2-category A consists of an object B of A, a 1-cell t: B >t,u:t 2 • B and 2-cells »t such that u • tTi = u o nt = id (Ml) (unit law), that is, the diagram tri Tit commutes, and (M2) that is, the diagram u «tu = u«ut = id (associativity), 18 commutes. An adjunction » A in a 2-category (f ,u ,r\,e): B A, also denoted by f B u Ti consists of objects B ,A of A, 1-cells f: B € > B and 2-cells T\ : > A, u: A -» uf, » 1 such that €:fu u€ • Tiu = id and €f • f r \ = id, that is, the diagrams uf u f Uf U€ €f commute. Given two adjunctions (f ,u ,T\,€) : B adjunction (t ,u ,T\ ,&°):b n D D > A and (f ,u' ,T\' ,€') :A > A', there is a composite > A' with f° = ff, u = uu', Tp = uT\'f » riand€ = €' •feu'. D D The two notions of monad and adjunction described above generalize the standard ones in Cat. Exactly as is the case in Cat, an adjunction (f ,u ,T\,€): B » A gives rise to a monad (B ,t,Ti,u) with t = uf and u =uef. Let (B ,t,Ti,u) be a monad in a 2-category A. A A of A, a 1-cell v: A > B and a 2-cell 5: tv i-algebra (A,v,|) fortius monad consists of an object > v such that 19 and = id | • T\V % • uv = % that is, the diagrams We shall often omit the 0-cell from the notation so that, for example, the above t-algebra may be written as (v , | ) . In the diagrammatic representation we go one step futher and simply represent a t-algebra by the diagram for its 2-cell, so that, for example, the above t-algebra will be represented by the diagram 20 B . A fork in a category D is a diagram oc P in D, such that the morphisms ex ,p and Y satisfy the relation Ycx = Yp. A split has a splitting fork is a fork, as above, which given by two morphisms a « b * c such that Y<? = 1 , oc^ = 1 and <p Y = p\|; [CWM, chapter VTJ. For such a split fork, Y is the coequalizer of ct and p. Indeed, if we are given a morphism % : b such that foe = gp, let 5 = g<p: c • d » d , then £Y = g<f>Y = gp+ = f oc^ = g. Furthermore, 5 is unique with the property 5Y = 5, since if g = S'Y for some S' :C • d, then S = g<f = S'Yy = We note that (A ,v,g) is a t-algebra for the monad (B ,t ,T\ ,u) in a 2-category A if and only if uv tv t V 2 5 is a split fork in the hom-set category A( B ,B), split by t2 Tit V V TiV tV This follows because the conditions for (A ,v ,g) to be a t-algebra are exactly the relations g e T\V = id. and g • uv = | »tg, while the relations uv °Titv = id and try « g = tg •T\tv hold in any case. Given two t-algebras (v ,g) and (v' ,g') with the same oc: (v,g) > ( V ) is a 2-cell cx: v domain A, a > v' such that the diagram morphism of {-algebras 21 commutes, that is The t-algebras with domain A form a category Alg(A ,t). We can extend Alg( - ,t) to a 2-functor A (which reverses the direction of 1-cells but not 2-cells) as follows. Given a 1-cell g: A' functor Alg(g.t) :Alg(A,t) -» Cat > A, we have a » Alg(A'.t), whose value at an object (v,|) of Alg(A.t) is the t-algebra B A' B The functor A lg(g,t) is defined in the obvious way on morphisms. Given a 2-cell tp :g 1-cells g,g':A' > A, we have a natural transformation Alg(f ,t) :Alg(g,t) »Alg(g',t) whose value at an object (v ,|) of Alg(A.t) is the morphism of t-algebras in A1g(A' ,t) g > g' between An Eilenberg-Moore object for a monad (B ,t ,T\,U ) in a 2-category A is an object B of A such that there is an isomorphism of categories Alg(A.t) = A(A,B), which is natural in A. be the t-algebra which corresponds to the identity on B. Then we have the following universal property, (i) Given a t-algebra (A ,v ,|), there is a unique 1-cell w: A w' > B such that v' As usual, such an object B, if it exists, is unique up to natural isomorphism. Hence we shall refer to "the" Eilenberg-Moore object for a monad (B ,t ,TI ,u). If Eilenberg-Moore objects exist in a 2-category A for each monad (B ,t ,T\ ,U ) in A, we say that A has Eilenberg-Moore objects. An Eilenberg-Moore object is a particular instance of the notion of a lax limit, which, in turn, is a type of indexed limit [2CL]. To obtain B as a lax limit we need to interpret a monad as a 2-diagram, which can be done using the result of proposition II.2. 23 For a monad (B ,t ,r\,u) in Cat, we can take B to be the associated category of Eilenberg-Moore algebras (or t-algebras) in the category B described as follows [CWM, chapter VI]. An object of B is a t-algebra (b ,h) in the category B, which consists of an object b of B together with an algebra structure map h which is a morphism h: tb » b such that the diagrams commute. A morphism of t-algebras f: (b ,h) » (b' ,h') is a morphism f: b > b' of t such that the diagram tb U * b tf b' tb' h' commutes. Such a t-algebra in can be interpreted as a t-algebra in the sense described previously with domain E, the category with a single object. b^ B t B Let u: B 5: tu > B be the evident forgetful functor which forgets the t-algebra structure and let > u be the natural transformation whose value at an (b ,h) object of B is the structure map 5(b) = h: tb > b. Thus 5 is a "global" algebra structure map. Then is a t-algebra in Cat in the general or "global" sense. Suppose B is a t-algebra in Cat. Then for each object a of A, w(a) = (v(a),j-(a)) is a t-algebra in the category B and for each morphism g: a » a'of A, w(g) = v(g):(v(a),i-(a)) > (v(a'),|(a')) is a morphism of t-algebras, which follows since the diagram 1(a) tv(a). tv(g) v(a) v(g) tv(a') 5(a') v(a') commutes by the naturality of g. In this way we obtain a unique functor w :A 6 such that B w This verifies the 1-cell universal property. The 2-cell part of the universal property is easily checked. An alternative way to establish this result, once B has been described as a lax limit, is to use the general 25 construction of lax limits in Cat [A2CJ. We can now generalize the standard result in Cat that "every monad arises from an adjunction", provided that we assume that the appropriate Eilenberg-Moore objects exist in our 2-category A. Thus, for each monad (B ,t ,T\,u) in A, we obtain an adjunction B B T\ u € with uf = t and u€f = u. The details are as follows. From the monad properties it follows that (B ,t ,u) is a t-algebra. Hence there is a unique 1-cell » B such that f: B B B B B Now (tu.uu) is a t-algebra, and it follows from the fact that(u,5) is a t-algebra that 5 : (tu,uu) > (u X) is a morphism of t-algebras. Hence, using the 2-cell universal property of B, there is a unique 2-cell € :fu » 1 such that J» B fu B 1 B t B Proposition 2 f B Proof: U6 • T\U = c B is an adjunction in A . 26 Given two monads (B ,t,ri,u) and (B'.t' ,1V ,u') in A, a morphism of monads (h,oc):(B,t,n,u) consists of a 1-cell h: B > B' and a 2-cell a : t'h » (B'.t'.n'.U') > ht such that 27 If oc = id, we call (h ,<x) a strict morphism of monads and denote it simply by h:(B,t,T M) ll » (B'.t'.Tt'.M'). There is a 2-category Mon( A) whose objects are the monads in A and with 1-cells given by the morphisms of monads. A 2-cell <p:(h, oc.) is a 2-cell <f: h > (g,|3) between 1-cells (h,oc),(g,p):(B,t,ri,u) » g of A such that h > (B ,t' ,tY ,u') 1 28 Horizontal and vertical composition in Mon( A) are defined in the obvious way using the horizontal and vertical composition in A. Restricting to strict morphisms for 1-cells, without changing the 2-cells, gives a sub-2-category Mon§( A) of Mon( A). Now suppose that an Eilenberg-Moore object 8 exists in A for each monad (B ,t ,T\,u) in A. We show that the assignment (B ,t ,T\,u) i > B on objects extends to a 2-functor >A. V:Mon(A) Let (h.oc): (B .t.ii.u) > (B' ,t' ,T\' ,u') be a morphism of monads and let B and B' be chosen Eilenberg-Moore objects corresponding to the monads (B ,t ,Ti,u) and (B' ,t' ,r\' ,u ) respectively, with 1 associated universal t and t' -algebras ( B ,u,5) and ( B',u' ,5'). Then we have an induced 1-cell V ( h, oc) = ( M x ) : B * B' which is the unique 1-cell such that B' (h, a) B' This makes sense because the right hand diagram represents a t'-algebra. Given a 2-cell <p: (h ,cc) > (g, |3•) between morphisms of monads (h ,cx),(g, 0): (B ,t ,r\,u) — — » (B' ,t' ,T\' ,U ' ) , we have an induced 2-cell V(<p) = <p: Y( h,oc) > V(g,(3) which is the unique 2-cell such that (Mx) B' -* B' (g,P) This makes sense because the right hand 2-cell is clearly a morphism of t'-algebras. These constructions evidently define a 2-functor V: Mon( A ) > A which we call the Eilenberg-Moore 2-functor associated with the 2-category Mon( A ) . We are involved here essentially with the functorial properties of lax limits. S o f tA d j u n c t i o n sa n dt h eA t t a c h i n gP r o c e d u r e Let X and A be 2-categories and let F: A » X and U: X > A be 2-functors. A para-soft adjunction (F,U,T) ,£ , r , s ) between F and U (where F is a para-soft left adjoint of U and U is a para-soft right adjoint of F) consists of the following data. A horizontal unit T) and a horizontal counit £, which are respectively para-natural transformations T): 1 ^ > UF and £ : FU vertical counit s which are respectively modifications r : 1 y Hence, evaluating r at an object X of X , we have a 2-cell T|UX UX * UFUX and evaluating s at an object A of A , we have a 2-cell FA FT) A • The following modification equations are required to hold. * FUFA > 1 x- A vertical unit r and a • U £ ° U T) and s : £ F ° F T) • 1 p. 30 (i) (Us°T|)«(UEFoT|T|)o ( F°T|) = id, (ii) ( E ° s U ) * ( E e o F T | U ) * ( e ° F r ) = id; r that is, the composite modifications given by the following diagrams are the identity 2-cells on T): 1 and E : FU > UF » 1 respectively. When r and s are invertible, that is, modifications whose value at each object are 2-cell isomorphisms, which includes the special case when they are identities, the adjunction is called a (para-) If, furthermore, T) and £ are both strictly natural transformations, then we have a strict quasi-adjunction. adjunction. Such an adjunction is a Cat-adjunction in the sense of enriched category theory. By requiring T) and £ to be allo-natural transformations instead of para-natural transformations, and changing the direction of the vertical unit and counit, we obtain the notion of an allo-soft adjunction. However, we shall be concerned here exclusively with para-soft adjunctions. Let F, F: A » X be two 2-functors. A para-natural consists of a para-natural transformation cp F : adjunction (cp, v ,h ,e): F > F, a stricdy natural transformation V: F > F > F and 31 modifications h : 1 -> vcb, e r c p v - (cpA,VA,hA,eA):FA -* 1 such that evaluating at any object A of A gives an adjunction > FA. Now suppose that we are given a para-soft adjunction (F ,U, T], £ ,r ,s) between the 2-functor F and a 2-functor U: X » A together with a para-natural adjunction (cp, V, h ,e): F > F. The situation is indicated schematically by the following diagram. cf U With this setup we have the following attaching procedure which constructs a new para-soft adjunction ( F ,u, t|, £ ,f,S) between F and u. This procedure will enable us to construct examples of soft adjunctions by attaching to a strict or quasi adjunction. We now give the details of the construction. Let T|: 1 > U F be the para-natural transformation given by the composition 1 and let £ : F U - -* 1 be the para-natural transformation given by the composition vu FU Let r: 1 UF UF ... e FU 1 > U £ ° UT) be the modification given by the diagram T|U UcpU UVU 32 35 UF U* UF The other modification equation can be checked in a similar way. If ( c p , v D D ,h ,e ): F D D • • F is another para-natural adjunction, then we can attach again to the D 2-functor F to obtain a para-soft adjunction (F ,U,T) ,E ,r ,8 ). It is straightforward to check that this D D D n n soft adjunction can be obtained from the original soft adjunction (F ,U ,T) ,£ ,r,s) by means of a single attaching using the "composite" para-natural adjunction ( t p t p , V V , n a V h cp • h , e • < p e v ) : F D D D D >F . D We shall make use of another type of attaching, which, in an appropriate sense, could no doubt be regarded as a dual of the previous construction. Let (F ,U ,T) ,£ ,r,s) be a para-soft adjunction where F: A » X and U : X (<p,V,h,e): U > A are 2-functors. Suppose that there is a para-natural adjunction * U,whereU:X schematically by the following diagram. > A is a 2-functor, so that we have the situation indicated 36 A T) V and let s : EF ° F T) > 1 be the modification given b y the diagram 37 By arguments similar to those used for proposition 1 we obtain: Proposition 4 (F, U, T), £, r,8) is a para-soft adjunction. • Some constructions involving monads leading to a soft adjunction We have seen that, as long as the 2-category A has Eilenberg-Moore objects, there is an Eilenberg-Moore 2-functor V: Mon( A) > A given on objects by V( B ,t ,T\,U ) = B. There is also an evident "forgetful" 2-functor V: Mon( A) > A defined on objects by V( B ,t ,r\ ,u) = B and in the obvious way on 1-cells and 2-cells. For each monad (B ,t ,T\ , u) we have the canonical adjunction f B B 1 c T\ U € of lemma 2. We show that these adjunctions give rise to a para-natural adjunction (cp, V ,h ,e): V Define cp :Y » V and V: V respectively. Let (h,oc): (B ,t,Ti,u) > Y on objects by setting cp(B .t.ti.u) = f and V( B ,t,Ti,u) = u > (B' ,t',T\' ,u') be a morphism of monads. Then the diagram » V. 38 V (h, oO V(B,t,n, U) * VCB'.t'.n'.M') v(B,t,Tu u) vCBw.n'.u') V(B,t,Tb M) VCB'.t'.n'.M') V(h, a) commutes, smce it is (h, oO where the canonical adjunction for the monad ( B' ,t' ,Ti' ,u') is f B' B' Tl Thus w e see V: V €' > V that is strictly natural. T o describe cp as a para-natural transformation w e need to define cp (h, a ) , where (h,a):(B,t,ri,u) V(B.t,Tt u) <P(B.t,Tu p) V(B,t,U lO be the 2-cell U' » (B ,t' .ir ,p') is a morphism o f monads. Thus w e let 1 1 Y(h, oc) YCB'.t'.n'.M') cpCB'.t'.n'.M') cp (h, oc) •* V(B ,t ,n .M ) , V (h, a) , , l 39 B 1 h • B' • B f B : •B l • B' (h, a) 1 It is straightforward to check that this makes cp into a para-natural transformation, cp (h ,cx) has the following alternative description. Lemma 5 Let (h,oc) :(B ,t,T\,u) (i) • (B' ,V ,T\' ,u') be a morphism of monads. Then oc is a morphism of V -algebras from s, B' h f . X BCQQf: 40 Now let h( B ,t,Ti,u) = Hand e(B,t,T\,u)= €. Then it is easy to check, using either of the preceding descriptions of cp on 1-cells, that h and e are modifications. Thus (cp, v , h , e ) : V > Y is a para-natural adjunction. Let F : A • Mon( A) be the 2-functor which assigns to each object A of A the trivial monad 0 (A, 1 A ,id,id), extended in the obvious way to 1-cells and 2-cells. We can take the object A for the EilenbergMoore object YFQA, but also VFQA = A .whence (cpFoA.VFoA.hFgA.eFoA ):YF A 0 » VF A 0 is the trivial adjunction 1 A ' ( id A 1 For a monad ( B .t.tl.u), F V ( B ,t,Ti,u) = ( B , 1 ,id,id). There is a strictly natural transformation 0 £:F Y 0 > 1 where £( B ,t,ri,p) iFoWB.t.Ti.u) by ( u , 5 ) : ( B , 1 ,id ,id) > (B ,t > (B.t.Ti.u) is the morphism of monads given ). (Saying that ( u ,5) is a morphism of monads is the same as saying that ( B ,u,5) is a t-algebra.) If (h,cx):(B .t.Ti.M) > (B'.t'.Ti' ,u') is a morphism of monads, the 41 diagram eCB.t.Tuu) F V(B,t,Ti, M) • (B.t.Ti. u) 0 (h, a) F V(h, a) 0 FnVCB'.t'.TV.M') (B'.t'.n'.M') E(B',t',Ty,u') commutes, since (h, a) B • B' 5' u' Lemma 6 F o A Mon(A) J T) = 1 V £ is a strict adjunction. Proof: ^ 0 = F A 1 F A 0 : F 0 V F 0 A * 0 F A and ve(B,t,Ti,p.) = 1 g : YF V(B .t.n.M) 0 » Y(B,t,n,M). • We can now apply the attaching procedure using the para-natural adjunction (tp, V ,h ,e): V construct a para-soft adjunction ( F ,V, T| , E ,r ,s). 0 0 0 0 0 > V to 42 Mon(A) l f| = CP V > VF is the identity natural transformation, since it is the composition The horizontal unit T ) : 1 0 0 1 VF„ VF„ of two identities. The horizontal counit £ : F V 0 0 > 1 is given as follows. For a monad (B ,t,Ti,u), £ ( B ,t,T\,u) is the composition 0 FoVCB.t.u u) F cp(B,t,n, M) 0 »• FoVCB.t.n, u) E(B,UP) *• (B.t.n, p) which is (B, 1 , id, id) (B , 1g , id,id) B (u,5) (B.t.n p) or (B, 1 B> id, id) U,u) (B.t.Tb u) This is the morphism of monads depicted by the diagram For a morphism of monads (h.oc): (B ,t ,T\,M ) > (B' ,t',iY ,p'), E ( h,oc) is the 2-cell between 0 morphisms of monads e (B,t,Tb M ) 0 F V(B,t,n, u) • (B.t.UM) 0 F V(h, oc) (h, oc) 0 £ (h, oc) n FoVCB'.t'.Ti'.M') (B'.t'.n'.M') B' The vertical unit r :1 0 > V E °T) V. 0 0 For a monad (B.t.Ti.u), T)oV(B,t,U u) VCB.t.ri, u) • VF V(B,t,u M) 0 Ye (B,t,Ti, u) 0 V(B,t,n, u) B | Ti B We can check directly that ( F , V , T | , E , r , 8 ) is a para-soft adjunction by verifying the two 0 0 0 0 0 modification equations. The first modification equation is trivial while the second one follows because F V(B,t.Tu u) 0 (B.t.Ti. M) 47 II. 2-Monads Strict Monoidal Categories and the Simplicial Category A strict monoidal category (D, +, 0) is a (small) category D together with a bifunctor 'p = ••+•• : [)xD >D which is associative, that is, the diagram v px 1 •D*D lx p v D*D D commutes, and with an object 0 which is both a left and right unit for "+", that is, 0+ | = T = 5+0 for each morphism gofD. A strict monoidal category (D, +, 0) can be regarded, in an obvious way, as a 2-category D_with a single object, or 1-cell 0. Let (D, + , 0) and (D', +', 0') be two strict monoidal categories. A (D,+,0) functor strict monoidal • (D', + *, 0') is a functor which preserves the monoidal structure, thatis, $ (0)=0 ' and $(f+5~) = $( T) + ( T) foreach pair of morphisms Tand Tof -Such a monoidal D functor can be identified with a corresponding 2-functor D_ * D_' between the corresponding 2-categories. In the following all monoidal functors should be interpreted as being strict A monoid (c, T\, U ) in a strict monoidal category (D, +, 0) is an object c of D together with two morphisms T[: 0 c=0+c• » c and u: c+c T\+C • C+C » c such that the diagrams C+ T[ c+0=c C+C+C C+ (J u +c C+C 48 commute. Regarding the strict monoidal category (D, + , 0) as a 2-category D_with a single object, a monoid (C,TI,U) in (D,+,0) is the same as a monad structure on the single object of 0. Conversely, a monad (B ,t ,r\,u) in a 2-category A is a monoid in A( B ,B) where this hom-set is regarded as a strict monoidal category in the obvious way. We consider the simplicial category A as described in [CWM]. The results obtained are, for the most part, well-known, but the treatment here is slightly different from the standard treatment so as tofitin more readily with subsequent ideas. The category A has as objects thefiniteordinal numbers 0,1, . .., n where for n>l, n={0,1,...,n-1) and the morphisms are all non-decreasing (monotonic) functions % : n ? ( j ) . Ordinal addition on the objects of A extends to a is, functions 5 such that 0<i<j<n bifunctor "+": A x A |+5 : m+n > n'; that > A . For two morphisms g : m » m' and £ :n » n' of A > m'+n' is given by <I+?) (i) = [ T<i> if 0<i<m, .m'+ 5 if m<i<m+n. We can represent an object n of A pictorially by a collection of n points labelled 0,1, . ., n-1 equally spaced in a vertical line and then a morphism between two objects can be pictured as a mapping from left to right given by a family of arrows or lines, such as is shown for the following example of a morphism 3 > 3. 2: -.2 The ordinal sum of two morphisms can be obtained pictorially by placing their arrow diagrams one above the other in the appropriate order. It is clear from this that ( A ,+, 0) is a strict monoidal category. 0 is an initial object in A and 1 is a terminal object, so we have unique morphisms T\ : 0 Hence the morphism pictured above is Tt+ u+1. > 1 and u : 2 > 1. 49 The diagrams u+l i+n T\+l l+M commute because 1 is a terminal object; that is, we have the relations Urn+i) = TT(I+T\) = 1 (Ai) 11(7+1) = (Fd+H) (A2) Hence (1, T\, u) is a monad in A . The relations (A 1) and (A2) can be represented pictorially; for example, (A 2) is given pictorially as follows. 2 2 : If- ^--^ = o• lj o' 0 For k>0,let u <> :k -» 1 denote the unique morphism, which can be pictured as follows if k k>l. Thus u ( 0 ) = Ti, u formula u ( u + l ) (k) ( 1 ) = = 1, u = u, u ( 2 ) u(l+u (k> ) = p ( 3 ) ( k + 1 ) = u(u+l) = TJ(l+u) and we have the recursion . An arbitrary morphism | :m » n of A can be expressed in the form T = TT 0> (n, +"p l + (m ) +p"<n-l>, m where rrij^ is the number of elements in the subset (J)" (i) of m f o r i = 0 , l , . . , n - l and 1 1:10+1^+.... + m _ n 1 = m. This shows that the morphisms of A are generated by 1, T\ and u under"+" and 50 composition. Since 1 is a terminal object in A , we have the formula +7j(k )) 7J(n) ]J(k ) 7J(k ) ( 1 + 2 = n + lT< l k + K 2 + +k n> which is the "general associative law". Suppose ( B ,t ,ri,|j) is a monad in a 2-category A. For n>0, define u < : t n) u<0> - Ti:1 follows: - * t recursively as n >t uU> = 1 :t ——* t u<> - u:t 2 • t 2 u<«> = u • u '"M :t n Proposition u (n) 2 1 General associative Law for a monad o o (k > o U o (k ))= 2 U n M (k +k + 1 for + k> 2 n n>l. (GAL) Proof: The case n=l is trivial so we start by considering the case n=2. We must show that «(u( i) o (k ))= k u M 2 u (A) (k!+k ) 2 for any kj_, k , which we do by induction on k . For k =0 we have 2 2 u 2 •(p(k ) o ( k ) ) = 1 U 2 P( < l) o n ) k u U as required. t For k =l we have u • ( M I ou(k ))= (1C 2 ) 2 Assume that (A) holds for k - l where k 2 2 >2. u »y(ki>t _ Then u » (u u o (k +l) u ° u < 2>) = K 1 > as required. = U< l 2>. k + k Having dealt with the case n=2 we now prove the general result by induction on n. Assume that the formula (GAL) holds for n-1 where n>3. Then u <> • (p < i> o (k ) o n k u 2 o (k )) = M n k-,+ J (k M 1 + +k -i n .... + k _ ) n 1 by the inductive hypothesis. = u (k!+lc2+ +k ) by n j m e case =2, which we have already proved. n Proposition 2 Lef be (B ,t ,ri,u) a monad in a 2-category A. Then fAiere /s a un/'gue monoidal functor $:A suchthat$(l) = t, $("ri) = nand$(IT) = u. > A(B,B) 53 Proof: For an object n of A , where n>l, we set $ (n) = $(y(m)) = u (m) p o r a g e n e r a l morphism % :m n > n of A , express | in the form ]T o + Tr i + (m ) I= (m ) o where m.^ is the number of elements in the subset (m ( J ) 1^+11^+ = t and for each m>0, we set = m- Then set $ (F) = u - 1 +ll< n-l) rn (i) of m for i = 0 , 1 , . . , n-1 and > °u< i> ° <>|i ("Vi-l >. This is clearly the only m possible way to define $, if $ is to be a monoidal functor. We must check that $ now has the required properties for a monoidal functor. It follows immediately from the definition that $(T T) = $(T)°$(?) (B) + for a pair of morphisms | : m » n'of A . We must also check that > m' and 5 : n <K?°D = #(?)•$(!) for any two morphisms f: m > n and 5 : n for the special case % = u <i>-t-u < 2> +.. . . k $(?°T> k > k of A . In view of (B) it suffices to check this +u n>, S~ = (k = <K7T<> o(^T(k ) TJ(k ) = $(]I( l 2 = U< l 2 k k + k +k + + + 2 + k +k n In this case +7(k >)) n 1 ]T< >. + n n>) n>) = p (n) e (u (kj.) o (k ) u 2 <>(i < >) by the general associative law k 0 n for the monad ( B , t ,TI , u ) , = $(lT< >) n ocH7J<k ) 7J(k > 1 + 2 + +7 n>) (Jc = $(?)•$(?). A general composition 5 ° | can be expressed as a sum 5iFi + where 5 = ^ + + 5p> l = = Ii + + + 5pF p ? and each summand has the form just considered. Hence p t^TiJ-^Ti)] 0 °[*(Ip)»$(F )] p 54 = [*(?i)o = *(Ti+ °$(5p)] • [ $ ( T i ) « » . . . . . * ( T ) ] o p + ? )°*(Fi+ + T ) p p = <KT) •$(£). • We shall often omit $fromthe notation and, for a morphism f : m $ (T) = ? : t » m ' of A , write • t ', simply taking off the "bar". This is consistent with the notation used already in m m connection with the special morphisms r\ and p. Note that the 2-cell in A(B,B) corresponding to T+n:m+n > m'+n is 4>(f+n) = | t : t n+|":n+m n »t ' m + n > n+m' is$(n+f) = t g : t n m >• t n + m + n n+m while that corresponding to '. Corollary 2 Given a monoid (c.Tt.ij) in a strict monoidal category (D,+ ,0), there is a unique monoida functor$:( A , + ,0) > (D,+ ,0) such that$( l) = c, <Kn) U ano* $(7T) = M= : Proof: This result followsfromproposition 2 by regarding (D,+,0) as a 2-category with a single object. • Lemma 4 A morphism g:m > n of A has a unique factorization f= where IQ-.TR h > s issurjectiveand |j:s o fc > n isinjective. Proof: This is just the standard factorization of set theory. Let s be the (ordinal) number of elements in the image of % and let | j : s » n be the unique order-preserving injection with the same image as ?. Since | j is an order-preserving bijection between s and the image of | , there is a unique surjection $Q : M that |j ° %Q = £. This factorization is clearly unique. * S SUCN • 55 We call ?c m e surjective part of g and f j the injective part of g. We call a morphism of the form p~= h+IT +m:h+k+m > h+m+1, <k) where k>2 and h, m>0, an elementary collapsing morphism. The top of p is 1( p)=h+k-l and the bottom of p" is <B( ~p) =h. We can picture an elementary collapsing morphism schematically by a diagram of the following form, in which the "wedge-shaped" shaded region is understood to contain k arrows which converge to a single point, and the lower and upper blank regions are understood to contain h and m parallel arrows respectively. h+k+m-1 h+m T(p)=h+k-l 8(p)-h Lemma 5 For any (non-identity) collapsing morphism g:n' — — » n elementary collapsing morphisms p ..., p lf J = P" ° where r^n such that °Pi r andl(pj )< r of A there are unique «(pj)for j = l , . . . , r - l . + 1 Proof: Express f in the form | = p 0> + p< l> +....+ p n - i >, where k > l for each i . Then we have (k k ( k i |" = (]J(k ) + -l)(k +TJ< l> +n-2)(k +k +p"< l) +n-3) k 0 n 0 k 0 1 (k + Q +k _ +lT< n-l>). k n 1 Omitting any factors which are identities, we obtain a factorization of the required form. Because of the condition l ( p j + 1 ) < ®(Pj), each factor Pj is associated with the collapsing of points in the domain n ' t o a single point of the codomain n. This gives the uniqueness. • The factorization of lemma 5 can be pictured by the following schematic diagram. P2 Pi Pr-l Pr We call a morphism of the form P"(n, j) = j+TT+n-j-l:n+l » n, where n>l and 0< j<n-l, a primary collapsing morphism. Lemma 6 Any (non-identity) collapsing morphism g:n' F = p"(n, j ) o p » n of A has a unique factorization o p~(n'-l, j ) x as a composition of primary collapsing morphisms, where p=n' - n and n ' - l > j > . . . . > j >0. 1 Pioof: Obtain the unique factorization of lemma 6 and then use the formula 7<k> = "p(i+TD(2+7) (k-2+H) to decompose each elementary factor into a composition of primary collapsing morphisms. p 57 We call a morphism of the form S(n,i) = i+Ti+n-i:n > n+1, where n>0 and 0<i<n, a primary injection. L e m m a7 Any (non-identity) injection f: n ' > n of A has a unique factorization f = S"(n-l,i ) o q o S"(n' as a composition of primary injections, where q=n • - n and 0 < i < . . . . <i <n. 1 q Proof: 5 is determined completely by its image in n. Let i be the elements of n , taken in q increasing order, which are not in the image of £. This gives the factorization of the lemma. Let £: m • » n be a morphism of A with collapsing part |rj and injective part Ij. Factoring f~ by c lemma 6 and gj by lemma 7 gives a canonical factorization of g as a composition of primary morphisms. If we refer to a general morphism of the form \T= h+IT(>+m:h+k+m k » h+m+1 where k>0, k*l and h,m>0, as an elementary morphism of A , factoring | c by lemma 5 and |j by lemma 7 gives a canonical factorization of f, 5 P p-1 1' as a composition of elementary morphisms. We now list a number of relations involving the primary morphisms of A . They fall into two main types: those derived from the relations (A 1) and (A2) involving T\ and u where the actions of the components "interfere" with each other in an essential way - we call these relations essential, and those which arise from the monoidal structure of - we call these relations non-essential. 58 Essential relations f o r the p r i m a r y m o r p h i s m s o f A (h+TT+k)(h+l+Tl+k)= h+k+1 (h+Tr+k)(h+T\+l+k)= h+k+1 (API) (h+U +k)(h+U +l+k) = (h+U +k)(h+l+U +k) (AP2) We add h on the left and k on the right in each factor occurring in the relations ( A 1) and (A 2). Non-essential relations f o r the p r i m a r y m o r p h i s m s o f A We give these relations in a simplified form. The general form can be obtained by adding h on the left and k on therightin each of the factors. Each of the relations in this simplified form gives two equivalent expressions for a morphism of the form f+s-1+5 where s>l and f , 5 are chosen from T[ and p. Hence they can be obtained from the general formula l+s-1+5 = (m'+s-l+?)( |+s-l+n)= for two morphisms £: m (g+s-l+n•)(m+s-l+5) ' of A . •» m , 5 :n 1 (s+r )(n+s-l)= (r +s)(s-l+T ) (PA 3) (s+u)( u+s+l) = (u+s)(s+l+u) (PA4) (S+Tl)(u+S-1) = ( P+S)(s + 1+Tl) (PA 5) (-n+s)(s-i+u)= (PA 6) l l l (s+u)(-n+s+i) The last relation is illustrated pictorially below, where thistimethe shading is a substitute for drawing s-1 parallel lines. 59 Using the notation for primary morphisms given above, namely p(n,j) = j+u+n-j-1 and 5 (n, j) = j + T\+n- j , the relations (PA 1) to (PA6), in general form, are equivalent to the following (more familiar) relations. 6~(n+l,i)8"(n, j) = S"(n+1, j+1) 8"(n, i ) , i<j, p~(n, j)p~(n+l,i) = p"(n,i)p"(n+l, j+1) , i<j, p(n,j)S"(n,i) = i<j, [ S"(n-l,i)p~(n-l, j - 1 ) , n, i=j,i=j+l, . 8"(n-l,i-l)p~(n-l, j ) , i>j+l. Proposition 8 The category A fe generated under composition by the primary morphisms subject to th relations (PAl)to(PA6). Proof: These relations suffice to put any composite of primary morphisms into canonical form. • Note that we are ignoring the monoidal structure of A in proposition 8; the relations (PA3) to (PA6) allow for algebraic manipulations which could otherwise be performed by using the monoidal structure. Tensor Products Let A be an object of a 2-category A and let D be a small category. A tensor product D®A of D with A is an object of A for which there is an isomorphism of categories A( D®A,B) = Cat( D, A(A,B)), which is natural in B. Let apj > A(A ,D®A) be the unique functor which corresponds to the identity 1-cell on D®A. Then we have the following universal property. (i) Given a functor f:D » A(A ,B), there is a unique 1-cell f:D®A > B such that the diagram 60 U A (A, D®A) »»A(A,B) commutes, where f„ = A(A,f). (ii) Given a natural transformation oc:f 2-cell a: f — » A(A ,B), there is a unique > f between functors f ,f':D » f (where f and f are obtained as in (i)) such that V where oc„ = A(A,oc). A functor f:D — morphism f~: 7J » A(A ,B) gives for each object u of D, a 1-cell f(U) :A » v"of D, a 2-cell f("|~) :f( IT) gives for each object u of D, a 1-cell crp /\( u) : A a 2-cell crp ( f ) : A ^ ( u~) > CD,A^> > f( v~). In particular, CTQ^.D » B and for each » A(A,D®A) > D®A and for each morphism f : u 11131 The univesal property of D® A can now be restated as follows. » Vof D, 61 (i) Given a functor f:D •B > A(A,B), there is a unique 1-cell f:D®A such that (a) for each object u of D the diagram f D® A »• B Of course (b) really makes (a) redundant (ii) Given a natural transformation oc:f 2-cell oc:f > f between functors f ,f':D » A(A ,B), there is a unique » f (where f and f are obtained as in (i)) such that, for each object u of D, f(u) f f f(u) Where there is no danger of confusion we shall write cr = <TQ . When a tensor product D® A exists in a A 2-category A for each pair of objects D e Cat and A e A, we say that A has tensor products. If D® A exists for each A e A and for some fixed small category D, we say that A has tensor products with D. For example, the usual category product gives a tensor product in Cat. For an object u of D, dp (ID : A A > D*A is the inclusion functor or sectional u given by crp ( u~)( <p) = ( u , <p)where <p is a morphism of A. It can be A shown that the 2-category Mon( A) has tensor products when A has tensor products. 62 We now show that if A has tensor products and a choice of tensor product is made for each pair of objects D e Cat and Ae A, then the assignment on objects (D ,A)i variables Cat x A > D®A extends to a 2-functor of two » A (that is, simply a 2-functor, if we give the obvious description of Cat * A as a product 2-category). First we show that for each small category D, D® -: A > A is a 2-functor. Suppose g:A is a 1-cell of A. Then we have the functor 0"r 'D,B D , *A g A (A, D ® B) (B, D® B ) where g* = A( g ,D® B). Hence, by the universal property of D®A, there is a unique 1-cell a * > v of D > D®B such that for each morphism £ : u D®g: D®A D,A (17) Jl DA F a a D,A ( D®A D® g D® B (v) B Given a 2-cell a: g • g between 1-cells g, g': A 1 D,B A (B, D ® B ) Hence there is a unique 2-cell D®oc : D®g • D®A |i D®a D®g' % <-V D ® B B » B of A, we have a natural transformation I oc* A (A, D ® B ) » D®g' such that for each object u of D D® g A | D®B > B This clearly makes D® - : A > A into a 2-functor. Now we show that for each object A of A, -®A : Cat > A is a 2-functor. Suppose f:D • -> E is a functor between small categories D and E. Then we have a functor cr r D• E,A A (A, E® A) Hence, by the universal property of D®A, there is a unique 1-cell f®A: D®A morphism £ : u a A D,A > E®A such that for each > v of D ( 7 ) H ^DJ^ f®A D®A E® A E,A a a D,A ( v ) f ( u ) E® A E,A ff Given a natural transformation ^: f > f between functors f, f : D f(v) > E , we have a natural transformation E,A Hence there is a unique 2-cell <p®A : f®A A (A, E® A) » f'®A such that for each object u of D 64 f ®A f® A ^E,A | a lf EA *E,A This makes -®A : Cat f(u) ' (u) E 0 A f ( u ) > A into a 2-functor. In order for tensor product to be a functor of two variables, we need the two families of one variable 2-functors D® -: A 1-cell g.A * A and - ®A : Cat > B in A and a functor f-.D > A to be compatible in a suitable sense. Firstly, given a » E the diagram D® g E® g D® B must commute. For each morphism of g: u E® B f®B » vofD, the horizontal composition of both (E®g)( f® A) and (f®B)(D®g) with W 11 a is the 2-cell 7 ) %JV D,A ( v ) D® A ff f(u) EB E®B a f(v) £>B Hence( E®g)( f®A) = (f® B)( D®g) by the uniqueness part of the universal property associated with E® B. This means that f® g is "well-defined" as either of these compositions and gives the diagonal of the preceding square. We also need a compatibility condition involving the 2-cells of A and Cat. Let oc: g 2-cell between 1-cells g, g': A functors f, f : D > f be a natural transformation between > B of A and let <p: f » E. Then we require that E® g f® A D®A > g' be a J[ ¥ ® A E®A J | E®oc E®B E®g' f ®A f ®B D® g D® A E® B D®g' f ®B For each object u of D, the horizontal composition of both of these 2-cells with ap (If) : A A a f(u) g J | 9 > D®A is a B J| ^FR P(U) W < E®B ( u ) Hence, again by uniqueness, the preceding two 2-cells are equal and give a well-defined value for if ® oc. 66 It may now be checked that tensor product is indeed a 2-functor Cat * A A as claimed. However, since from the point of view of working with the tensor product, the important point is that <p® cx is well defined in the sense described, we omit any further details. In the following we shall write D® oc = 1 ®oc and <p®A = <f ® 1. The tensor product is a particular instance of an indexed colimit [2CL]. The functor CJQ ^ or its image in A( A ,D®A) constitutes the "universal co-cone". Let D and E be small categories and suppose that the 2-category has A tensor products. Then we have isomorphisms of categories (natural in B): A(D®(E®A),B) = Cat(D,A(E®A,B)) £ Cat( D ,Cat( E,A( A,B))) = Cat(D*E,A(A,B)) = A((DxE)®A),B). Thus we have an isomorphism in A, D®( E®A) = (D*E)®A. We compare the 1-cell universal properties of these two objects of A. The universal co-cone of (D *E)® A consists of 2-cells (u', V) indexed by pairs of morphisms £ : u functor f:D><E * u', 5 : v •* v' of D and E respectively. Suppose given a * A(A,B). On the one hand there is a unique 1-cell f :(D E)®A X * B such that 67 a A DXE,A U V ) Jl °"DXE,A ' (? a 5} DxE,A ' ' (u V (° X E )® - A f ( u , v) } f( for each pair of morphisms g : u » u' , 5 : v > IP , 5~ : V A(A,B). For each morphism | : u ff/T): V) > v' of D and E respectively. On the other hand there is a unique functor fg : D morphisms f": u" U', » Cat( E, A( A,B)) such that, for each pair of > v of D and E respectively, fo(?)(¥) = f(T. T ) as 2-cells in 5 > u' of D we have a natural transformation * foCu ) between functors f (TD ,f ( u ): E 1 1 0 0 > A(A,B). Hence there is a unique 2-cell f TTD 0 E® A I fTf) B 0 such that f ( u , v) J]i(5,5) f ( u , V) 1 for each morphism 5 : v » v' of E. This defines a functor A(E®A, B) f 7p -» so there is a unique 1-cell f : D ® (E®A) D D, E ® A U E® A * B such that for each morphism g : u > u' ( 1 J ) J, D, E ® A^F) D®(E®A)- a ff 0 -*B D, E ® A ( ^ ) E® A » B is the unique 1-cell such that Thus f : D®( E®A) 11 D, E ® A A | E,A a ( ? ) E ® A Jl °"D, E®A<F> a a E,A ( v l ) D, E ® A<'> D®(E®A) u f( u,v) f(u',v') for each pair of morphisms g : u > u' , 5 . v » v' of D and E respectively. The 2-cell universal properties can also be compared to show that under the isomorphism D ® ( E ® A ) s (D*E)®A, the 2-cell 69 A A E,A ( V ) l E^ A a a E/ v ( 5 , ) ) E ® A D, E®A ( u ) Jl D,E®A^ a a D®(E®A) D, E ® A< '> U in the universal co-cone of D® (E®A) corresponds to the 2-cell °"DXE,A( u",v) A Jl DxE,A(F,5) a (DxE)®A 0- xE,A^',V) D in the universal co-cone of (D*E )®A. One can now show that the isomorphism D®( E®A) = (D*E)®A is natural in A in the sense that for any 2-cell ex.: g » g' in A 1®g D®(E®A)= (DXE)®A J,1®rx (DXE)®B 1 ® g' 1 ®( 1 ®g) D®(E®A) J,1 ® ( 1 ® cx ) D ® ( E ® B) = (DxE)®B 1 ® ( 1 ®g' ) 70 2 M o n a d sa n dA l g e b r a s A (strict) 2-monad ( T ,T| ,J1) defined on a 2-category A consists of an endo-2-functor T : A strictly natural transformations T): 1 > T , Ji: T 2 > A and > T such that the following diagrams of strictly natural transformations commute.[2DM] T We shall be concerned with 2-monads for which the endo-2-functor T : A » A has the form T = D® - where (D, +, 0) is a strict monoidal category. The details are given in the following proposition. P r o p o s i t i o n9 Let (D, +, 0) be a strict monoidal category and let A be a 2-category with tensor produc Let T = D®-: A- > A and let T|: 1 ->T,J1:T 2 > T be the strictly natural transformations given by T]A = cr (0): A DA > D®A v |IA:D®(D®A)= (DxD)®A p ® - 1 •—• D ® A where p is the functor of two variables given by the monoidal addition. v Then ( T , T), Ji) is a strict 2-monad. Proof: First we show that the diagram 71 • TA TA 2 commutes for each object A of A. NotethatTT|A: TA | :u > T A is 1 ® a 2 D A (0) :D®A- D® ( D®A). For each morphism > u' of D we have VA ( T 7 ) l®a VA ( U ' D A D®A J l ^ D A ^ A (0) : »-D®(D®A) °D A z£ "p ® 1 *• D ® A } °D, D ® A A (Dx D)®A ( 0 ) f •D ®A ii | D,D®A ^ 0 ( °D,D®A V A ( U ) D > A ( D i A * D®(D®A)= (DxD)®A "D ® 1 u , ) (u,0) IVoA^ V ) 5 (u',o) (DxD)®A 'p ® •D ® A *D®A 72 Hence the diagram 1 D® A ®°D,A ( 0 ) D ® (D® A) 112 (DxD)®A 'p ® 1 D® A commutes by the uniqueness part of the universal property of D®A. We now show that the diagram T|TA TA •TA 2 commutes. First note thatT)TA :TA • T A is CX D®A > 2 : D ® A * D®( D®A). For each morphism > u' of D we have | : u VA ( U ) D, D ® A J A (0 D) | D,A a ( ? ) D®A. % D A ( 0 ) V »>D®(D®A)=s (DxD)®A P ® 1 (0,u) Jl V D A ^ ' ^ V D , A (0 ,U') (DXD)®A *D®A *• D ® A 73 VA ( U ) VA ( U ' } Hence, by uniqueness, the diagram D® A °D, D ® A • ( 0 ) • D®(D®A) 112 (DxD)®A 'p ® D® A commutes. Lastly we show that the diagram TUA JJTA commutes. Note that T JiA is 1® (-p® 1 ) D®(D®(D®A))= Let | : u » u' , 5 : v D®((DxD)®A) > v' and V : w »-D®(D®A) » w' be morphisms of D. Then 74 Jl ° D , A A ( V ) D® A | ° " D . D® A<5) D ® ( D ® A) | °" , D ® (D® A)<D D 1 ® ( p® 1 ) v s D ® ((D x D)® A) Jl ° " A DxD p®| v »• D ® (D® A) £ ( D x D ) ® A A (5.v) (DxD)®A Jt , a D (DxD)®A(F) D®(D®(D®A)) *• D ® A D®((DxD)®A) etc. = A Jl ° D x D , A ( ? ' ^ (DxD)®A '—> D ® A Jl D, D ® A (Ti a D®(D®A)s etc. = A | °D, A ^ ( + v ) A D ® A 1 °"D, D ® A(T) D ® (D® A) = (DxD)®A—P_®—U D ® A Jl DxD,A a ( 5 ' 5 + ^ (DxD)®A A " ® P 1 »D® A Jl°D,A ^ 5 ^ ( + + D On the other hand Ji TA is D®(D®(D®A)) s (DxD)®(D®A) p® 1 •* D ® ( D ® A), ® A 75 » u' , 5 : v For morphisms % : u A | °D,A > v' and V : w D® A JI°"D, D® A ^ ) (V) v = (D x D) ® ( D ® A) A !°D,A ( v ) > w' of D , as before, we have D® (D® A) 1 °"D, D®(D® A)(T) D®(D®(D®A)) p®1 "p®1 > D ® (D® A) = ( D x D ) ® A D® A i cr DxD, D ® A ( l . ? ) 'p ® 1 *• D ® A (DXD)®(D®A) D ® (D® A) £ (DxD)®A etc. A Jl D,A a D ® A | D , D ® A ( ? ^ D ® (D® A) = ( D x D ) ® A — ( v ) a A + l DxD,A * ^ a ( A (DxD)®A + | cr A ( | + 5 + v) as before. We obtain the desired commutative square by uniqueness. " ® P 1 D® A >D® A P ® » D® A 1 76 Let (T, T), Jl )be a 2-monad defined on a 2-category A. A (strict) T -algebra (B, p) is an object B of A together with an algebra structure map which is a 1-cell p:TB > B such that the diagrams commute. Proposition 10 Let (D,+,0) be a strict monoidal category and let (T, T), JJ.) be the 2-monad of propos with! = D®-. Then p:D®B • B is a T-algebra structure map if and only if the corresponding functorfy.D > A(B,B) is a monoidal functor, where A(B,B) has the obvious structure as a strict monoidal category. Proof: Suppose we are given a monoidal functor (D, +, 0) » A( B ,B). Let p:D<8>B corresponding 1-cell, that is, the unique 1-cell such that a D,B Hu) ( 1 7 ) for each morphism % : u » u' of D. We show that the diagrams > B be the 77 D ® ( D ® B )- (ALG) D® B D®B 112 ( DxD)®B V B ( 0 ) D®B B commute. Thefirstdiagram commutes because $( 0) = 1 Q. To show that the second diagram commutes let £: u > u' and £ : v » v' be two morphisms of D. Then 'DxD.A^ °DxD,A^'5) a DxD,A '' (u (DxD)®B V,) V B B 'p ® 1 ( H.B * ( U + V + ) 5> D® B <K u+v) <{>( u' +v') D®B *(u)$( v) Jl $(D$(T) B B $(u')$(v') *(u') $(V) On the other hand, °D,D®B °D, B ^ B Jl °b B ^ ( D U & B i°D, D ® B ( 5 ) °D,D®B °D,B< '> °D,B ® ( v ) (U) 1°D B F ( 1® p D®(D®B) (V,) °D,B( V) + & 1°D, B D® B • D® B ( 5 ) D®B- °D,B( ') V $(u) $(v) $(u') also. Conversely, suppose that p:D®B $: D B is a 1-cell such that the diagrams (ALG) commute. Let > A (B, B) be the corresponding functor, that is, for an object IT of D, $ (ID is the 1 -cell 79 B and for a morphism g: u ff(u) D® B > u' of D, $( J) is the 2-cell cr(TJ) B (T(|) | D® B cr(u') Then we can show that # is a monoidal functor. Clearly 4>( 0) = 1 g. An obvious rearrangement of the steps used to prove thefirstpart shows that $ (g~+ 5*) = $ (?H (T)- • Let (T ,T| ,Ji )be a 2-monad defined on a 2-category A and let (B ,p)and (B' ,p') be two T-algebras with structure maps p:TB > B and p:TB' > (B',p') is a pair (h,a) where h:B > B' respectively. A morphism of 1-algebras (B ,p) » B' is a 1-cell and a : p'°Th > h°p is a 2-cell as shown in the diagram such that CO identity 80 and (ii) TB 2 JiB Th 2 id T B' 2 JiB 1 Tp' Given two morphisms of T-algebras (h,oc):( B ,p) . „ P' P' > (B' ,p') and (g,(3):(B ,p) 2-cell between morphisms of T -algebras i f : (h, a ) P " > (g, (3) is a 2-cell i f : h > (B' ,p'),a > g such that P P' With the evident rules for horizontal and vertical composition we have a 2-category T-Alg( A). In the case that (T ,T) ,Ji ) is a 2-monad of the form given by proposition 9, where T = D®- for a strict monoidal category (D, + , 0) , we denote the 2-category of T-algebras by D-Alg( A). A morphism of T-algebras (h ,oc):(B ,p) h:(B,p) > ( B' ,p') is called strict if oc = id, in which case we denote the morphism by » (B',p'). Restricting to such strict morphisms without changing the 2-cells gives a 81 sub-2-category T-Algg( A) of T-Alg( A). Note that there are some changes in notation and terminology from those in [2DM]. The standard result of 1-category theory easily generalizes to give a strict adjunction F A ~* Tl U T-Alg (A) s £ where F is given on objects A of A by FA = (TA ,J1A), with the obvious extension to 1-cells and 2-cells, and U is the evident "forgetful" 2-functor. For a T-algebra (B ,p), where p:TB £( B ,p): FU( B ,p) * (B ,p) is p:(TA,JiA) » B is the structure map, » (B ,p), which is easily seen to be a strict morphism of T-algebras. In the case T = D ® - , for a strict monoidal category (D, +, 0), we abuse notation and denote the "free T-algebra" ( TA.J1A) by ( D®A, p ® 1 ). Recall that, strictly speaking, Jl A is the composition of v "p® 1 :D®(D®A) • D ® A with the isomorphism (DxD)®A =D®(D®A). Now extend the forgetful 2-functor U to T-Alg( A) and suppose that F takes values in T-Alg( A), or, more precisely, compose F with the inclusion of T-AlggC A) into T-Alg( A), but retain the symbol F for the resulting 2-functor. Then the counit £ extends to a para-natural transformation as follows. Foramorphism T-algebras (h,oc):(B,p) FU(B,p) FU(h, a) » (B',p') of let £(B, p) £ (h, a) FU (B , p')1 be given by the 2-cell £(B', p') (B,p) (h, oc) •(B\ p') 82 Since (h ,<x) is a morphism of T-algebras, we have This shows that £ (h ,rx) = rx : p'°Th > (h |cx )°p is a 2-cell between morphisms of T-algebras. It is easy to see that this definition makes £ into a para-natural transformation FU ——> 1 between endo-2-functors of T-Alg(A). 83 Proposition 11 Given a 2-monad (T, T), Jl) defined on a 2-category A, there is a quasi-adjunction T-Alg (A ) U T) £ where the horizontal counit E is para-natural and the vertical unit and counit are identities. Proof: • The triangle identities are essentially the same as for the strict case. By proposition 2 a monad ( B ,t ,T\,p) in a 2-category A gives rise to a unique monoidal functor $ : ( A ,+ ,0) > A( B ,B) such that $( 1 ) = t, 4>( T\) = T\ and <K1T) = p. If A has tensor products, we obtain a A-algebra (B ,p), where the structure map p: A ® B > B corresponds to $, that is, it is the unique 1-cell such that cr(m) B lcr(I) A ® B cr(n) for each morphism £. m -•n of A . Conversely, a A -algebra (B, p) givesriseto a monoidal functor $: ( A ,+, 0 ) > A( B, B) and therefore also to a monad (B ,t ,Tt ,u). Hence for a 2-category A with tensor products, monads in A are just A-algebras. By comparing also the 1-cells and 2-cells we shall see that the 2-categories Mon( A) and A-Alg( A) are essentially the same. Let ( h , o c ) : (B ,t,ri,u) (1) » (B' ,t',T\ ,u') be a morphism of monads, that is, a 1-cell in J Mon( A). Let (B ,p)and (B' ,p') be the A-algebras corresponding to these two monads with structure maps p: A ® B : ( A ,+ , 0 ) » B andp : A ® B ' 1 > B' respectively and let be $:( A ,+ , 0 ) > A(B,B), > A( B' ,B') the corresponding monoidal functors. Then we have the composite functors 84 A A (B, B) A ( B', A (B, B' ) B' ) A (B, B ) 1 whereh«= A(B,h) and h*= A( h,B'). For each object n of A , h„<Kn) = ht and h*$'(n) = (t') and-we n have a 2-cell B- B (n) a' B'. (t') n n copies L e m m a 12 ex : h*$' > given by cx(n) = ex' > is a natural transformation. n Proof: We need to show that the diagram (m) (V) h m a (t') hn a commutes for each morphism f: m (n) > n of A , that is, ht' n 85 and £' =4>( ?'). It suffices to show this for the generating morphisms T\and p., but this follows where £ = immediatelyfromthe definition of a morphism of monads. • It follows from lemma 12 that there is a unique 2-cell a : p'( 1 ® h ) A, B B p A® B > hp such that t B n 1® h id oc. • A ® B' B' a A , B' ( n ) B' P' (t') n for each object n of A. Lemma 13 (h,a): (B,p) > (B'.p') is a 2-cell in A-Alg( A). Proof: The condition B O-(O) *A ® B — p 1 1® h id B' CT(0) identity oc • A ® B' B' 86 is immediate. To show that A®(A®B) £ (A*A)®B "p eg) 1 1 ® ( 1 ® h) B') = (A xA )® B' a A ® B' 1 'p ® 1 ® p A ® (A® B) *• B 1® h id A ® (A ® p »-A®B B' P' p »• A ® B 1® ( 1 ® h) * B 1® h 1® a A ® ( A ® B' )• A ® B' 1® p B' P' let m and n be two objects of A . Then B cr(m,n) v * (A xA )® B p® 1 •A ® 1® h B id (A xA )® B' C7(m+n) • 'p ® 1 1® h a(m+n) V • A ® B' oc • A ® B' P' mfn , •A ® B id B' p 1® h id cr(m, n) B P' 87 while <T(n) ———> B 0"(m) — • A ® (A® B) A ® B 1® p ^ ® (1® h) 1® h p - A® B 1® h 1 ® oc B' o-(n) •A ® B' cr(n) B cr(m) . • A® B • A ® (A p *• ® B') oc Z A 1® p ' rj(m) B ->• B p' p B - 1® h id V •A® B' o-(n) 1 1 ® B' »• A® 1® h B' >B B' oc •A fj(m) P' ® B' B' P' •^nri-n B »• B *• B ry(n) B'- (t') * B oc >^ (m •B' n B (t') B' r B' (t') : ,m+n • Lemmas 12 and 13 showthata 1-cell in Mon(A) gives rise toa 1-cell in A-Alg( A). Conversely, suppose (h,cc):( B,p) B t > (B ,p') is a 1-cell in A-Alg( A). Let 1 B B ^ — *A®B P B - 1 ®h « 7 id oc^ 88 Then we can show, by induction, that B cr(n) B (t') id •B' r ®B 1 ®h (n) oc' B' • A B' oc A cr(n) ® B' B' P' for each object n of A . The case n=0 is immediate and we have t B t n B B ™< > n B'- B (t') •B' n 2liL> . A ^i2_* ® P — * B ® B A 1®h ~ B' P' (7(1) • A® B' B' p' by using the inductive hypothesis, B a( n) • A® B a( l ) • A ® (A® id a(n) B) id • A ® B' 1® p • A® B 1®(1®h) 1® h B' B id a A® B' cr(n) „ 1®h id B' £ B cr(l) A ® (A ® B') p - 1® h 1® a 1 ® p' oc A ® B' P' "p ® 1 • »• A ® 1® h 1® h id B' B id (A A X a( 1, n ) )®B' 'p ® A 1 ® B' since (h ,<x) is a 1-cell in A - Alg( A), (rf 1+n ) 1 B p • A®B id cr( 1+n ) Let | : m •A ® B' » n be a morphism of A. Then B A ® B £ »B 1® h o ^ A ® B' B' P' (rfn) or(m) cr(m) » A®B 1® h id B' crfm) •A ® B' 90 Hence B > B where f = $( f) and ?' = $(!'). By taking (• to be r\ and u in turn we obtain the required properties for (h ,cx ( 1 >) to be a 1-cell in Mon( A). It is now clear that the 1-cells of Mon( A) correspond to the 1-cells of A-Alg(A). Let<p: (h,oc I )) 1 »(g,|3 >) be a 2-cell between morphisms of monads and let (h,oc) and (g,|3) (1 be the 1-cells in A-Alg( A) corresponding to (h,cx < ) and (g,(3 >) respectively. Then, for an object n of X) A, we have B (1 • (g ,(3) is a 2-cell in A -Alg( A). Conversely, it is clear that a 2-cell in A -Alg( A) Hence <p : ( h ,cx) is also a 2-cell in fion( A). From now on we shall identify the 2-categories Mon( A) and A -Alg( A) for a 2-category A which has tensor products. However, this causes notational problems with regard to 2-cells. For a 1-cell > (B',p') in A-Alg( A), the corresponding morphism of monads is (h,cx):(B ,p) (h,oc ):( B ,t ,T\,(j) • (B'.t'.Tr" ,u') where rx (1) (h, J3): (B ,t ,T\ ,u) ( 1 ) > (B' ,t' ,T\' ,u') is a morphism of monads, we shall denote the corresponding morphism of A-algebrasby (h,"J3"):A Let (E ,t,T\,Li) = ocO"( 1). Going in the opposite direction, if » (B',p'). Thus "J3"cr( 1) = |3. be a monad in Cat. Since, for an object A of A, - ® A : C a t » A is a 2-functor, it follows easily that (E®A ,1® 1 ,T\<8> 1 ,u® 1) is a monad in A. For example, ( A , "p) is a monad in Cat, that is, an object of A-Alg( C a t ) , where the A-algebra stucture map p:A xA v > Cat( A , A ) is the corresponding monoidal functor, this monad monoidal addition. If $ : (A ,+,0) v can also be denoted by ( A , t , Ti, u ) where~t = v v 1+| , T\ = rQ: 1 V v p= M):( t ) v 2 > A is given by the v 1): A » A is the functor given by "t( |) = > t is the natural transformation given by T\( n) = ti+n: n v v > t is the natural transformation given by "u(n)= p+n:n+2 v > n+1 and > n+1. For 92 an object A of A, (A®A, t® 1 , n ® 1 , "p® 1) is just the free monad ( A ® A , ' p ® 1). Indeed, the tensor v , v, product operation induces a 2-functor of two variables Mon(Cat)xA , > Mon(A) given on objects by ((E,t,Ti,p),A) i • (E®A,t® 1 ,n®1 ,U® 1). Although this is straightforward to verify directly, we omit to do so; instead we shall establish the corresponding general result for D-algebras where (D,+ ,0) is an arbitrary strict monoidal category. Let (D,+,0) be a strict monoidal category, let ( E ,p) be a D-algebra in Cat with structure map p: DxE » Cat( E ,E) be the corresponding monoidal > E and let A be an object of A. Let $ : (D,+,0) functor. Then we have a monoidal functor ¥ : (D,+,0) (D,+, 0) $ * Cat(E.E) > A( E®A ,E®A) given by the composition -®A »A(E®A, E®A). Hence we have a D-algebra (E®A ,q) in A, where the structure map q: D®(E®A) > E®A is the 1-cell corresponding to ¥. Lemma 14 In the situation above the structure map q: D® (E® A) • E® A is given by the composition p ®1 D ® ( E ® A ) = (DxE)®A • E®A. Proof: Let %: u » u' and $: e » e' be morphisms of D and E respectively. Then E® A 93 <H u ) ® A °" E A °f_ A ( ? ( p ( E ® (p(u',e')) A a 5 E ) ® A DxE,A ( E®A ' i ) U 5 ) '' (DxE)®A p ® 1 E®A e , ) ( U ) Jl°D,E®A ^ ( °D,E®A °E,A(e') ( u ( 5 °D,E®A °E, A ^ ( DxE,A Jl DxE,A ' a ! ° E A 1 A a A J,#( I ) ® E®A ) (p(u,e)) Jl°E, A A Jl °E, A 1 D®(E®A) s (DxE)®A E®A ( U , ) • With an obvious abuse of notation suggested by this lemma we write p® 1 for the structure map q. Let (h ,a): (B ,p) > (B' ,p') be a 1-cell in D-Alg( A). Then we have a corresponding natural transformation a : h*$' > h „ $ between the functors (D,+, 0 ) A (B, B) A (B, B' ) ( D, +, 0 ) A ( B \ B' ) A (B, B' ) 94 where $ and $' correspond to p and p' respectively. The naturality condition can be expressed as follows. For each morphism g: u > u' of D, Proposition 15 (i) (B' ,p') is a morphism of D-algebras if and only if the natural (h,oc):(B.p)- transformation oc corresponding to the 1-cell oc satisfies the conditions: (A) (B) a ( 0 ) = id:h »h, $(v) *(u) *'( v) $'(u) $'( u+V) for each pair of objects u,v 0 / D. (ii) (f: h /.ef (h,a), (g,|3): (B ,p) > (5' ,p') be two morphisms of D-algebras. Thena2-cell > g is a 2-cell between morphisms of D -algebras ip : (h, oc) — > (g, [3) if and only if 95 *(u) *(u) <Ku) " i'CU) " for all objects u of D, where a are J3 the natural transformations corresponding to a and |3 respectively. Remark: Combining (A) and (B) of (i) with the naturality condition for oc, we have the three conditions for the pair (h, oc) to give an allo-natural transformationfrom$ to $', where $ and $' are regarded as 2-functors in the obvious way. Proof: (i) Suppose (h ,cx) satisfies the conditions (A) and (B). Then a straightforward generalisation of the proof of lemma 13 shows that (h ,oc) is a morphism of D-algebras. Conversely, if (h ,oc) is a morphism of D-algebras, we can easily show, using the same steps as those in the obvious generalisation of lemma 13, but arranged in a different order, that B tr( v) * D®B cr( u) 1® p »> D ® ( D ® B) 1 ® (1® h) cr( u,v) • (DxD)®B 1® p ' p B ® h 1® a D ® (D®B' )• B *- D ® B a D ® B' "p ® 1 — »-D®B P' B' p 1®h 1® h oc ( D x D ) ® B' 'p ® 1 -*• D ® B' B' 96 This gives (B). (A) is immediate. This follows by generalising the argument used to compare the 2-cells of Mon( A ) with those of (ii) A-Alg(A). * - • P r o p o s i t i o n 16 Let A be a 2-category with tensor products and let (D ,+ ,0) be a strict monoidal category. Then the tensor product operation induces a 2-functor of2-variables D-Alg(Cat)xA > D-Alg(A) given on objects by ((E,p),A) i » (E®A,p®1) Proof: First we show that for an object A of A, -®A:D-Alg(Cat) » D-Alg(A) is a 2-functor. Let ( h , o c ) : ( E,p) > (E'.p ) bea 1-cell in D-Alg( Cat). Let ¥ and ¥' be the composite functors 1 $ (D,+, 0 ) and . C a t (E, E) ( D,+, 0 ) - ® A ® A Cat(E',E') A ( E® A, E® A) •A ( E ' ® A , E ' ® A ) respectively, where $ and $' and correspond to p and p'. For each morphism %: u » u' of D, we have $("v)®1 E®A h® 1 E'®A $("v)® 1 oc( v ) ® 1 4>'( v ) ® 1 E®A E®A h® 1 E'®A h® 1 E'®A $'( u)® 1 4>( u)® 1 cx( u ) ® 1 $'( u)® 1 E® A h® 1 E'®A 97 cx(0)®1 = id:h®1 E®A h® 1 E'®A »h®1and $( v ) ® 1 $( u ) ® 1 ' »• E® A h® 1 oc( v ) ® 1 $'( v ) ® 1 cx( u)® 1 E'®A- 4>'( > E®A h® 1 E'®A u)® 1 $ ( U + V )® 1 E®A — h® 1 oc(u+ v)®1 E'®A • $ '("u + V ) ® 1 • E®A h® 1 E'®A for each pair of objects u, v of D. Hence we have a natural transformation V: (h®l)**' • (h®1)„¥' which satisfies the conditions (A) and (B) of proposition 15. This now gives a morphism of D-algebras (h®1 ,V):(E®A,p®l) • (E'®A,p'®1) such that for each pair of objects e of E and u of D A aCe) • E®A cr(ID • D ® ( E ® A ) = (DxE)®A —•• p® 1 h® 1 1®(h®1) D®(E'®A) = (DxE')®A • E®A p'® E'®A 98 a(e) A * ( u)® 1 • E®A Tf(u) = h® 1 cr(e) h® cx(~u)® E'®A- A *- E ® A E'®A $'( u)® 1 (j( u ) ® 1 *> E® A *> (DxE )® A E® A ( Ixh)® 1 cx ® 1 (DxE')®A cr( u,e) (DxE)®A E'®A p' ® 1 E® A ( Ixh)® 1 a® (DxE')® A h® 1 p ® 1 .1 h® 1 E'®A 1 Again we shall abuse notation by writing ( h ® 1 , ¥ ) as ( h ® 1 ,rx® 1). Let(h,a),(g,|3):(E,p) > (E',p') be 1-cells in D-Alg( Cat) and let <p: (h,oc) > (g,|3)bea 2-cell. Then h® 1 E® A $( u)® 1 *• E ® A g® <p ® 1 E®A E'®A- oc( u ) ® 1 # * ' ( u)® 1 > E®A h® 1 h® 1 PC u ) ® 1 g® 1 $( u)® 1 E'®A E'®A- *'(U)® 1 E'®A 99 for each object IT o f D. Hence <p® 1 : (h® 1 ,cx® 1) > (g® that the preceding constructions make-®A:D-Alg( C a t ) 1 ,(3® 1 ) is a 2-cell i n D-Alg( A ) . It is clear > D-Alg(A) into a 2-functor. It is easy to see that for a fixed object (E,p) o f D-Alg( C a t ) , (E,p)®- : A » D-Alg(A)is > A in A , 1 ®g: (E®A ,p® 1) also a 2-functor. In particular, for a 1-cell g: A > (E®A' ,p® 1 ) is a 1 strict morphism o f D-algebras. • An alternative derivation of the soft adjunction of chapter I W e now give an alternative construction o f the para-soft adjunction described at the end o f chapter I. L e t H denote the category w h i c h has one object 1 (and one morphism). There is a trivial monad structure on I for which the corresponding A - a l g e b r a structure map is the unique functor A x II = A both o f the functors A x I > I and A * I b y f . L e t u :1 0 • H. W e denote be the inclusion functor »A 0 given b y u ( 1) = 1. T h e n , since 1 is a terminal object i n A , w e have an adjunction 0 , A \ u id 0 I given by the natural isomorphism I ( f 0 ( n ) , l ) £ A(n,u ( 1)). The transformation given b y T \ ( n ) = Li > 1. 0 :n 0 unit T I : 1 0 >uf 0 0 is the natural A s mentioned previously, there is a "left hand" monad structure on A with sructure map given b y the monoidal addition "p "t : A = "+":A xA >A ~u(n)= u+n:n+2 "1(1") = is the functor given b y given b y T i ( n) = T\+n: n v > A. Then we > n+1 > n+1. v ( A , p ) = (A 1+1 , "r\: 1 and u : ( t ) v have 2 v •t v /\,"r[/u), where is the natural transformation > "t is the natural transformation given b y 100 Lemma 17 Let u : " t u 0 0 (u ,"u "):(U f ) 0 0 ; 0 > u be the natural transformation given by M( n) = u : 2 0 0 > ( A , " p ) and f : ( A , " p ) > ( I , f ) are morphisms of monads and the 0 0 adjunction fr H id in Cat enriches to the adjunction fr (A, P) V in A-Alg( C a t ) = Mon(Cat), fhar/'s,tothe (A, t. T\ M) v v adjunction , v 1 TIQ 1 (U ,U ) 0 0 I(J (I, Proof: id, since (u e nu v 0 0 )(!)= U (l) nu ( v 0 0 1) = • 1. Then u ( T l + l ) = 1. l.id, id) 101 since p ( l ) u u ( l ) = p(p+i) = p(i+ p) = p ( i r t u ( l). Thus v 0 0 0 (u ,p0):(II,1 ,id,id) 0 » (A,"t, Ti, u) is a morphism of monads. f :( A,"p) v 0 > (2, f )is v 0 0 clearly a strict morphism of monads. 1 since p f (n) tTi (n) = u(l+ p <>) = u < > = Tt t(n).Thus n v 0 0 n 0 n+1 v 0 : 0 1 > (u ,p )f is a 2-cell in 0 0 0 Mon(Cat). Let A be a 2-category with tensor products. Then, by proposition 16, we obtain an adjunction in Mon(A) • 102 fp ® 1 (A®Vp®1) "* t TiQ® 1 ( u ® 1, 0 " p ® 1") 0 ( I ® A , f ® 1) 0 id For each pair of objects A ,B of A, we have isomorphisms of categories A(H®A,B) = Cat(I,A(A,B))= A(A,B) which are strictly natural in both variables. It follows that o~( 1): A A = H ® A. Let p : A ® A — > 1 ® A is a natural isomorphism • A be the composite 1-cell 0 f A® A o ® 1 H®A = A. > Then p0 is the structure map for the trivial monad structure on A; (A,p0) = (A, 1 A ,id,id). Hence we have the following adjunction in Mon( A). PQ (A®Vp®1) TIQ® 1 " ( (ff(l),"ff(IT)") (A, P ) 0 i d Note that 1 A | a ( u o-(i) Let A 1 Tl V £ Non(A) ( n > ) A® A 103 be the quasi-adjunction obtained by applying proposition 11 to the current situation. F is given on objects by FA = (A®A, p®1) = (A® A,"t® 1 /TI® 1 ,"u®1) s/ T): 1 and V is the evident forgetful 2-functor. > VF is the strictly natural transformation with T)A = a( 0) :A • A ® A and £ : FV > 1 is the para-natural transformation such that for a monad (B ,p) = ( B ,t,Tt,u), £( B ,p) is the strict morphism of monads given by p : (A® B , "p® 1) (h ,oc): (B ,p) > (B ,p). For a morphism of monads > (B' ,p'), £ (h ,cx) is the 2-cell between strict morphisms of monads given by P A ®B 1® B h rx A ®B B" 1 As before, let F : A p' > Mon( A ) be the 2-functor given on objects by F A = (A,p ) = 0 0 0 (A, 1 ,id ,id), with the obvious extension to 1-cells and 2-cells. By varying A the adjunction A (A® A, p® v (A, P ) 1) r^® 1 0 ((T(l),"ff(M)") givesriseto a strictly natural adjunction (cpo.^O' ^0' o ) e : F ^ * o« where e is the identity F 0 modification. Hence, by means of the attaching procedure, we obtain a para-soft adjunction (F ,V,T| ,E ,r ,s ). 0 0 0 0 0 ...> Mon(A) The choice of notation suggests that this is the same as the soft adjunction described at the end of chapter I. We shall now show that this is indeed the case. 104 > VF . The horizontal unit T) : 1 0 0 For an object A of A, T) A is the composition 0 T|A a(0) The horizontal counit E : F V 0 Vcb A 0 VF A V FA • 0 A® A • 1. 0 For a monad (B ,p) = (B ,t,fl,p), £Q( B ,p): (B ,p ) ——> (B ,p) is the morphism of monads given 0 by the composition (cr(l),"o-(p) ) ( A ® B , p ® 1) (B, P ) that is, it is (t,"p"):(B ,p ) • (B,p) or (t.p): ( B, 1 ,id,id) 0 n+! > t for each object n of A . n + 1 n : Suppose (h ,oc): (B ,p) » (B' ,p') is a morphism of monads. Then £ ( h ,oc) is the 2-cell between 0 morphisms of monads given by o-(i) , » A ® B p id cr(l) The vertical unit > (B.t.n.u). B Note that "p"cr( n) = p< > t B (B, p) , v 0 A ® B' r :l. >Y£ oVT] . 0 0 0 For a monad (B ,p), r ( B ,p) is the 2-cell 0 T|V(B,p) V(B, p) Vcb V(B, p) 0 • VFV(B, p) • VF V(B, p) Q V E ( B , p) (7(0) A ® B V ( B , p) 1 7* A® B cr(l) B |ff(T\ (o)) 0 A® B cr(0) The vertical counit s 0 : E F 0 o F T| 0 0 0 >1. For an object A of A, s A is the 2-cell between morphisms of monads given by 0 106 F Vcp A 0 0 F VF A Q 0 V VF A 0 (A, P ) | id 0 Thus we see that Q (A, P ) Q (F ,V,T| E ,r s ) is the same soft adjunction as that obtained in chapter I. The 0 0l 0 0l 0 various 2-functors and natural adjunctions involved in the two methods of constructing this soft adjunction by means of the attaching procedure are pictured in the following diagram. A V |j Mon(A) V F 1 i 107 HI. The Lifting Construction for Soft Adjunctions Let (F ,U,T| ,£ ,r,s) be a para-soft adjunction where F: A Let Q denote the para-natural transformation U £ ° T) U: U > X and U :X > U and let m : Q ° Q modification given by the diagram T|U U£ Proposition 1 For each object X of X, (UX ,QX ,rX ,sX )/s a monad in A. BmoC O U > A are 2-functors. > Q be the 108 109 110 Ill On the other hand, 113 This is the same as the composite modification obtained for Q 2 • The triple ( ft ,r,m) is called the natural monad structure associated with the soft adjunction (F, U, T|, £ ,r ,s). It can be interpreted as a monad in an appropriate functor 2-category. Let g: X > X' be a 1-cell of X and consider the monads (UX ,QX ,rX ,mX) and (UX' ,QX' ,rX' ,mX'). Since r and m are nodifications, 114 it follows that (Ug,Qg):(UX,QX,rX,mX) * (UX'.QX'.rX'.mX") is a morphism of monads. With the evident description on 2-cells, we obtain a 2-functor M : X » Mon( A ) given on objects by MX = (UX ,QX ,rX ,mX). Suppose that the 2-category A has lax limits, or at least Eilenberg-Moore objects. Then we have the Eilenberg-Moore 2-functor V : Mon( A ) » A whose value at a monad ( B ,t ,T\ ,u) is the Eilenberg-Moore object B. We also have the forgetful 2-functor V : Mon( A ) VM : X > A . Let 0 = VM : X >A . Note that U = > A . Then the para-natural adjunction (cp , v ,h , e ) : V described in chapter I, whose value at a monad (B ,t ,T\,U ) is the canonical adjunction (f ,u ,T\ ,e): B gives rise to a para-natural adjunction ( c p , v , h , e ) : U e = eM. Note that h = r: 1 • > V > B, >0 where cp = cpM, V = V M , h = hM and • O = V cp. The following proposition summarises the situation. Proposition 2 Given a para-soft adjunction ( F , U , T ) , £ , r , 8 ) between 2-functors U :X » A , there is a 2-functor 0: X F:A > X and » A such that for each object X of X , Ox is the Eilenberg-Moore object associated with the monad ( U X . f t X . r X . m X ) . There is also a para adjunction (cp , v , h , e ) : U > 0 such that for each object X of X , (cpx, v X . h X , e X ) : UX is the canonical adjunction for the monad (UX,QX,rX,mX). We call the 2-functor 0 : X > A of this proposition the lifted 2-functor associated with the soft adjunction ( F ,U ,T) ,£ ,r,s). Under a suitable hypothesis we shall construct a complete "lifted" para-soft adjunction ( F ,U , T), £ , r , s ) for a given para-soft adjunction ( F , U , T ) , E , r , s ) . The horizontal unitT) is constructed in a manner which is roughly analogous to the way in which the comparison functor for an ordinary adjunction in is constructed and the horizontal counit £ is constructed in a manner analogous to the construction of an adjoint for the comparison functor [CWM.Chapter VI]. First we construct T|. No additional hypothesis is needed for this, apart from the requirement that A has sufficient lax limits so that U exists. > Ox • 115 Lemma 3 For each object A of A T|A T)A UFA T)T)A UFT)A UFA T] UFA UFUFA U£FA UFA /san QFh-algebra. Proof: The condition involving rFA follows immediately from the definition of a para-soft adjunction so we check the condition involving mFA. T)A T|A UFA T|T)A UFT)A UFA T|UFA UFUFA U£FA UFA lOFAoQFA 116 UFA T)A , U P U F U£FA_ A /T] UFA UFA \T)UFUFA T1T1UFA J). T]T]A\ ^UFA X ^ U F A TIUEFAJI \ UFUFUFA UFUFA UFA UFA ' UFA T)A ^ T|UFA .UFUFA UFA \T]UFUFA T|T|UFAJ[ \ UFT)UFA UFUFUFA UFT)T)A^ UFT]A UFUFTjA TIUEFA| UFUFA UEFA ^ UFUFA ^ UFA X'HUFA ,T]UFUFA UFT1A UFA >^ , UFUFUFA \ * V T|UEFA]J UFUFA V UFUEFA UEFUFA UE FA K UEEFA]1 UFA • T j p ^ — • UFUFA ^ U F U F A _ _ * UFA UFA ' UFA T) UFA UFUFA UE FA UFA UE FA UFA UFA which is the required 2-cell. • There is a modification z: Q ° V > V such that for each object X of X, is the universal cone associated with the Eilenberg-Moore object. To see that z is a modification, note that it equal to the modification 119 Note that V FA ° T)A = T)A. We now show that, with a suitable definition for 1-cells, T) becomes a para-natural transformation such that VF ° T| = T|. Lemma 4 Let g :A > B be a 1-cell in A. 77?en T)g: T)B ° g QF B -algebras from to Proof: > UFg °T)A /s a morphism of 120 122 It is straightforward to check that this makes T) into a para-natural transformation such that VF ° T) = T|. Note that, if T| is strictly natural, thenT) will also be strictly natural. We now consider the problem of constructing a "lifted" horizontal counit £. In order to do this we introduce the following coequalizer hypothesis. Let a and b be the composite modifications given by the following diagrams. We suppose that for each object X of X the two 2-cells aX and bX have a coequalizer in the horn-set category X( FUX ,X), and furthermore, that there is an additional naturality property satisfied.namely: for any 1-cell g: A > UX in A, the coequalizer of aX and bX is preserved by the induced functor Fg*= X(Fg,X):X(FUX,X) For each object X of X let £X: F UX and bX, so that we have a coequalizer diagram »X(FA,X). • X be a chosen coequalizer "object" for the two 2-cells aX 123 aX nX EXoFVX £X oFQX o FVX ex bX For the present, consider nX to be a convenient label for the 2-cell which arises here. Later on we shall see that A we do indeed have a modification n, as the notation suggests. We now show that e extends to a para-natural A\ A transformation e: F U * 1. Let g: X > Y be a 1-cell of X. Then, by the naturality part of the coequalizer property, we have a coequalizer diagram aYoFUg e Yo Q Y o FVYo FUg EY°FvYoFUg F nY o F U g - *eYoFUg b Y o FUg Consider the diagram aY oFUg E Y o f f i Y o F V Y o FUg CYoFVYoFUg nY o F U g - »-eYoFUg bY o F U g g o aX goex"FQX°FVX g° g o eg E g o Fv Y (Eg"FQX°FVX)o(EY°FQg°FVX) e x o FVX g onX bx A initially excluding the arrow for Eg. The left hand and middle arrows are the 2-cells given as follows. g °h 124 FUg FUX FUY FVY FVX FVY FVX FQY FQX Since a and b are modifications, we obtain two commutative squares by taking the upper and lower horizontal arrows respectively. Using the upper coequalizer diagram we obtain a 2-cell Eg, as shown, such that the completed right hand square commutes. Using the uniqueness part of the universal property associated with the appropriate coequalizers and the para-naturality of E, it follows that £ is para-natural. Then the commutativity A. of the right hand square shows that n: £ ° F V j* » £ is a modification. Now we construct the vertical unit and counit for the lifted soft adjunction. We start with the vertical unit A. A* A. A. A. A. r. Let Q denote the para-natural transformation U £ ° T) U : U A. c: V A. A. » V o Q given by the diagram A* > U and consider the modification Proof: We work at the level of para-natural transformations and modifications instead of evaluating them at an arbitrary object X of X. On the other hand, 132 T]U T)U UFU • which is the same modification that we obtained before. It follows from lemma 5 that for each object X of X, there is a unique 2-cell such that uex A. A. Using the uniqueness part of the universal property of UX, it follows that r: 1 A. > Q is a modification. Thus we now have a candidate for the vertical unit of the lifted soft adjunction. We now construct a candidate for the vertical counit 133 By taking T]A: A • UFA for the 1-cell g in the original statement of the naturality part of the coequalizer hypothesis we obtain a coequalizer diagram a FA ° FTJ A • £ FA ° Ff]> FA ° FT)A bFA ° FT| A rA > ^ £ FA ° FT)A - A n FA ° FTi A ; ! • £ FA ° FT] A for each object A of A. Note that F VFA ° F T|A = FT)A. Lemma 6 sA: £ FA o F T)A > 1 p coequalizes the two 2-cells aFA ° F T|A and bFA ° FT)A. A Proof: aFA © F T]A is the 2-cell FA FTI A FUFA FT) UFA • * FUFUFA FUEFA £ FUFA ££FA FUFA while bFA ° FT|A is the 2-cell £ FA »- FUFA £ FA FA 135 FT] UFA FUFA • as required. It follows from lemma 6, using the preceding coequalizer diagram, that there is a unique 2-cell sA: E FA o FT|A > 1 p such that A FT] A FA £ FA FT] A FUFA sA V £ FA FA A routine verification involving an appropriate coequalizer diagram, obtained using the naturality part of the coequalizer hypothesis, shows that s: EF ° F T) > 1 is a modification. P r o p o s i t i o n7 Given a para-soft adjunction (F ,U ,T| ,£ ,r,s) for which the coequalizer hypothesis holds, t is a lifted para-soft adjunction (F, 0, T), E, f, 8) where 0, T), £, rand 8 are as described above. Proof: It remains to check that we do indeed have a para-soft adjunction. UF 137 139 L e m m a8 A. The para-natural transformation cp : u composition * 0 can be recovered from T) and E as fne Proof: For each object X of X, cpX: UX • UX is the unique 1 -cell such that UX This follows by the standard construction of the canonical (abstract) adjunction associated with a monad, as given in chapter 1. On the other hand, we have UX 142 T|ux UX uex • »• UFUX * UX TjUFUX T|UX T|T)UX UFUX' UFUFUX- UFT]UX T)UX TIUEX uFuex UFUX UEFUX uex U££X UFUX which is mX. Hence Uex o T|UX = cpX:UX Ug ux •* ux > Y be a 1-cell in X. Then UY T|UX T]UY T]Ug UFUX » UX.Letg:X uex UFUY ClFUg uex ueY ueg ux UY- Og A A VY • UY A This shows that UC ° T)U = cp as a para-natural transformations. We can apply the attaching procedure to the lifted soft adjunction (F, U, T), £ , r . s ) using the para-natural adjunction (cp ,v ,h,e): U > 0 to obtain a para-soft adjunction (F.U.T) ,£ ,?,s) between the original pair of 2-functors F and U. We shall see that, in a suitable sense, this new soft adjunction is essentially the same as the original soft adjunction (F.U.T) ,£ ,r,s). The horizontal unit T): 1 > UF for the new soft adjunction obtained by the attaching procedure is 143 the composition VF OF- 1 UF . Hence we have immediately that T) = T). The horizontal counit £ :FU A. FU > 1 is given by the composition A. F* £ FU' The following proposition relates £ to £. P r o p o s i t i o n9 A A. Let p: £ ° F cp diagrams. A. » £ and q: £ F ^ A. > E ° F cp be the modifications given by the follo . U P : FUFU Then p and q are mutually inverse modifications. F0£ 144 Proof: p e q = 1 Using the formula which gives the definition of 8 and the second 2-cell equation for the para-soft adjunction (F ,U ,T) ,£ ,r,s),we see that this is the identity modification on £. 147 148 We continue with the comparison between the para-soft adjunctions ( F ,U ,T| ,£ ,r,s) and while the vertical counit s: £ F ° F T) > 1 is given by the diagram Proof: (i) The first modification is 151 (ii) The first modification is • Proposition 10 allows the 2-cell equations for the soft adjunction (F ,U, T|, E , r,s) to be related direcUy to the 2-cell equations for the original soft adjunction (F,U,T],E,r,s). This supplies the more precise meaning behind the earlier claim that these two soft adjunctions are essentially the same. 153 Idempotent Monads We introduce idempotent monads at this point in order to be able to give a fairly simple example of the lifting construction. Proposition 11 Let (B ,t ) be a monad in a 2-category A. Then the following three conditions are equivalent: (0 tn = nt. (ii) tp = pt, (iii) p is an isomorphism. Proof: To see that (i) implies (iii) note that in addition to the relation p • tTi = t we also have \r\ • u = T|t » p = tp • T t l 2 = tu °\ T\ =t(p °Vn.)= t . The relation p • Tit = p • tr\ gives immediately that (iii) 2 2 implies (i). To see that (ii) implies (iii) note that in addition to the relation p © T\t = t we also have Tit • u tp ©Tit = pt ©Tit =(p ©Tit)t= t . The relation p©pt = p © tp gives immediately that (iii) 2 2 2 implies (ii). • A monad (B ,t ,Ti ,p) in a 2-category A which satisfies any one of the three equivalent conditions of proposition 1 is called an idempotent monad. Recall that for a monad (B ,t ,T\,p) in a 2-category A, p < : t k) M (0) = . ] n p(l> = 1 ;t U (2) _ . 2 u t p(k) _ $(TJ(k) ).LetkTi:0 > t is defined recursively by: > t, » t, , t > p(k) = p « pk-lt ;t or equivalently, if $: (A,+ ,0) k 2 > t fork=3,4, , > A( B ,B) is the monoidal functor corresponding to (B ,t ,TI ,p), then > k be the morphism of given by 154 k.T\ = T\ + + T\ :0 * k k summands and write T l k = T \ o > t oT\:1 k J V k factors sothat$(kTJ) = T\ . ( 0T[ is the unique morphism 0 > 0 and T\° =1:1 k » 1.) L e m m a 12 For any monad ( B ,t ,r\ ,U ) in a 2-category A, we have the relations t T\ (0 h (ii) y(h+l) (iii) ot k n 8 = h h (k+l) u p(h+l) .fn. h + k . (h+k+l) = M = 11 n t t ; h,k>0. Furthermore, if ( B ,t ,TI,U ) /s an idempotent monad, we have (iv) t Ti = n t , (v) t u< > k = u< >t , > = t h h (vi) t n •u< k k+1 k k h k k + 1 h ; h,k>0. Proof: (i),(ii) and (iii) can easily be checked by obtaining the corresponding formulae in A , namely: (i) ' (h+kn)hT\ = (h+k)"ri, (ii) ' TJ(h+l)( TJ(k+l) ^ _ 7J(h+k+l) (iii) ' 7 = n+ ( h + 1 ) )h (l+hn) > 1; h,k>0. The left andrighthand sides of (i)' are different representations of the unique morphism 0 sides of (ii)' are different representations of the unique morphism h+k+1 different representations of the unique morphism 1 tu < = u * k ) k > > h+k, the two > 1 and the two sides of (iii)' are > 1. (iv) is clear and for (v) it suffices to show that t for k>0, which is easily done by induction on k. Assuming that this formula holds for some k, we have tu <k+1 > = t( u • tu <k>) = tu « t2p <k> = ut » tp <k> t = (u • tp <k> )t = u <k+1 > t. We can also prove (vi) by induction. The formula is trivial if k=0 and tT\ ® p = t from the proof of proposition 11. 2 155 Assume that the formula holds for k. Then, since tTl Ti = tT\ © T\ and k+1 k k+l o p ( k + 2 ) = K^k e M ( )op T l k + 2 «tM< = t T\ ©tTi • M • t u = t Tl • T\t • (J = t Ti = t(tT\ = t 2 k 2 k 2 k otp( k k+2 k + 1 © tu ( k + 1 ) , we have > ( k + 1 ) , otp(k+D D k + «tM< =u > k + 1 >) . • L e m m a 13 F o r an idempotent monad ( B ,t ,T\ ,u) in a 2-category A, we have the relation p(h)p(k) = t p(h+k-l). h+k »t ;h,k>l. 2 t Proof: First note that MM = tu < >, since MU = Mt • t M = tM • t M = t(M ° tM) = tu 3 2 2 that the formula holds for some h , k > l . T h e n p(h+l) (k) M = otu< >)u< > h u k = (U o t p ( h ) ) = Mt o t M < > t o t h + l p ( k ) = Mt «t(M - Mt o t ( M < > M = Mt « t M = that is, ( t o t h+lp(k) h ( h > h 2 tM ( h + k ) , t« t U h ( k > ( h + k _ 1 ) ) ( k ) ) ( 3 >. N o w assume t p(h) (k+l) u (u luWt) _ M - KM o Ot)t)o n(h) k+l ( h ) M t = tu » t M < H • p(h)tk+l = tM o(tp(*> o u( >t )t = tM » M = tM • p ( = Mt op (h+k-1) |2 = p k h ( k ) (h+k) h + k M ( h ) t -D t 2 tM< >. h+k t = k 157 Lemma 14 For an idempotent monad (B ,t ,n ,M) in a 2-category A, we have the relation ^(h+D^k _ k (h+l) h+l n M •t :t k + 1 ;h,k>l. r k (h-k+i) if t M . T\ h > k > if h<k ; h,k>0. K _ H Proof: If h=0 or k=0, the relation holds trivially. For h=l and k=l, we have TIM =r\\ • M = t and MTI « = tT\ • M = t 2 For h,k>l,wehave p(h+l)^k 2 = ( y .o (h) Q ^ k - l u = (tn °M • M t ) n (h) = (Mn •M On ~ (h) k k_1 1 = M tn = tM n . (h) k-1 (h) that is, B 1 t »• B t h + 1 •B t k t k-l t k_1 jk-1 t Using this result repeatedly, we obtain the required formula for p < h + 1 the same formula for T\ p (h+i) > Ti . A similar calculation gives k • k Let A denote the quotient category of A defined by introducing into each non-empty hom-set of A the equivalence relation which identifies together all the morphisms in that hom-set, so that each non-empty hom-set of A contains a single morphism. (The objects of A are the same as those of A, namely all the finite ordinals.) In particular, for n , k £ 0 , every morphism n morphism n+k > n+k is identified with n+kT\ and every > n+1 is identified with n+p * ) . Then, denoting the equivalence class containing a k morphism £ by [ f ] , we have [n+kT\]= [kT\ +n] and [n+p * ]=[p"( +n]. k ) k> The operations of "+" and composition in A induce well-defined operations of "+" and composition in , so that ( A ,+,0) becomes a strict monoidal category. W e shall show that idempotent monads can be regarded as A-algebras. Where there is no possibility of confusion we drop the parentheses [ ] from the notation. We adopt this convention in the statement of the following lemma. Lemma 15 In ( A ,+ ,0) the following relations hold for h, k>0 . (h+kT\)h.T[ (i) (ii) (iii) TJ(h+l)( TJ(k+l)) h+ p" (h+1) (l+kT\) = = (h+k)T[ TJ(h+k+!) «= 1 (iv) h+kri = kT\+n (v) h+p"<> = 7 = k+1 (vi) k (l+kT\)TJ ( k + 1 ) ( k ) +h 159 (vii) hTi+kTi (viii) TT<> +U< ) h ]I (ix) ( h + 1 ) k +kTi = (h+k) T[ = l+7J(h+k-l) «= kT\+M" = [h+7j (h+1) ( h _ k + 1 ) L (k-h)n if h>k, if h<k. Proof: These relations clearly hold because there can be at most one morphism between any t w o objects o f A. • Note that (i),(ii) and (iii) actually hold in A . Composition in is determined by the relations (i),(ii),(iii) and ( v i ) , or, more precisely, by the obvious "translations" o f these relations obtained by adding an n to each factor w h i c h occurs. For example, ( v i ) implies that (n+l+kn)(n+Tr (k+1) ) = n+k+1. Similarly, the operation " + " is determined by the other relations. Observe that all morphisms o f A objects n>l o f A except for k "n.: 0 > k, k > 0 are isomorphisms. Hence all the are isomorphic to each other, w h i c h means that the skeleton o f A t w o objects 0 , 1 and w i t h a single non-identity morphism 0 is the category 2 w i t h • 1. Proposition 16 Let be (B ,t ,T\,U ) an idempotent monad in a 2-category A. Then there is a unique monoidal functor *:(A,+ ,0) such that $(1) = t, $("ri) = -n, and $ (TT) = > A(B,B) u. ErQQf: In order that $ becomes a monoidal functor we must set # (n) = t ,<Kn+kTi) = t T \ n <Kn+u< >) = t u k n ( k ) n k and for n, k > 0 . W i t h this definition, all the relations o f lemma 15 are preserved under Since these relations determine the structure o f (A,+,0) as a monoidal category, it follows that $ is indeed a 160 monoidal functor. For example, if p>q>r>0, the unique morphism | :q the unique morphism 5 : r r » r is |=r-l+p <<J r+1 > and > p is 5 =r+ (p-r) T[. <*5 5 0 5 is the unique morphism q $(?) = t n r p _ r > p , that is, 5 ° f =q+ (p-q) T\, hence $( S T) = t^riP-q. Now 0 and$(f) = t - p(q- >,so r r+1 1 4>( 5") • $(T) = t TiP- o tr-l (q-r+l) r r M t ( ts-r-nP-s • r i r tq-nP-^ • t r i 3 r t^TiP ^ • f - = < r - 1 q - r ) • t -r (tTr5~ t 0 r - 1 r r _ 1 p (q-r+D p (q-r+D- • p(<3 -r+1 >) $(?°T). The other cases can be checked in a similar way. We now check just one case of the preservation of "+" in detail. Suppose that p>q>0 and r>s. The unique morphism | : p T=s+(r-s)r\- T+T:P+S On the other hand » q is ?=q-l+p (p-q+D and the unique morphism "5 : s » r is » q+r isq+r-l+U<P J- ),So4 (T+T) = t J p (P+s-q-r+l) _ +s_c $("!) $(T) 0 = t q_1 > :r+1 M (p-q+D o t r i s c +r_1 _ q > r r - s jq+s-lp(p-q+l) ^ r - s t q+s-l r-s (p-q-r+s+1) t u s i n c e p _ s ^q+r-lp(p+s-q-r+l) Hence $(f) o $( 5 ) = $ ( 1 + 5 ) . • Let A be a 2-category with tensor products. Then, given an idempotent monad ( B ,t ,T[,u) in A,we have a corresponding monoidal functor $ : ( A,+ ,0) » A ( B ,B ) . Let p : A ® B > B be the corresponding 1-cell. Then p is the structure map for a A -algebra ( B ,p). Thus we see that idempotent monads 161 can be identified with the objects of the 2-category A -Alg( A). Identifying Mon( A) with A -Alg( A) in the manner described in chapter II, we can regard A-Alg( A) to be a sub-2-category of A-Alg( A); indeed, it is a "full" sub-2-category of A-Alg( A)=Mon( A). The inclusion 2-functor A - A l g ( A) induced by the quotient functor Q: A •* A-Alg( A) is > A in the following way. If (B,p )is an idempotent monad (A-algebra) with structure map p: A ® B » B, then its structure map as a monad (A-algebra) is given by the composition Q® 1 A® B If (h ,<x): (B ,p) „ i ® B- p B » (B' ,p') is a morphism of idempotent monads, then its image in A -Alg( A) is (h,oc(Q® 1 )): (B,p(Q® 1)) A® B » ( B' ,p'(Q® 1 )), as given by the following diagram. Q® 1 p 1 1® h A® B' Q® 1 The image of a 2-cell is obtained in a similar way. A Soft Adjunction which has a Lifting Our first example of the lifting phenomenon is provided by a para-soft adjunction analogous to the example considered twice before in chapters I and II. We have to change things a bit so that the construction will work. Specifically, we replace M o n ( A ) b y A - A l g ( A ) , that is, we restrict to the (full) sub-2-category of Mon( A) whose objects are idempotent monads. LetF :A 0 > A-Alg( A) be the 2-functor defined by F A= (B ,p ) where p : A ® A 0 0 0 >A is the structure map for the trivial idempotent monad structure on A . F is defined on 1-cells and 2-cells in the 0 obvious way. Let U : A - Alg( A) > A be the evident forgetful 2-functor. Then we have a para-so ft adjunction (F ,U,T|o,Eo,ro,So) where T| = 1 ands = id. 0 0 0 162 For an idempotent monad (B ,p), E ( B,p) = (t,"p"):(B ,p ) 0 idempotent monads (h,"oc"): (B ,p) > (B ,p). For a morphism of 0 > (B',p'), E ( h,"oc") is the 2-cell between morphisms of monads 0 given by the 2-cell t = pad) B •B cx B' B' V = p'o-(l) in A. For an idempotent monad ( B ,p) = (B ,t,ri,M), r ( B ,p) is 0 1 The "multiplication" for the natural monad structure on (B ,p) = (B ,t ,T\,p) is given by the 2-cell TVjlKB.p) U(B,p) UE (B,p) 0 • UF U(B,p) • U(B,p) 0 T| UF U(B,p) 0 Tl U(B,p) 0 0 T| T| U(B,p) 0 0 0 = id = id UF U(B,p) 0 TVjU(B.p) T| UE (B,p) 0 UF UF U(B,p) 0 S 0 UF UE (B,p) 0 UF U(B,p) 0 0 UE F U(B,p) 0 0 ue e (B,p) 0 UF U(B,p) Q UE (B,p) 0 0 UE (B,P) 0 U(B.p) Thus we see that the natural monad structure on U( B ,p) = B is just the original monad structure (B.t/ri.u). Now suppose that A has Eilenberg-Moore objects so that there is a lifted 2-functor 0: A - Al g( A ) > A associated with the soft adjunction ( F , U , T ] , E , r , s ) . Then we have 0 0 0 0 0 U( B ,p) = B with the obvious extension to 1-cells and 2-cells. Indeed this 2-functor is just the restriction to A -Alg( A ) of the Eilenberg-Moore 2-functor V: Mon( A ) > A. There is a para-natural adjunction u 0 t h v e whose value at an idempotent monad is the canonical adjunction f B n ' t u € B . Let Q denote the composite para-natural transformation U £ ° T) U: U 0 0 whose value at the idempotent monad (B ,p) is the universal t-algebra 0 > U. Then there is a We now check the coequalizer hypothesis for the construction of a lifted soft adjunction. Thus we consider the two modifications For an idempotent monad (B ,p), a ( B ,p) is the 2-cell in A -Alg( A ) given by 0 t, u ) where p is the structure map for the trivial idempotent monad structure in each case. 0 On the other hand, b ( B ,p) is 0 165 (B,p ) 0 ( t ,V) ' ( B ' P ) . To check the first part of the coequalizer hypothesis we need to find a coequalizer for these two 2-cells in >-Alg(A)((B,p ),(B,p)). 0 Now Ua (B ,p) and Ub ( B ,p) are the 2-cells 0 0 t u tU 2 15 which have a coequalizer in A( B ,B) given by the split fork Ut tu 2 tu associated with the t-algebra ( u ,5) and split by TlU TltU tu t u2 Proposition 17 ut (t.V)tu (t,V)u (u,"5") t5 is a split fork in A-Alg( A)( ( B ,p ),(B ,p)), (t.V)tu 0 T(lU split by TlU (t,V)u (u,V) Proof: Because (u,5) is a t-algebra, it is immediate that (u,"5"): ( B ,p ) 0 A -Alg( A). Then ?: (t ,"u")u > (B ,p) is a 2-cell in > (u ,"5") is a 2-cell between morphisms of idempotent monads since B u >B t * B id T\U:(U,"5") > (t,"u")u is a 2-cell in A-Alg( A) since 1 using the relation T\t = tT\. T\tu:(u,"5") > (t,"u")tu is a 2-cell in A-Alg( A) since 167 • using the relation p t = t p . Note that the fact that (B. p) is an idempotent monad is of crucial importance in the proof of this last result. Because the coequalizer of this proposition is a split fork, it is easy to see that the the second part of the coequalizer hypothesis, namely the naturality condition, is also satisfied. Corollary 18 Let h: A > B be a 1 -cell in A. Then the coequalizer diagram of proposition 17 is preserved under the induced functor F h*:4-Alg(A)((B,p ),(B,p)) 0 0 * &-Alg(A)((A,p ),(B,p)), 0 that is, (t.V)tuh (t,V)uh t?h * (u,V)h 168 is a coequalizer diagram; indeed it is a split fork, which is split by (t,V)tuh«- rituh Tilth (t,V)uh « (u,V)h. • Since the preceding results show that the soft adjunction ( F ,U ,T) ,£ ,r ,s ) satisfies the coequalizer 0 0 0 0 0 hypothesis, it follows that there is a lifted soft adjunction (F ,0, T], £ ,r,s). As one would perhaps expect, we 0 shall see that this lifted soft adjunction is precisely the evident strict adjunction (F , U, T), £) with T) = 1. 0 That T| = 1 follows since, according to the general construction of a lifted soft adjunction, for an object A of A, T| A: A > 0 F A is constructed from the 2-cell 0 T| UF A 0 U£ F A 0 0 which is the identity 2-cell on 1 ^: A The horizontal counit £ : F 0 o 0 » A. > 1. For an idempotent monad (B.p), £ :F 0(B ,p) o »(B,p) is (u,"5"):(B ,p ) » (B,p). 0 A. According to the general construction of a lifted soft adjunction, there is a modification n : £ ° F V 0 whose value at an idempotent monad (B ,p), 0 0 * > £ F v(B,p) e (B,p) 0 F 0(B,p) 0 • F U(B,p) ; o > (B,p) 0 | n (B, ) 0 P E(B,p) is the 2-cell (B,p ) (t,V) (B,p ). 0 0 (B,p) (u,V) > (B' ,p') be a morphism of idempotent monads. Then Let (h ,oc): (B ,p) (t,V) e (B, ) 0 P F U(B,p) • (B,p) 0 F U(h,a) 0 (h,oc) E (h,a) ^ is 0 FU(B',p')- h (h,oc) oc(l) (B;P') (B',p') 0 (B,p) e (B',P') 0 According to the general lifting construction, E(h ,oc) is obtained from an appropriate coequalizer diagram and then it fits into the commutative square EotB'.p'JoFoVCB'.pOoFoOCh.oO n (B',p') °F 0(h,cx) 0 o 0 E(h,oc) E (h,oc)°F v(B,p) 0 0 (h,rx)oE (B,p)oF v(B p) 0 E(B',p')oF D(h,cx) 0 > (h,a)on (B,p) 0 (h,oc)°E(B,p) Using the evident splitting we see that £ ( h ,oc) is (rToO (B,p )- (B',P ) Q 0 id (B',p ) (u,V) 0 (t'.V ") (t,V) (i) cx id. (B,p) (B'.p') (h,a) Hence £ : F 0 > 1 is strictly natural. o The vertical unit r: 1 > U£ °T)0. For an idempotent monad (B,p), ftB,p):(B,p) » Cl£(B,p) °T|0( B ,p) is constructed from the 2-cell U(B,p) V(B,p) U(B,p) T) U(B,p) 0 T| U(B,p) 0 r (B,p) 0 UF U(B,p) 0 UF V(B,p) UF U(B,p) u 0 0 U£ (B,p) 0 1 Un (B,p) 0 U£(B,p) U(B.p) 171 This 2-cell is 1 Hence r\ B ,p) = id. The vertical counit 8:£F O °F o T|0 * 1. The vertical counit s A : E FA ° F T| OA 0 0 » A, evaluated at an object A of A, is obtained from a certain coequalizer diagram involving two 2-cells whose vertical composition with s A coincide. Then sA fits 0 into the commutative triangle 172 Now n FQA = id, since the universal 1 ^-algebra associated with the trivial idempotent monad F A = 0 0 (A,p ) is 0 Thus we see that sA = id. By restricting the example of chapters I and II to idempotent monads we see that the soft adjunction ( F0,U,T|0,e0,r0,80) can be constructed from the strict adjunction ( F ,U,T) , £ ) by attaching via the 0 para-natural adjunction (dp, v ,h ,e): U > 0. The preceding discussion shows that the lifting construction retrieves the original strict adjunction (F ,0, T), £). 0 To complete the discussion of this example we note that in this case the modification isomorphisms of propositions 9 and 10 are identity modifications. For an idempotent monad (B ,p) = (B .t.Ti.u), the 2-cell 173 F f)U(B,p) F U£ (B,p) 0 0 F U(B,p) 0 * F OF U(B,p) 0 0 * F U(B,p) 0 0 £F U(B,p) sU(B,p) 0 E(B,p) P (B,P) 0 F U(B,p)0 (B,p) £ (B,P) 0 (B,p ) (B,p ) 0 0 (u,"5") id (B.p.) — (B,p) (t.V) 0 (t,V) (B,p ) | id 0 (B,p) (t,V) It follows that q (B,p) 0 F U(B,p) 0 FoTloUCB.p) F UF U(B,p)' 0 0 Fue(B,) 0 id 0 0 id F UF V(B,p) 0 F U(B,p) P 0 F v(B,p) \ £ ( , p ) 0 0 B F f|U(B,p) 0 n (B,p)J 0 F 0F U(B,P)o O F U(B,p) " (B,p) 0 F U£ (B,p) 0 0 £(B,p) = id, also. We can see this directly since the above 2-cell in A -Alg( A) is given by the 2-cell 174 IV. Commutative Monads A t :B commutative monad » B and 2-cells T\ : 1 (B,t,Ti,p,X) in a 2-category A consists of an object B of A, a 1-cell > t, p : t > t and X : t 2 2 (illustrated by the corresponding commutative diagrams) hold. (CM1) p • Va = p • Tit = id tTl lit (CM2) (CM3) (CM4) X 2 = x o x = id tX«Xt®tX = Xt«tX«Xt » t such that the following relations 2 177 There are some obvious redundancies in these relations. In view of (CM3), either part of (CM5) implies the other; in view of (CMS) and (CM6), either part of (CM1) implies the other. Note that an idempotent monad is a commutative monad for which X = id. For an example of a commutative monad defined on a large category let G be an abelian group and let t: Set > Set be the endo-functor of the category of sets given by tS = GxS. Define natural transformations "n.: 1 set and u : t * t > t as follows: 2 —» G x 5 -» (e,x) T\5:5XH p S : G x S x S- —> (g,g',x) i— where e is the unit element of G, GxS -» (gg'.x). It is well known that this defines a monad ( t , T i , p ) on Set [CWM]. Now define a natural isomorphism X:t > t by: 2 2 XS:G x S x S -* G x S x s -» (g'.g.x). (g.g'.x) i — Then (Set ,t ,Ti,p ,X) is a commutative monad. Let Pl denote the category whose objects are the finite ordinals functions. ( 0 0 ) is a monoidal category where + is defined exactly as it was for A , that is, + is defined on objects by ordinal addition and for two morphisms 5 : m |+5 : m+n and with morphisms given by » m' and 5 :n > n', » m'+n' is given by (f+J) (i) = I" f ( i ) if0<i<m, .m'+ 5 (i-m) if m<i<m+n. There is an inclusion functor A Along with the morphisms T\ :0 attention the isomorphism X :2 > D which is a monoidal functor ( A , + , 0) > 1, p :2 > (D,+, 0). » 1 which generate A , we single out for special >2 given by X(0) = 1 and X (i) =0. all 178 We can represent morphisms of fl by means of "arrow diagrams" just as we did for A. X :2 Thus > 2 is represented by the picture The morphisms T\ , u and X satisfy relations corresponding to the relations (CM1) to (CM8) for a commutative monad. (Di) 7(i+7> -jTrn+i) = i (D2) 7(i+7) = 7(7+D (fl3) x = Io x = 2 (04) (1+X) (X+l) (1+X) = (X+l) (1+X) (X+l) (05) X(i+n) n i ;T(n+i) = i+n (f!6) 2 = : + j j o x =TT (Pl7) (7+D (i+X) (X+i) = x (i+7) (H8) d+7) (X+i) (i+X) = X(7+D We shall show that the special morphisms J\, p and X generate D as a monoidal category subject to the relations (fl 1) to (Pl8) and also that Pl is a model category for the structure of a commutative monad in the same way that the simplicial category A models the ordinary monad structure. Proposition 1 Any morphism g : m — — • n of D has a unique factorization T= where f A :m T f o A P > n is a morphism of A and fp : m additional property that if i<j and = T(j), > m is a permutation with the then fp(i) < fp ( j ) , that is, fp does no change the order of points which have the same image under or, more simply, fp has no "unnecessary switching". We call f p the switching part of f and f the monotonic part of T ; we call the factorization of the A proposition the canonical factorization of the morphism f. Pioof: First we describe a method of constructing the arrow diagrams for £ and f p. Take each point i of n in A turn. If the inverse image of 0, ( f ) - 1 (0), contains m points, introduce m points into the domain of FA 0 0 and draw arrowsfromthese points so that these arrows all come together at 0. In general, if ( f~) (i) contains _1 rc^ points, introduce m points into the domain of £ A above any points already there and draw arrowsfromeach ± of these points to come together at i . Having constructed £A in this way, we obtain f p by connecting the points of ( f ) ( ? A ) b y "parallel" arrows. Thus for _ 1 (i) with those of 180 we obtain the factorization For a formal description of | and |p, let i : 1 > n denote the injection given by i (0) = i A and let :m • m denote the composition of the unique order preserving bijection ± > (|) (i) with the inclusion ( J ) - 1 - 1 > m. For each i we have a unique morphism (i) > 1 and the diagram u < i) : m.^ m r m > n A. k 1 m± > 1 TT i {m commutes, | ^ : m | ^ |p : m m + 0 = Tj< o> m ) » n is then defined to be the sum + Tr< l> m + + "jl'ron-l* N : rtiQ + m x > n. + . . . + rtv,-! > m can now be defined as follows. Consider the codomain of |p to be the ordinal sum where m.^ is the number of elements in (T) +. . . + restriction of |p to ( T ) " (i) .that is, Tp | ( | ) ( i ) 1 - 1 :(|") (i) -1 -1 (i) for each i . For each i let the >m + 0 + . . . + rc^^, be the unique order-preserving injection into the ith summand. |p is clearly bijective, as required, and by definition, has no unnecessary switching. • We now look for generators of the permutations in Pi. For h>l, k>l let X * ' ' :h+k h k > h+k be the permutation given by \(h,k) ( i ) i+k ifO<i<h-l, i-h ifh<i<h+k-l. h+k-1 \(h,l) : h + 1 -* h+1 is given by X < h , l > ( i ) i+1 ifO<i<h-l, 0 ifi=k. and X^'^ik+l > k+1 isgivenby X(l.fc) , = (i k if i=0, k-1 ifl<i<k. 182 In particular X * ' * = X. 1 1 Therelation X ^ ' 1 * = ( X + h - 1 ) ( l + X + h - 2 ) follows immediatelyfromthe ( h - l + X ) diagram Similarly, X ^ 1 ' * * Forexample, = ( k - l + X ) (k-2+X+l) X* ' * 2 1 = (X+k-1) . and X < (X+l) (1+X) x ( X + l ) so the relations (fTTjand (f|8) = (1+X) ' > 2 can be written in the form: ( D 7 ) * (7+D (f]8)* (l+p) X ( 2 - > X * - 1 ) 2 = I d + j T ) , = X(p+l) . 1 We have the recursion formulas: X < h + i , i > = ( X + h ) Xd,k+1) _ ( k + d + X ^ ' ) 1 ) X ) ( X(l,k) , + 1 ) ; which could be taken to be the formal definitions of X < ' > and X < • > in terms of X. We adopt the h 1 1 k 183 convention that X < ' ° ) = 1 X * ' * = l . By the well-known result that any permutation can be written as a 0 1 composition of transpositions, it is clear that any isomorphism(permutation) in D can be built up from X's and identities using the operations "+" and composition. We wish to show that the composition of permutations is determined completely by the relations (f|3) and (P|4). In order to do this we need to describe a "canonical form" for a permutation constructed from X's and identities. We simplify the diagrammatic representation of such a permutation by replacing each instance of X or "cross-over" by a "filled-in" rectangle and leave regions corresponding to parallel arrows blank. Thus, for example, X < ' > is represented by the diagram h hi • 1 : The idea of this representation is to divert attention from the internal structure of each "box" in order to concentrate on the algebraic behaviour of permutations. We still take account of the monoidal category structure of H by "pasting" horizontally to represent composition and pasting vertically to represent +. Hence the relations (P13) and (fl4) in diagrammatic form are: (Tl3) (04) We call a permutation a: h+k +m+1 -> h+k+m+1 of the form cr = h+X ' + m , where k>l, an elementary permutation. It is a special type of cycle. (Jc 1) 184 h+k+m We define the height of the elementary permutation IT = h+X^'^+m tobe#"(r7) =h+k+l. Proposition 2 For any non-identity permutation T'-n permutations o" , <Sp-i, p o^, T- • n where n>2, there are unique elementary such fnaf Vp ° O p - l ° ° and ^/"(Fi) <#("rl ) for i=l, . . . , p - l . i+1 We call such a representation the canonical factorization of the permutation If Proof: The proof is by induction on n. First note that the result is immediate for n=2 . Suppose that any permutation n g: n+1 > n has such a canonical factorization. Given a permutation » n+1, consider the restriction of g to n, g j n: n > n+1. There is a j in the set n which is not in the image of | j n, namely j= g(n) . Let 0 : n+1 > n be given by = [ i - l if j<i<n, L i ifO<i<j, that is, 6 = j + u + n - l - j . Then g'= 6°( g | n ) is a permutation which can be pictured by the diagram 0 — 0 e in which the arrow originating at the point n is considered to be omitted and the shaded region represents the remaining arrows constituting f | n . 5' is obtained by "erasing the arrow" of F which starts at n and then "closing up the gap" in the codomain. By the inductive hypothesis 5' : n F= Then g'+l: n+1 F * n can be written in canonical form Q o 7f _ o q oFL x • n+1 has a canonical factorization obtained by adding 1 on the right of each factor in the canonical factorization of f ', thus: F + l = < Oq +D ° ( O q - i +D ° ° ( F +1) . x If j=n, this gives the canonical factorization of | . If j<n, we have F o ( j X ( n - j , l ) ) o (F+l) + = (j+X^-J- )) 1 o ( F +1) Q o ( F _ ! +1) Q o ......o ( F +1) . X 186 n n-1 **************** * \ \ \ \ \ \ \ \ \ **************** • \ \ \ \ * * * * • \ \ \ V * * • \ \ \ \ * \ * \ \ \ \ \ \ ' \ . \ \ . \ \ \ . \ \ \ * * * * * * * * * * * \ \ \ \ \ \ \ \ \ \ * * * * * * * * * * * \ \ \ \ \ \ \ \ \ \ ' •* ************** ' \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** **************** **************** ******* JE** ******* •\\\\\\>\.\.\\\\\' **************** • XS\\\\\\\\\\\\' **************** • \\\\\\\\\\\\\\" **************** • \\\\\\\\\\\\\\' **************** ' \\\\\\\\\\\\\\' **************** ' \\\\\\\\\\\\\\.' **************** • \ \\\S\\\\\\\\\' **************** **************** j + 5r Since j+X ( N _ <n-j,l> 3 » i) is uniquely determined as the composition g ° ( g'+l) , we have the canonical _1 factorization in the second case. • Examples 1. LetjM » 4 be the permutation given by | ( i ) = 3-i.Thus £ reverses the order of the elementsof4 = {0,1,2,3}. f" has the canonical factorization g~= X °1 2. X^'^rk+l ( 3 °2 ' X ) (X~ ' (2 °"3 * k+l has the canonical factorization = (k-l+X) (k-2+X+l) which is the formula given previously. (X+k-1) ( X+2) . 187 k k-1 We can picture an elementary permutation 0" = h+X < ' > +m by a diagram of the form k 1 h+k+m. h+k ********** \ \ \ \ s \ \ \ \ \ \ *********** \ \ - \ \ N \ \ * * * *!•*. * >-W> \ \ \ \ ******* * * *\* * * *\ *\ *\ * \ * \ \ \ A \ \ \ \ \ \ \ \ * * * * * * * * * * , * * * * * * * * * * , \ \ \ \ \ \ \ \ \ \ * * * * * * * * * * * in which the shaded region represents X < ' * and the unshaded region corresponds to "parallel arrows". Again k x the idea is to divert attention away from the internal structure of X 1 >, but still retain the geometrical representation of the operations of composition and + by means of horizontal and vertical pasting. The canonical factorization \= a i = n i + o" ° cr _i ° p p ° o~i of a general permutation | : n > n , where X ^ i ' * + m± andhi+kj^+nii = n fori = 1 , 2 , . . . , p , can then be pictured as follows . 1 188 h j+k j+m ^ i h v x x x x x x x x X X \ X X X X h +k 2 + k i + h +k +m i m p p p 2 x x x x x x x x v X X X X X X X x x x x x x x x v X X X X X X X ^/x^x"fI f ^ i / i ^ X h l + k l ' X X X X X X X X \ X \ X \ \ • X X X X X X > X X X X \ X X • X X X X X X X * x x x x x > X x'x x x x x x x x x x x 'x ' XZ>X X X X X X X \ x x x x x x x x x x x x x x x x x x x x x x x x x • X X X X X X X X X X X X X X ' X X X X X X X X X X \ \ X \ ' X X X X X X X X X X X X X X We now proceed to show that any permutation generated from X's and identities using "+" and composition, can be put into canonical form by means of formal manipulations using only the relations ( 0 3 ) and(fl4). Lemma 3 The relations (03) and (04) imply that the following relations hold for h > 0 and k (03)* ( X + h ) (04)* ( h + X + k ) X<h+l,l> =1+ X < h , l ) \(h+k+l,l) = X < h ( + k + 1 ' 1 > ( h - l + X + k + 1 ) . PjQQf: (03)* ( X + h ) X(h+i,D = = 1+ ( X + h ) ( X + h ) X* 1 1 ' * 1 using The proof can also be given in the following diagrammatic form. (1+ (03). X ( h ' x > ) by the recursion formula 189 (f|4)* We give the proof in diagrammatic form. (The second step uses the relation (f|4).) • Lemma 4 Let g= 0" ° 2 o~ :n 1 > n where rj-^ and cr are elementary permutations and 2 0{( rj ) > !H( cr ) . Then, using the relations (fl3) and (f|4), we can obtain one of the follow 1 either 2 two elementary permutations ' and F ' with Fj ) < M( F ') = M( F ) and pr a single elementary permutation F w/Yh Proof: 1 2 2 F) = J^Fj) and |~= F = F x 2 ° F . x Lei = hj_+X< i' >+m fori=l,2, where k^l.Then we have h ^ k ^ r r ^ = h +k +m = n-1 k 1 i 2 2 2 and h2+k Si +k . 2 1 1 Case (i): h +k <h . 2 2 1 In this case cr only moves points which are unaffected by oyso and 0" can simply be 2 2 interchanged to obtain the result, that is, set a ' = cr and a ' = c y At a purely algebraic level, only the x 2 2 monoidal category properties of + and composition are involved. Case(ii): h <h <h +k . 2 1 2 2 By successive applications of the formula (04)* followed by one appbcation of the formula (03)* we obtain ? 2 o ?! = (h +X< 2' )+m )(h +Y( l' >+m ) k 1 k 2 2 1 1 1 = (hi+l+ X ^ l " - 1 ) + ) (h + X ^ " ' > +m ) 1 1 mi 2 x 2 h +k -l 2 2 Case (iii): h <h 1 2 By successive applications of the formula (fl4)* we obtain F 2 o 7j = (h +X~< 2' >+ni )(h +X< l' >+m ) k 2 = (h + x 1 k 2 1 1 1 D 4m{) (h -l+ X< 2' > +m +l) k 2 1 2 Case (iv): h = h +k . x 2 2 cr 2 o o-j. = (h^X^l^l"^' )^) 1 = F. h +k +m 2 h l + k 2 2 l h +k 2 2 By repeated applications of lemma 4 we obtain: P r o p o s i t i o n5 Let T~ F q ° ^q-i ° ° 0"! where (j ± is an elementary permutation for i = l , . . . ,q. Then fhere are elementary permutations F j 'forj=l, . . . , r, where r < q , such fhaf 194 5 and = 0" ' V _i ° R o T #(Fj') < # ( F j + 1 ° O"! 1 ' ) for j=l, . . . , r - l , that is, such that this new factorization of is canonical. Furthermore, this canonical factorization can be obtained by purely formal algebraic mean relations (f]3) and (fl4). • P r o p o s i t i o n6 (i) The permutations in f] are generated by \ and identities using + and composition. (ii) Let |: n > n and 5 : n » n be two permutations given in canonical form. Then composite permutation 5 o g can be obtained in canonical form by purely formal algebraic m using relations (fl3) and (fl4). Proof: (i) follows immediately from proposition 2, or alternatively, is a consequence of the standard result that an arbitrary permutation can be expressed as a composition of transpositions. (ii) follows from proposition 5. • We can now describe a canonical form for a general morphism f : m 5 = 5A ° 5p where £p is the switching part of f and | A > n of H namely: is the monotonic part of £ with each of |p and T A given in their respective canonical forms, that is, | ^ = 7J(m ) + TJOti!) 0 where m is the number of elements in ( ( i ) or ( f ) ± F P = F p o F _! p o + _ 1 + TJ(mn-l), (i) for i = 1 , . . . n, and o v lt where each cr j is an elementary permutation and 9<( 0" j) < M( F j ) for j = 1 , . . . , p - 1 . + 1 We shall show that the composition of two arbitrary morphisms of f], each given in canonical form, can be obtained (in canonical form) by purely formal algebraic means using the relations (Dl) to (fl8). We make a simplification in the diagrammatic representation of morphisms of A generated by Fand 195 -> 1 by the diagram where each shaded triangle corresponds to an instance of p and the unshaded region is considered to contain parallel arrows. Hence this diagram corresponds to the formula: 7<> m p <> ;m m MU+p) (m-2+7). » 1 may also be represented by the diagram where the unshaded region is now considered to contain arrows sloping downwards parallel to the top side of the triangle. This diagram corresponds to the formula: 7J(m) = ]T(7J+i) The associativity relation: (02) Fd+TT) can be represented pictorially thus: = P"(P+D, (p+m-2) . 196 More generally, the equality of the two expressions for p ( > given above can be established by repeated m applications of (02). The relations (06), (f|7) and (08) correspond to the pictorial relations: (06) (07) (08) Lemma 7 For m>0 we have (07)* \(l+p" (08)* )T(p" +l) = (l+'p< >)X"< ' >(m> (m) ) = (F^+Dll ' ", 1 m 1 1 m 1 (07)* is a formal algebraic consequence of relations (02), (05) and (07), while (08)* is a 197 formal algebraic consequence of (02), (05) and (08). Proof: For m=0 the formula (07)* is just part of (05) and for m=l it is trivial, hence we shall suppose that m>2 . That formula (07)* holds in this case is immediately clearfromthe folowing diagrams. m m In each diagram the same arrows are brought together. In the left hand diagram they are just brought together "sooner". We give two demonstrations that (07)* is an algebraic consequence of (02) and (07). (i) Direct algebraic proof by induction. The recursion formula: p (p +1) = p ( m+1 *, is a consequence of relation (02). Assume that formula (07)* holds for m. Then we have Xd+"p (m+1) ) = Xa+7> a+7 +i) (m) = (7+1) (1+X) (X+l) (l+7 +D (m) by(07), = (7+D (1+X) (7 +2) (X< ' )+1) (m) 1 m using the inductive hypothesis, = (7+1) (7 +2) (m+X) (X^-^+l) (m> = (7< >+l)X( ' > m+1 1 m+1 using the recursion formula for X < ' 1 m+1 '. (ii) Diagrammatic proof. 200 > h+l+m of the form V = h+p We call a morphism V :h+k+m elementary A-morphism or an elementary arbitrary morphism of A , | ; m monotonic ( k ) +m , where k>0, an As we have seen in chapter II, an morphism. » n, can be written in the canonical form P~ 0> + " p l T= (K where k± is the number of elements in ( f ) > v ( k + + "p< n-l> k (i) for each i , and so can be written as a composition - 1 n > v n-l v where each V.^ is an elementary A-morphism of the form l = + p( i.) k + m^. Indeed we have described a canonical form for such a decomposition using lemmas 11,5 and 11,7. As mentioned above, our intention is to show that composition in fl is determined completely by the relations (01) to(08). By successive applications of the formulas (07)* and (08)*, a composite morphism cr ° V, where a is an elementary permutation and V is an elementary A-morphism, can be written in the form ov" = CT where v' is an elementary A-morphism and V o cr o oF q l t is an elementary permutation for each i . For our general result we shall need to able to remove unnecessary switching from a morphism of the form V V i ° where the morphisms °^i ° °F l t are elementary permutations, the morphisms V j are elementary A-morphisms and we may assume that the composition cr ° v _i s s ° is in canonical form. In order to achieve this we shall need the formulae of the following lemma. It is easy to check that these formulae hold by drawing arrow diagrams, but since we need to show that they are consequences of the relations (Ol) to (08), this requires more work. However we shall simplify things a little, at the expense of consuming some space, by giving "diagrammatic" proofs. 201 Lemma 8 Let F = " X l ' > -i-m! bean elementary permutation and ( k elementary A-morphism, where h +k +m =h +k +m =n; h , 1 1 1 2 2 2 have the following expressions for v ° cr : n+1 (CM) V = h+ u < 2 1 x t k + 1 ) 2 +m 2 bean h , m >0 and k k > l . Then we 2 2 lf 2 > h +m = 1 . 2 2 If h <h and h +k <h +k , 1 2 2 2 1 1 v" ° F = (h^\< l- 2' >+m ) (h -l+7J"( l +m +l) k k 1 k 1 +1) 2 2 = F' ° \T', where F /s an elementary permutation and v' /s an elementary A-morphism. (In this case the elementary morphisms "commute" in the sense that at least we obtain an elementary permutation and an elementary A-morphism composed the opposite order.) // h S i andh +k <h +k , (US) 2 1 1 1 2 2 \T°F= (h +F l +rri ) = (k +1) 2 2 v! (In this case all the switching of cr is "unnecessary".) (PCM1) If h <h <h +k <h +k , 2 1 1 1 2 2 \T orJ= (h +F 2 2" l" l>+m ) (h +X< l" 2' >+h +m ) < h - l + F l l 2 > + 1 ^ + 1 ) (h +k h k h 2 2 h 1 1 ( h 2 2 + k _ h + 1 2 = v" ° F ° \T, x where V v° 1 2 , v are elementary A-morphisms and cr' is an elementary permutation such that x 2 <s' has no unnecessary switching. (In this case we have "partial commutativity".) (PCM2) /fh <h <h +k <h +k , 2 v" oF= 1 2 2 1 1 (h +M+m -l) ( h + X l l ~ 2 2 ' ) + m ) (h +F 2 +m +l). (h 2 2 +k h -k 1 2 (k 1 2 ) 2 (This is another case of "partial commutativity".) Furthermore, these relations can be obtained by purely formal algebraic means using the relations (fl2), (fl6) and Proof: (08). 202 Case (CM): h y h j and h +k.2 x i • Sh +k 2 h^+k 1+1^1 h +k +m 2 h l + k 2 2 lj : h +k 2 0 N 2 2 0 + M 2 203 using relation (fl8), 205 206 Hence V ° a = ( h ^ X < i 2' D +111!) (h -l+ p < i l> +m +l) k _K k 2 + 2 208 209 using relation (Pl6). Hence V* °F = Case (PCM1): (h +"u 2 ( k l + 1 ) +m ) 2 h <h <h +k <h +k . 1 2 1 1 2 2 = V. 212 Hence V ° a = (h + M < 2 h 2 Case(PCM2): h < h i < h 2 + k 2 + k 2 l- l _ h k 2 i i< h + k ) ( h l + \ (h -h ,1) +h x 2 ) (h -l+ y ( l l 2 > +m-,+l). h 2+m2 2 + k _ h + 1 216 Hence V ° cr = (h + u+m -l) (h + X (h +k -h -k , l) 2 2 2 1 1 2 2 ) (h + (j <2> +m +l). • K +rril 2 2 The relations of lemma 8 can be given in abbreviated diagrammatic form as follows. (CM) l + l m h +k +m 2 £2 2 h +n^ +K — (k^TS^ 2 2 h +k -l ->2 2 2 2 ^ x j 2 2 h h JJ h -l 2' +m l + k l ~2 K >w 2 (US) h +k +m 1 1 1 N. "2 2 H 2 + K 2 + M 2 h +k i 2 h l + k 2 l £-<k l) lr 2 2 h (PCM1) +m 218 hj+kj+mj h +m2 2 ^-(k^l) h +k2 2 h +k -l 2 2 ^-(n^-mi* 1) In each case all or part of the triangle is "moved to the left" and in so doing reduces the "size" of the square by an appropriate amount One can check that in the arrow diagrams corresponding to (CM), (PCM1) and (PCM2), when a triangle is moved to the left, it still brings together the same group of arrows; they are just brought together sooner. Note that the relation (fl8)* of lemma 7, whose proof was omitted earlier, is a special case of (CM). Proposition 9 Let ITA : m » n be a morphism of A given in canonical form and let 5p : m >m a permutation also given in the canonical form ? p where = F Q OCTq.! ° • ? r is an elementary permutation for each i and JW(F ) < # " ( F L Then there are indices i lr . .. Fp= ,i k iv/tf? OSi-j^ i I + 1 ) for i<q. < ij^q such that if 2 % ° V i ° o i i - T tfjen f o |p is the canonical factorization of f"= f ° £p tv/tf? monotonic part f^ and switching par A A |p (which now contains no unnecessary switching). Furthermore, this can be achieved by purely formal algebraic means using the relatio (06) and (08). Proof: The problem is to remove unnecessary switching from 5 p. Factor f injectiveand f is surjective. Then f = f A ° 5p = ?i ° fc ° 5pc W e 0 2 0 A as f = A Tc where Ti leave lj out of the considerations temporarily and work with the morphism f Q ° 5p, which can be pictured by the diagram 220 V /V : / where £rj has been factored (canonically) as a composition of elementary collapsing morphisms. Take each "triangle" in turn and use the relations (CM), (PCM1) and(PCM2) of lemma 8 repeatedly to move each triangle, or any "dissected part" of a triangle, as far as possible to the left Use the relation (US) of lemma 8 wherever possible to remove unnecessary switching and then bring the triangles back to the right of any switching by using the relations (CM), (PCM1) and(PCM2) in reverse. Note that this procedure can only remove complete elementary factors from 5p, so the resulting permutation gp will still be in canonical form. Also, because the factorization of 5p is canonical, any arrows which are brought together by a triangle which has to be "left behind" in the translation process do not cross each other at all before they come together. This is clear from the following diagrams. (PCM1) Thus a l l unnecessary switching will be removed by the procedure described. 222 Proposition 10 Let |": m > n and 5": n — — > k be morphisms of f] each given in canonical form. Then the composite morphism S ° 5 : m > k can be obtained in canonical form by purely formal algebraic means using the relations (Dl) to ( f l 8 ) . Proof: Write the canonical factorizations as f = | ° f p and S = SA° Sp where f p and f are the switching and A A monotonic parts of f respectively, while Sp and 5A are the switching and monotonic parts of 5 respectively. Then T ° T = T A T P ° I A Fp • We first compute S p ° 0 IA- 0 f has a (canonical) factorization A FA= where each v ± ^ V 0 P I 0 0 is an elementary A-morphism of the form v V i- = h± + p ^ i * + m.^ ± and Sp has a canonical factorization Tp = F ° Fq_! q o o F where each CT j is an elementary permutation and M( cr j) 5p° ?A = °q 0 °q-i 0 0 a i 0 v l t < p 0 cr j v p-i for j = 1, . . ., q - 1 . Then ) + 1 0 0 v so we can use the x relations ( f l 7 ) * and ( f l 8 ) * repeatedly to obtain Sp ° f in the form A 5p° where FA = V 0 V J ' O ......° V oF' s o Fg^" o o Fj', is an elementary A-morphism for each i and C j ' is an elementary permutation for each j . This involves the relation (D2),(n5), (fl7) and (08). This now gives S 0 f in the form "S°F= V o v^" o ^ - oF " o F o v V - -o 1 o Fi", where the Vi"and a j " are elementary A-morphisms and permutations respectively. The A-morphism V " o Vy.^" o u o can be put into canonical form v u v u - l i v using the relations (f~11) and (02), while the permutation a " v canonical form 0 0" _ " ° v 1 o Fj_" can be put into 223 ° 'v-l ° a l using the relations (Pl3) and (fl4). This permutation can then be modified to remove any unnecessary switching by using relations (fl2), (P|6) and (D8), so thatfinallywe have 5 ° F, in canonical form. • Proposition 11 Let (B ,t ,ri,p ,X) be a commutative monad in a 2-category A. Then there is a unique monoid functor $ : (fl,+, 0) -> A( B ,B) such that: $(l) and = t: B > B, $( ri) = n • 1 » t. <KIT) = M : t >'t $( X) = X:t 2 » t . 2 2 EKjof: Since (B ,t ,Ti,p) is a monad, $ is uniquely determined on the sub-monoidal category (A,+, 0 )by the conditions $( l)= t, <K T\) = T\ and <K P) = p. A general morphism ~%: • n of A can be written in m the form |"« 7<k ) + "p l> + + "p^n-l), <k 0 where is the number of elements in (fD (i) for each i and we have _1 $ ( D = 5«= P 0> ° p < l > o op(Vl):F k (k > t , m where p< i> = f ( " p i ) for each i . k ( k ) We needto defined on permutations sowe set $("X( ' >) = X ' > : t k 1 (k X(k,l) is defined recursively by •X<l'i>=X, X (k+l,l) k = X t which corresponds to the recursive formula for X X(k+l,l) Y ( k = X ^ ' ' is the 2-cell 1 ( +k) o t X (k,l) t • ': 1 (1+ x ( k , D >. 1 k + 1 » t k + 1 , where 224 k copies Then for an elementary permutation <T= h+X < ' > +m we must set $ ( a ) = t X < • > t and for an k arbitrary permutation \ : n = h±+ X < i' > k 1 k 1 m > n given in canonical form T= where h 1 +111^^ F q o F _! o o F q x for each i , we must set $(D- e ^CFj). 4>(F )» c^Fq.! ) o q By writing a general morphism of in the canonical form | = | ° F, p , we see that $ is uniquely A determined on D by setting <K?) = #( S^) • $(fp)Let I : n • n and 5 : m > m be two permutations. Then |"+ 5 = (n+ If) ° (J+m), hence, if % has the canonical factorization F, = cr ° ° r j while T has the canonical factorization q 5 = t r ° o t , we have x S~+T Now lt = (n+T ) r o (rH^) o o (F +m) © q ©(O^+m). cr+m) < #(n+ x ), so this is the canonical factorization of 5+5- Thus we have q x <KT T) + = $(n+ 5") $(T+m) e = t4>(5~) • <KI~)t n = m *(I)o$(5). Each of the relations (fl 1) to (fl8) has an analogue among the relations (CM1) to (CM8) given in the definition of a commutative monad. Let E be an expression for a morphism of fl obtained from the generating morphisms T\, p, X and identities using + and composition. This expression has an "image" in A( B ,B) under $ constructed in the analogous manner to E but using TI, U , X and powers of t instead of T\. M. X and identities 225 respectively, and the operations of horizontal and vertical composition instead of + and composition respectively. Any step in manipulating the expression E using the relations (Ol) to (08) corresponds to an analogous step in manipulating the "image expression" using the relations (CM1) to (CM8). Let %: m » n and £ : m > k be morphisms of fl. Write each of these morphisms in canonical form. Then, using the description of $ given above, we can obtain "image" expressions for $ (|^)and $(.5) as 2-cells in A( B ,B). By vertical composition of these expressions we obtain an expression for $( 5 ) ° $(1D. Accordingtoproposition 10, we can put 5 ° % into canonical form using the relations (Hi) to (08). Thus we can apply the corresponding steps to the expression we have for $( 5") • §C%) to produce an expression which must necessarily coincide with the image of 5 ° | under $ obtained using the description given above. Thus we have $( T ° T ) = <KT) • $(?). Let \ and 5 be any two morphisms of 0 with canonical factorizations \ = fp and 5 = 5~A° 5p respectively. Then T+T = (IA°1P) = so we have $ ( | ~ T) + + (?A°T ) P ( F A ? A > ° ( T P 5p), + = $(IA + + T A ) $(Tp Tp) 0 + = (*(|^)o $( 5 " ) ) » ( $ ( T p ) ° A = ($(f ) ° $ ( F ) ) ° A = $(D°<K?). P *(T )) P ($(? ))»($(T )) A P • The universal property given by proposition 11 gives a complete characterisation of 0 . Its objects form the free monoid generated by 1 under"+" and its morphisms are generated under"+" and composition from r\, u, X and identities subject to the relations (01) to (08). We now consider the problem of finding generators and relations for 0 using only the operation of composition. In order to do this we extend the ideas already introduced to deal with the corresponding problem for A . 226 A morphism of Pl of the form i+X+n-i-2:n where n>2 and 0<i<n-2 is called a primary » n permutation. The formula "X<*'1> = ("X+k-1) ( l + X + k - 2 ) (k-l+X) gives a canonical factorization of an elementary permutation h+X ( ' >+m as a composition of primary k 1 permutations. For a general morphism F,: m > n of D, we have the canonical factorization T= Ij ° lc ° T P where ?j is monotonic and injective, ?c is monotonic and surjective and |p is a permutation with no unnecessary switching. Each of these three factors then has a canonical factorization as a composition of elementary morphisms and then each of the elementary morphisms can further be broken up as a composition of primary morphisms. Thus we have a canonical factorization of F. as a composition of primary morphisms. We now list a number of relations for primary morphisms of fl which extends the list given previously for A . Again we classify these relations as being either essential or non-essential. Essential Relations for Primary Morphisms of D These are derived directly from the relations (fll) to (PI8) by adding an h on the left and a k on the right of each factor which occurs. Thus, for example, (Pl8) gives rise to the relation (h+l+"p+k)(h+T+l+k)(h+l+"X+k) = (h+"X+k)( h+p+l+k) (Pfl8) We designate the eight relations obtainedfrom(fl 1) to (D8) in this manner by (Pf) 1) to (Pf|8) respectively. Nonessential Relations for Primary Morphisms of 0. These are relations which arise from the monoidal structure of D. Just as we did in the case of the category A , we shall give the non-essential relations in a simplified form. The general form of each relation can be obtained from the formula given by adding an h on the left and a k on therightof each factor which occurs. 227 (s+n)( T[+S-1) = ( T l + s ) ( s - l + T\) 0TI9) (S+TDCU+S+I) = ("M+SXS+I+'M) (PfllO) (s+i+"X)("x+s+i) = (Y+s+i)(s+i+X) (pnn) (S+T[)( M+S-1) = CjI+s)(s + l+T\) (Pfll2) (s+TDCn+s+i) = (n+sXs-l+IT) (Pfll3) (S+1+T\)(X+S-1) = (X+s)(s+l+r\) (PfU4) (n+s+i)(s-i+X) (Pf|15) (s+"X)( T\+S+1) = (S+1+M")(~X+S+1) = (X+sXs+i+p") (PD16) (s+"X)( p+s+l) = (ir+s+i)(s+i+X) (Pni7) P r o p o s i t i o n 12 The (non-identity) morphisms of the category f] are generated under composition by the primary morphisms subject to the relations (Pfll) to (PD17). Proof: We show that these relations suffice to put any composition of primary morphisms into canonical form as a composition of primary morphisms. Firstly, any composition of primary morphisms can be arranged using these relations into the form 5 i ° I2 ° £3 W N E R E %2 ^ ?3 ^ compositions of primary injections, primary m collapsing morphisms and primary permutations respectively. Then we can put Ti»T2 and T3 into their respective canonical forms as compositions of primary morphisms. In the case of F.3. one can check that everywhere that the monoidal structure of was used in the arguments used previously to obtain the canonical form for a permutation as a composition of elementary permutations, the same result can be achieved by using the non-essential relation (Pfl 11). Finally, we can remove unnecessary switching from I3. Again one can check that the various manipulations used previously to achieve this only use the monoidal structure of in the way that it is recorded in the relations (Pf|9) to (Pfll7). • 228 Let A be a 2-category with tensor products. Then, given a commutative monad ( B ,t,ri,u ,\) in A,we > A( B ,B). Let p : P)®B have a corresponding monoidal functor 4>: ( f l , + , 0) > B be the corresponding 1-cell. Then p is the structure map for a fl-algebra (B ,p). Thus we see that commutative monads can be identified with the objects of the 2-category Pl-Alg( A). This automatically gives us the appropriate 1-cells and 2-cells for the 2-category of commutative monads. Let ( B ,p)= (B ,t,ri,p ,\) and (B' ,p')= ( B' ,t' ,p' ,X') be commutative monads. A similar argument to that given in chapter n for ordinary monads shows that a 1-cell ( h ,cx): ( B ,p) fl-Alg( A) can also be regarded as a pair ( h , o c ) : (B ,t,Ti,p,X) • (B' ,t' ,T[' ,p' , V ) where (1) cxd) = cxa(l):t'h t • ht.thatis, _ _ B cr(l) _ fl® B B' ( 1 ) ):(B,t,ri,p) cr(l) p B 1® h id such that (h,a > ( B' ,p') in ex. n® B ' P' » (B'.t'.iy.p') is a morphism of monads and t 2 We shall call either (h ,oc )or (h ,a < ) a morphism of commutative monads, hoping that it will be clear from 1> the context which of the two forms is meant fl-Alg( A) is a sub-2-category of A -Alg( A) (but not full with respect to 1-cells). The inclusion J: H-Alg( A) » A -A1g( A) is induced by the evident inclusion A » fl in the following sense. 229 If ( B ,p)= ( B (B ,t , T i , p ) . ,t,ri,u ,\) is a commutative monad, then its image in If ( h , o c ) : (B ,p) 1® A) is the monad ( B ,p( J® 1 )) = > (B' ,p') is a morphism of commutative monads, then its image in A - A l g ( A ) is (h,oc(J® 1 ) ) : ( B , p ( J ® 1 )) A A -Alg( ®B > ( B',p'( J® 1)), as given by the diagram J®1 ^ _ D® B p h id A ® B" n® B 1 j ® 1 P' The image of a 2-cell is obtained in a similar way. As mentioned earlier, any idempotent monad is a commutative monad. This fact corresponds to the existence of a monoidal functor Q': (D,+ ,0 ) quotient category of fl. If Q: A > ( A , + ,0 ), which can be obtained by regarding A as a » A is the quotient functor, we have the following commutative triangle of monoidal functors (A, + , o) Q (D. + , o) which induces the commutative triangle of inclusion 2-functors -Al g(A )- A-Alg(A) D-Alg(A) 230 V. Composite Monads In the monoidal category (D, +, 0), 0 is an initial object and for an object k of Pl the unique morphism >k is kri = k+k+ 0 +k ( k summands). The diagram k+kri k > 2k < is a coproduct diagram. For k>l, let p : 2k kT\+k k > k denote the unique morphism of f l such that the k diagram commutes. Thus p is a "codiagonal" or "folding map". In particular, p j is just p : 2 k M can be pictured by the diagram k 2k-l k-1 It is easy to check that for k+s=m, p" m = (p'j.+ p's) (k+\( ' >+s) s k Hence we have the recursion formulae Fk+i = (Hfc+u") Fk+l (k+X^-kJ+l), = <M + U") (1+ X^'^+k) . k > 1. 231 The diagram U +k k k+ Pk commutes, thus we see that (k,kri, p ) is a monoid in the monoidal category (Pl. +. 0). k Let A be a 2-category which has lax limits, or at least Eilenberg-Moore objects, and suppose we are ,\) in A. Let $ : ( Pl, + , 0) given a commutative monad ( B ,t » A( B ,B) be the corresponding monoidal functor. Writing, as usual, $(f) - 5 for a morphism 5 of Pi, the image of (k,kri, p ) under$isa k monad ( B .t* ,T[ ,p ) in A for each k^l, which we call the k-fold composite monad associated with the K k commutative monad (B ,t ,Ti,p ,X). We denote the Eilenberg-Moore object for this composite monad by B and k the corresponding universal cone by (u ,5 ). k k Since this universal cone is a t -algebra, we have k 232 We shall show that there are adjunctions k,k+l f B k nk,k+i ' c U k ' k + 1 such that the diagram of adjunctions k,k+l commutes. First we define f] Lemma 1 is a t -algebra. k EffiQf: The condition involving r i k + 1 is clear. € B k ( k + 1 K + 1 Because of the relation (K2), it suffices to show that 235 |2k+2 This follows from the relation in Pl: (p+PjJ (l+X^'^+k) (k+l+p+k) (k+2+\ ' ' '>) ( k 1 = (p+k) (l+X^' *) 1 (Pfc+i+l) . The relevant morphisms of D can be pictured by the following diagrams in which the shading is now a substitute for drawing k parallel arrows. • Using the result of lemma 1, we define such that ( k + 1 :B > &k+l be the unique morphism 1-cell t0 k is a i -algebra. k Proof: The condition involving T \ is clear and the condition involving k relation in A( B ,B). is a consequence of the following 237 For 0<i<k, we define u ( i ) k ( k + 1 j(i> k,k+l >k+l" : B 5k >B k + 1 , = Letu k ( k + 1 =u<°) k r k + 1 : B » B and let t k + 1 to be the unique 1-cell such that k k k fk + 1 B k+l =u , k k + 1 f k (k + 1 : B » B. k k Lemma 3 *k, k+l k :B * is the 1-cell induced by the morphism of monads B k (t,X< ' >):(B,t T ,Mi ) k 1 k ,c 1 l t » (B,t ,Ti .M ). k Jt k Proof: (t, X * ' )) is clearly a morphism of monads and we have k 1 f k,k+l -*B k+l" k,k+l t k Now Tiu :(u ,5k) k k+i : 1 ^(tUk.tSk • X ' U k ) is a morphism of t -algebras, so we can define ( k k »t t k,k+l k+i be the unique 2-cell such that 10 k ( 1 > k 240 Similarly, we have a unique 2-cell u k ( k + i: (t | ) )t( 2 > c+1 t k (k + such that 1 B tk,k+l The following result is easy to check. Lemma 4 ( Bk^k,k+lk+i.Mk,k+l) i s a monad. We shall show later that the Eilenberg-Moore object associated with this monad can be identified with B k + i ' however, for the present we are mainly interested in T\ constructing between fjc^+i and k + 1 k( k + 1 as the unit of the adjunction that we are . The next step is to describe the counit € k J c + 1 . We need to obtain some preliminary results leading to a decomposition of the universal cone ( u ,5 ). By k taking compositions of 1-cells of the form u B > B k + S k k > k + 1 : m a ) :k k + 1 •B we obtain various 1-cells k for s > l . To describe these 1-cells let a. = < a , a 0 increasing sequence of s elements ofm = k+s = Ti ( B l f = A 0 ^\ + + a - a - l + T i + a -a -l+T[+. • • • • 1 0 1 , a _ > s 1 denote an {0, . . .. ,m-l}. For each such sequence let • m denote the morphism of f l given by ^<m,A) 0 k m-ag^-l. 241 Thus Ti ( n wa ) :k > m is the unique order preserving injection whose image does not contain the points of the sequence a. Let T\ ( n i ja ) :t > t be the corresponding 2-cell in A( B ,B). k m Lemma 5 is a i^-algebra. Proof: Letu ( a ) k m : B m >B k denote the composite 1-cell B • In particular, taking the sequence < 0, i-1, i+l, i with 0<i<k is omitted, we obtain a unique 1-cell u < i > 1 j c + 1 k> in k+1 in which the only one element : B k + 1 > B such that k Proof: The second 2-cell is 243 The next result is immediate from the definitions. 244 L e m m a7 For 0<i<k-l, we have B k+1 ,<i+l> ,<i> l,k uJc,k+1 U >k+l 1, k+1 • By induction from lemmas 6 and 7 we obtain the following decomposition. L e m m a8 B , k+1 k+1 »k+l l,k+l • 245 Lemma 9 • Using the result of lemma 9 we define X ^ ' * : B 1 k + 1 >B k + 1 to be the unique 2-cell such that 246 k+1 (k,l) k+1 k+1 k+1 X<k,l) J K + 1 k+1 Since the k-fold vertical composition [ X *k, k-fold horizontal composition [ ^ (k, l ) ]k j ms e ] is the identity 2-cell on t k identity 1-cell on B k + 1 k + 1 , it follows that the . Thus, in particular, we see that (k' > is an isomorphism. 1 Lemma 10 (k,l) •* Bk+1 >k+l ,<i> l,k+l ,<i+l> U >k+l' — >B if i<k B if i = , .<0 > 5 Proof: ,<i> l,k+l (k,l) >k+l >k+l k+1" l,k+l k The lemma follows from the relation r . i + 1 l tn tT\ k _ i _ 1 k if i<k, if i=k, which follows from the relation in D: X< ' > k x (i7\+l+(k-i)Tl) = ((i+1) T \ + l + ( k - i - D n> if i<k, if i = k . . l+kT\ As usual this relation can easily be verified by drawing diagrams to represent the morphisms. The left hand morphism can be pictured by the diagram i+1 if i<k, and by the diagram 248 Proof: Thefirst2-cell is 249 The result follows by lemma 7. Generalizations of lemma 11 can be obtained by using the following result. L e m m a 12 For any i , j with 0 < i < k and 0 < j < k Proof: The case i = j follows from the fact that which is an easy consequence of the relation M • \ = u. If we may assume without loss of generality that J > i - L e t u < i 'J > 2 j c + 1 :B k + 1 > B be 2 the unique 1-cell given by the strictly increasing sequence of k - 1 elements of k+l which omits i and j. Hence so by lemma 11, 255 Proof: First we show that Since u u k • t T \ u = i d , we obtain thefirsttriangle identity for the adjunction. k To prove the second triangle identity for the adjunction we show that 1 1 is the identity 2-cell. This follows immediately from the fact that the upper 2-cell is 1 while the lower 2-cell is 258 P r o p o s i t i o n 15 The diagram of adjunctions Hence f k ( k + 1 f k - f Since u T i k k + 1 k k + 1 . = T\u , we see that k 1 This establishes the desired relation between the counits. By composing adjunctions of the form k,k+l f B * ^k+l we obtain adjunctions ( ' 1 k,k+1 U € B K > K + 1 k + i 261 Lettjcm k,m k,m &k =u f > B . Then t : k k /k + 1 the morphism of monads (t, X < - >): (B ,t , T i , u ) k 8 k k k : B > B is the unique 1-cell induced by k k > (B ,t , T \ ,M ). k k k Lemma 16 For m>k>l, T\ : 1 km > t k m is the unique 2-cell such that 262 Proof: It suffices to establish the equality of the given 2-cells which we can do by induction on m. The inductive step is obtained from the relation 1 B • Letting p l k m :(t k > m ) —> 2 t k f m be the unique 2-cell such that k,m we obtain a monad structure ( B , t k k m , Ti k m , p k/in ). L e m m a 17 For m>k>l, € k tm :f u k rm k r m > 1 is the unique 2-cell such that 263 Proof: The lemma follows by induction on m with the inductive step being obtained by reducing the 2-cell 264 We denote the second 2-cell in the statement of lemma 17 by 1f . Using the decomposition of lemma k( m 7 we have ' P r o p o s i t i o n 18 The Eilenberg-Moore object for the monad ( B ,t k k( m and the associated universal i.^ -algebra is given by ( t m kf , Ti , p k (m m , 5 kf m k m ) can be identified with B ). PjBQf: It suffices to show that B has the appropriate universal property with respect to the monad m ( B . t , , Tlicm- Mk,m)- F ° k k m r u i 1-cell universal property let e 265 be a t -algebra. Now k f m Let w: A > B be the unique 1 -cell determined by the above t -algebra. Then m m 266 w Hence w is unique. It is straightforward to check the 2-cell universal property. P r o p o s i t i o n 19 The adjunction f J k,m k,m : is the canonical adjunction arising from the monad ( B , t k k m , k,m T i k ( m , M kf m ). Proof: The 1-cells f k( m , u k Tm and the 2-cells T\ construction. This is immediate for u k ( m ,e K? m , T\k, m k( m m coincide with those arising by the canonical & k , m- ^ e o r ^k, m w e have k,m Hence 5 , f , k m k m = M , - as required. k m We now investigate the 2-functorial properties of the preceding constructions. 269 Let(B.p) = (B,t,rt,p,X)and(B',p') = (B\t\ri\M\X') be commutative monads. Then for k>l we have k-fold composite monads (B ,t k ,r\ k ,p )and (B' ,t' k k ,r\' k ,p' ). Suppose (h ,cx): (B ,p) > (B' ,p') is k a morphism of commutative monads. Then we have a morphism of monads » (B'.t'k.n^.M'k) (h,a< >):(B,t ,Ti ,M ) k k k k where, as before, k copies Indeed, with the evident description for 2-cells, we have a 2-functor C : Pl-Alg( A ) -» Mon( A ) . Since ( k , k r i , p ) is a monad in D , there is a unique monoidal functor J : (A ,+, 0 ) - -» ( ( " ] , + , 0 ) with k k k J (l)=k, J (Ti)=kri and J (p )= p . Then C is induced by J in the following way. k k k k k k For a commutative monad (B ,p), C ( B ,p) = ( B ,p ( J ® 1)); if (h,oc): (B ,p) k k morphism of commutative monads, C ( h ,cx) is the morphism of monads given by the diagram k J ®1 k A® n® B 1® h P ® h id A® B B B' J ®l k a n® B' B' -> (B'.p ) isa 1 270 Now suppose that A has Eilenberg-Moore objects. Then we can compose C with the Eilenberg-Moore k 2-functor V: Mon( A) > A to obtain a 2-functor 0 : fl-Alg( A) > A given on objects by k 0 (B,p) = 0 (B ,t,ri u,X)= B . We have a para-natural adjunction (<p,y,h,e):V k k J > V whose value at k a monad (B , t, T\ , u) is the canonical adjunction f B B n Hence for each k > l there is a para-natural adjunction (c where U : D-Alg( A) P ] C ) v , h , e ) = (cbC ,VC ,hC ,eC ):U k k k k k k »0 k k > A is the evident forgetful 2-functor. The value of this para-natural adjunction at a commutative monad (B ,p )= (B ,t ,T\,M ,X) is the canonical adjunction B B For m > k > l , there is a para-natural adjunction ( < P k/m ,V k fm ,h k (m ,e k (m v ): 0 k » 0 whose value at a m commutative monad (B ,p) = (B ,t ,r\,ii ,X) is the adjunction n ,r : k The para-natural transformation P c k / m k,m is given on morphisms as folows. If (h ,cx): (B ,p) a morphism of commutative monads, then cp , ( h ,a), that is, k m O (h,oc) k O (B,p) U (B',p') k k *k,m(B',P') 0 (B,p) m is the 2-cell given by U m(h,oc) * UjB'.p ) 1 » (B' ,p') is 271 where the adjunction ^Ym u ' ' k e' , m k m is associated with the commutative monad (B',p')= (B' ,t' ."n. ,p' ,V). We have the following commutative 1 triangle of para-natural adjunctions for m>k>l. *k,m U We now return to a consideration of the category Pl and describe two ways in which it can be given the structure of a commutative monad. Firstly there is the fl-algebra structure map p : D v "<J>: (H,+, 0) v x n left hand commutative monad structure which has the > D given by the monoidal addition, that is, "p( f ,5) = 5+5. > Cat(D,ri) be the corresponding monoidal functor. We write $( l ) = t; then v $( k)= " t , where t (m) = k+m. For a morphism f:m k v k thus ?(n)= |+n:m+n v <n, t. Ti. u, x). v v v Let v » kof f l we write $(T)= ~ f t V v m > k+n. In this way we obtain a commutative monad ( D / p ) = >"t ; k 272 We also have a right hand commutative monad structure described as follows. Let monoidal category obtained from functor p'rOD > (D,+,0) by "reversing the addition", that is, |© 5 = 5 + This operation is a f l where p(|~,5~) = v The diagrams commute, so we have a corresponding monoidal functor $ : (("] ,© ,0) > Cat( D ,fl). v Let A : (D,+ ,0) » (D ,© ,0) be the monoidal functor which is the identity on objects and has the following description on morphisms. For each object n of f l let Z isomorphism which reverses the order of the elements of n, that is, 2 > m of f l , let A(J) = 2 ° T ° 2 : n morphism |: n (fl ,© ,0) denote the » n be the self-inverse (i) =n-i for 0<i<n-l. Then, for each > m. Note that, because of their symmetry, n m n :n n the generating morphisms T i , p and X are all unaffected by A. We also have, for example, A general, for two morphisms <• and 5 of D we have A ( f + 5 ) = • (fl ,©, as claimed. Indeed A : (fl,+, 0) (1+1J) = u+1 .In £ + f,, which shows that A is a monoidal functor 0) is clearly an isomorphism of monoidal categories. Consider the composite monoidal functor (n.+,o) • cat(n.n). •(n.e.o) The corresponding fl-algebra structure map is on — — • o n — — -n which gives a commutative monad (fl, p(Ax1)). v We write $ A ( 1 ) = $ V |:m ^kofflwewrite V ( 1 ) = t ; then $ ( 1 ) = ( t ) where ( t ) (n) =n+k. For a morphism v v v $"A(T) = 5 " : ( t " ) m v k k > ( t ) . Using this notation tiie commutative v k monad ( f l , p "(Ax 1)) is (fl, t , r\", p, X ) . Then for each k>l we have the k-fold composite monad v (fl, (t ) , v k Cn, ) ,p v k k v v ). In order to avoid using parentheses we write (t ) v k = t£and ( T \ ) v k = r^.Thus, for example, (l ) v : 1 (n)=n+kT\:n k t * *k* s m e natural transformation whose value at an object n of D is the morphism » n+k. Let (n, 9) be a t^-algebra, where n is an object of D and 0 : t n k map. Such a t^-algebra gives rise to a pair (n, <p) where <p: k k nrj+k > n is the composite morphism e~ • n+k Conversely, suppose we are given a pair (n, <p) where *p:k > n is the algebra structure *> n > n is an arbitrary morphism of D. Then, since n n+kr\ • n+k<« is a coproduct diagram in D, we can define 0 : n+k nT\+k k » n to be the unique morphism such that the diagram n+kri commutes. Then the diagram n+k+k n+U 0+k n+k k n+k • 0 -*• n automatically commutes. Thus we see that 6 is the structure map for a t^-algebra (n, 6). We shall henceforth identify t^-algebras with pairs (n, y) such that ip : k D. With this identification a morphism of t^-algebras ?:(n, *p) |: n > m of D such that the diagram > n is a morphism of »(m, \p) is a morphism 274 k n — *• m i commutes. Rather than work with the complete category of t^-algebras, we make use of the full subcategory f l £ whose objects are pairs (n, .a) where a. = <a , 0 , a _ > is a strictly increasing sequence of k elements k 1 of n. Such objects can be thought of as finite ordinals with k distinct specified base points. A morphism |:(n,a.) Mm,b_) of f l is a morphism | :n k » m of f l such that 5(aj.) for 0<i<k-l. In the pictorial representation of such a morphism we represent arrows which map base points to base points by lines of the form No two such "base point arrows" may cross each other. We call D k the reduced category of {^-algebras. For a sequence a. = <a , 0 <a +m, 0 , a _ > inn, letm+^ = a.+m denote the sequence k 1 , afc-i+m > in m+n. Letnidenote the sequence <0, , m-l> in any finite ordinal n with 275 n>m. The free t£-algebra associated with an object n of D is the pair (n+k, n+JO. The corresponding algebra structure map is p£ (n) : (t ) 2 k (n) ^ ^ ( n ) • t£(n) orn+p :n+2k • n+k. Since the free k t -algebras are objects of the reduced category f l , it is clear that we have an adjunction k k f k n n _i ^k u k k *k obtained as a restriction of the canonical adjunction associated with the monad ( D , t , T i , p k n off!, f ( n ) is the free t -algebra just described. For a morphism % :n k k f ( | ) = |+k: (n+k,n+k.) n+k k k k ^mofPl, — ?+k »rn+k » f l is the evident "forgetful" functor and we have u f k > 1 is the natural transformation whose value at an object (n, a) of D k k counit € : f u ). For an object k > (m+k,m+k.). thekdiagram k commutes, as required. u : f l k k k algebra structure map, that is, the unique morphism € ( n , a) : (n+k, n+JO k = t . The k is the associated > (n,a) suchthatthe diagram n commutes. The right hand commutative triangle shows that € (n,a) is a morphism of f l . k k € (n,a) may be pictured by the following diagram where, as before, we use shading as a substitute for k drawing parallel arrows. The triangle identities for the adjunction (f £, u £, r\£, € £) are given by the commutative triangles The functor p: fl x 0 v > fl given by monoidal addition induces a functor fl * fl £ we also denote by p. This induced functor is given on objects by "p (m, (n,a)) = v may also write as m+ (n,a.). Given two morphisms £ :m > fl £ which (m+n,m+&), which we > m'of f l and 5: (n,a) » ( n ,a') of 1 277 fl , p (5,5) is the morphism of Dk given by f+ £ : m+ (n,.a) » m' + (n' ,a.'). The diagrams v k nxon:———•n-n; p X 1 n*n; •n; clearly commute. Hence (("")£ , p) is a commutative monad which we may also denote by ( , t , r i , " u , X ) v v v with the obvious definitions for t, T i , u and X. v v v v P r o p o s i t i o n 20 The adjunctions f; n in Cat enrich to adjunctions (n^.-p) (n, p) v /nfl-AlgCCat). The diagrams n*n; n onix t; 1* r>n; •a U. OH' commute. For example, the left hand diagram commutes because fkp<r.5~> = fk(T ?')= r+?+k ="p(T.fk(T)) = p(i*fk)<r.5). v + •n: v n v 278 Hence f £ and u are strict morphisms of Pl-algebras. k We have 1 on- on;. Ix ixfi U, n- onsince "p( 1 xT\ ) (m,n) ="p (m, k n on- •n (n) ) = m+n+kTi = t\k(m+n) = "p (m, n). Thus T \ is a 2-cell k between morphisms of Oalgebras. Also »on; on; •n 1 since for a pair of objects m of n and ( n , a j off]^ € p(m(n,a)) = v k — n. v 'k wehave p( 1 x e ) (m, (n,&)) = m+€ (n,a.) while v k k € (m+n,m+a). These are just different representations of the same morphism of f]^ k . • 279 We shall show that for m>k2:l there are adjunctions K k,m n n; — i k which are the restrictions to the reduced categories of the adjunctions f B k,m * k l k,m c B k,m which we considered previously, for the c a s e ( B , p ) = ( f l , p " ( A x 1)), that is, ( B , t , T i , p , X ) = (n,t .n .u .x ). v v v v Form>k£l,let f f k ( m k ( i n : D * P l b e the functor given on objects by k m ( n , a ) = (n+s, <a , .. . ., a _ n , n + l , . . .. ,n+s-l>) 0 k lf where k+s=m. Thus s new base points are added "on the top o f (n,a). » (n',a') o f D , f Given a morphism g: (n,a) k g+s : (n+s, <a , . . , a ^ ^ n , , . . ,n+s-l>) 0 Let u k fm : 0^ »f l k k r m ( £ ) is the morphism of > ( n ' + s , <a ' , . . 0 given by .a'^^.n', be the functor which "forgets" the last s base points. . . ,n'+s-l>). 280 (ii) EEQQf: (i) The morphism of D obtained b y evaluating the natural transformation given b y the second diagram at anobject (n,a.) of D k can Depictured by the following "arrow diagram". Note that X" X"< ' >(n) = n+X< '^sinceA(X< ' >) = X< - >. k s k k s s k ( k ' s ) (n,aj = This is the same as the morphism given by evaluating the first natural transformation at (n, a.). (ii) The morphism of f l obtained by evaluating the natural transformation given by the right hand diagram at an object (n,a.) of f l ^ 0 3 1 1 be pictured as follows. 282 This is the same as the morphism of f l given by evaluating the first natural transformation at (n, a.). Lemma 2 shows that f£ and m f ^k,m - >B andu^n, : B m m • are the restrictions to the reduced categories of the 1-cells > B ^ respectively, which we described previously, for the case m (B,t,Ti.M,X)= ( n , t , r . M , X ) . v v v v l For 0 < i < k - l let u { < i > ( J c : Pl k *fl v be the functor which "forgets" all the base points except for the base p o i n t a ^ . ^ . This functor is given on objects by v/ * (n,aj = ( n j a ^ . j ) andhasthe 1 obvious description on morphisms. (Here f l " = Pi J and we have omitted the parentheses < > for the sequence consisting of the single point a^^.j^.) Lemma 22 Proof: Clearly u u £ v object (n, a.) of D ; k k = u . The natural transformation given by the right hand diagram evaluated at k gives the morphism of f] pictured as follows. n+k-1 284 This is the same as the morphism given by evaluating the natural transformation of the left hand diagram at • (n,a). Lemma 3 shows that u £ u<i> < : L > k is the restriction to the reduced categories of the 1-cell > B,which we defined previously, for the case (B.t.Tl.M ,\)= ( f l , t~ Ti", p", X " ) . l,k r3jc : » n ^ - T h e n t ^ is given on objects by t , (n,a.) - (n+s,a.) L e t - i n " k,m k,m = u f k and is given in the obvious way on morphisms. Let T\£ fm : 1 valueatanobject (n,a) ofn isri^ (n,a) = n+sri: (n,a.) k m m > ^k,m be the natural transformation whose > (n+s,a.). For an object (n,aj of Pl^ we have f Let€ u (n m ^k,m k,m : k> k,m k,m ' a) = (n+s, <a , . . ., a ^ ^ n + l , .. . ,n+s-l>) 0 * be the natural transformation whose value at an object (n,a) of flm isthe u 1 unique morphism of P l such that the diagram m commutes. €^ (n,a.) can be pictured as follows. m 285 L e m m a 23 (i) 1 Proof: (i) is clear. 286 (ii) The second natural transformation evaluated at an object (n,a) of 0^ is the morphism of f] pictured as follows. n+s-1 n+s-2 n+1 n n-1 a Jc-l a a k a k-l ^0 0 0 This is clearly the same as the morphism given by evaluating thefirstnatural transformation at (n, a). • Lemma 4 shows that Tik,m ande^,,, are me restrictions to the reduced categories of the 2-cells ^k, m 1 * *k, m ^ k , m fk, m k, m : m € : * 1 respectively, which we defined previously, for the case u (B,t,Ti,M,X)= ( n , t , V . P . X ) . v v v It follows from the preceding considerations that for m>k£l we have adjunctions k,m H k 1 U k,m 1 m •k,m which are obtained as the restrictions to the reduced categories of the adjunctions f k,m "* &k k,m B m J for the case (B .t.Ti.u ,X) = (fl, t , T\ , u v v 1 0 3 1 ( *k, m' k , m' ^k, m' k , u e ^ a n X k,m : as suggested earlier. If one was simply interested in showing adjunction without relating it to the earlier results of this chapter, then 287 this can easily be done directly. Although this is not strictly necessary for the logical development of the theory, we do it anyway. For an object <n,a) ofD^ the diagram v f f , f 4 k,m' -k,ni n ( n ' a v ) f k,m( '.a) v • k,m k,m k,m( ^) n f u f n € f k,m k,m < '3) f n k,m( '3> n commutes because it is n+sTi+s (n+s,< a , . . . a ^ , n , . . . , n + s - l » »• (n+2s, < a , . . . a ^ , n , . . . , n + 2 s - l >) Q c n+ u« (n+s,< a , . . . a ^ j , n , . . . , n + s - l » 0 For an object (n,a) o f f ! ^ the diagram •U "MM) k f m f k ( m u ] t f m u commutes from the definition of € k /m (n, a), since m u k fm (n,a) k,m € (n, a) k | i n (n,fl) =n+siv 288 Proposition 24 For m > k > l the adjunctions k,m "k,m in Cat enrich to adjunctions k,m (n-P) k,m : k,m in D-Alg( C a t ) . Proof: It is easy to see that the diagrams on; nxn; ix f k,m 1 k,m ix ( m Uk,r n; on; nxn; commute so f £ u k,m and u£ are strict morphisms of n-algebras. rm We have 1 on; ix f k,m 1 X T ik,, •* on: |x u k,m on; •n: 289 1 since for a pair of objects m of Pl and ( n , a.) of f l "p(1XT^ m k ) (m, (n,a) ) = m+n+sTl: (m+n,m+a.) = > (m+n+s,m+a.) 'H.k,(mn,m+a) = T^^'pOn, (n,a))+ m Hence T\ ( k m is a 2-cell between morphisms of fl-algebras. We show that nxn; ^ — „ JL^L—on;; e. n*^ ^ i For a pair of objects m of f l and (n,a.) o f f l = m+€ (n,a.) : (m+n+s, <m+a , • • • ,m+a _i» m+n, . . .,m+n+s-l>) krItl 0 The "arrow diagram" for this morphism of e ic, m < m + n ' - -) * fl-algebras. m+ m a sm e k is shown below. It is clear that morphism of Dm- This shows that € k ( m m > (m+n,m+a.). " p (m, (n,a.)) = is a 2-cell between morphisms of 290 • 291 VI. The Lifted Quasi-Adjunctions By proposition 11,16 the tensor product operation induces a 2-functor of two variables fl-Alg(Cat) x A > fl-Alg(A). Hence, using the left-hand commutative monad structure on f] we obtain a 2-functor F : A —» H-AlgC A), given on objects by FA = ( f l ® A, "p ® 1), and using the left-hand commutative monad structure on Pl for k > Pl-Alg( A), given on objects by k 21, we obtain 2-functors F£: A F£(A) = ( n k ® A , The adjunction f 1 (n,-p) v k „ m , p) v k ^ U k 6 k in fl-Alg( C a t ) of proposition V.20 gives rise to a strictly natural adjunction (cb-,v ,h ,e ):F k k >Fi k whose value at an object A of A is the adjunction in fl-AlgC C a t ) f (n®A, p®D v ® l k (n ®A, p®n v ^ k n ®i u k k ® i e k ® i Similarly, for m >k 2 1 , the adjunction f 1 v k. m ^k,m in Pi-Alg( C a t ) € k,m of proposition V.24 gives rise to a strictly natural adjunction (*k,m.^k,m.hk,m. k,m ):r"k e >*m whose value at an object A of A is the adjunction f (n ®A, p®o ^ v k ^ m ® 1 v m ® 1 K, m u ^ ® ' (n;®A, p®o v eiu® We have the following commutative diagram of strictly natural adjunctions. 1 p® v 1). 292 k, m Fk" r k, m Let n-Alg(A) ' H u e be the quasi-adjunction obtained by applying proposition 11,11 in the case where the 2-monad (T,T) ,Ji) is derived from the strict monoidal category (fl.+ .O). Then the unit T|: 1 transformation with T)A = a( 0 ): A » UF is the strictly natural > f l ® A and the counit £ : FU > 1 is the para-natural transformation such that for a commutative monad (B,p), £(B,p)isthe strict morphism of commutative monads given by p:( D ® B,"p® 1) »(B,p) and for a morphism of commutative monads ( h ,oc): (B ,p) > (B' ,p'), £( h ,oc) is the 2-cell between strict morphisms of commutative monads given by n® B • B 1® h V n® B' -*• B 1 By means of the attaching proceedure using the strictly natural adjunction ^k^k'^k^k ^ : f r > Fjc we obtain a para-soft adjunction ( F ^ , U , T | , £ , r , 8 k k k k ) for each k21. Form >kil, the para-soft adjunction ( F , U,Tl ,£ ,r ,8 ) can also be obtained from the para-soft adjunction m m m m m (F ,U,T) ,e ,r ,8 ) by attaching using the strictly natural adjunction k k k k k (^k\m> k\m'^k,m' k,m v e ) Fk * Fm • : *;| 1 situation is indicated by the following diagram. V k,m Fk 1l v; D-Alg(A) *k V k F u We now describe the para-soft adjunction (F ,U,T) ,£ ,r ,8 )in detail. k The horizontal unit T ) : 1 k k k k > UF . k k T) £ is a strictly natural transformation and for an object A of A,T]£A is the composition T)A Ucp A k UFA „ p|^ A A The horizontal counit £ : F U k * UF A k k A * > n ®A k > 1. k For a commutative monad (B,p),££(B,p)isthe composition V U ( B , p) £(B, p) k F U(B, p) > FU(B, p) k * (B, p) This is the strict morphism of commutative monads given by u ( D t ® B , ~ p ® 1) k® 1 * (fl® B, p ® 1) v P : > (B, p) Let (h ,oc): (B ,p) » (B' ,p') be a morphism of commutative monads. Then £ £( h ,oc) is the 2-cell between strict morphisms of commutative monads given by n® B ® B 1® h B ® h id f)y ® B' u ® 1 k The vertical unit r£ : 1 oc n® B' P' B' » U £ ° T| U. k k For a commutative monad ( B ,p), r£( B ,p) is the 2-cell U(B, p) T|U(B,p) • UFU(B, p) UcprU(B,p) > UF~U(B, p) UFU(B, p) U£(B,p) U(B, p) » B a(0) The vertical counit a^iEtf^ o F£T|£ -> 1. For an object A of A, 8 A is the 2-cell in f]-Alg( A) given by k Fj-TiA F^UFA F^Ucb^A F-UF-A V^UFA V^UF id FUF^A FUcp^A EtpJA = £F^A id <f F£A This is the 2-cell between strict morphisms of commutative monads given by n®A k H ® A k 296 Now let (B ,p) = (B ,t ,T\.U ,X) be a commutative monad. The natural monad monad structure associated with the soft adjunction (F ',U,T] ',E ,r ',s ' ) gives rise to a monad structure on U( B ,p) = B. The k k k k k "multiplication" is given by the 2-cell TlfcUO.p) U(B, p) UE (B,p) k * UF U(B, p) —* k U(B, p) T| UF U(B, p) k T|^U(B. p) T l T | U ( B , p) k id k k k = id / *• U F U F U ( B , p) *• U F U ( B , p ) Tl U(B, p) U F U £ ( B , p) k k UF T] U(B, p) T l U £ ( B , p) k = UF U(B, p) k k k k k k U»;U(B. p) k U £ F U ( B , p) k k UE- (B, p) U £ £ ( B , p) k k UFrU(B, p) UE; cr(k,k ) n® k l^® n ®B 1 B k U id « / U(B, (B, p) k® 1 p) rs ——* n® P B — Cr(2k) B |o-(u-€ (k,Js )) k CT(k) f|®B •» B - 297 since U^€ (k, k^ ) = p . k k The unit for the monad structure on B is given by the vertical unit of the soft adjunction. Lemma 1 For a commutative monad (B ,p) = (B, t, r\, p), the natural monad structure on B given by the soft adjunction (F,U ,T] ,E , k k k 8 k ) is the k-fold composite monad structure (b ,i , r ^ , u ). k From this lemma we see that, for k>l, the 2-functor 0 : H-Alg( A) k » A described in chapter V k is the lifted 2-functor of chapter IH obtained from the natural monad structure associated with the soft adjunction ( F , U , T ] , £ , r , 8 ) . Recall from chapter V that there is a para-natural adjunction k k k k (^k'^k- k< k * 0 , whose vriue at each commutative monad (B,p) is me adjunction n k B IfQ :U k — -» U is the para-natural transformation Q Bv k = U E ° T ] U , there is a modification z k » V , k u w whose value at a commutative monad (B ,p) is the universal cone k k k • 298 B • Recall that £ k = u^e^. In order to construct a lifted soft adjunction between F£ and 0^, we shall show that the coequalizer hypothesis of chapter III is satisfied. Thus we consider the following modifications. F F a k i^k Fk^lkU F k^k U k £k k : F u c - b k k k c id : F k k v For a commutative monad (B ,p), a ( B ,p) is the 2-cell in D-Alg( A) given by k 1® u, n ®B k k F U k k n ®B k | € i k 0 1 n ®B k u:® i n® B / 299 u ;® u k n® B while b ( B ,p)is the 2-cell in H-Alg( A) given by k 1® t u,. k u ® 1 1 k 1® ?! n;®B n® B k 1® u. To check the first part of the coequalizer hypothesis we need to find a coqualizer for the two 2-cells a (B,p) andb (B,p) in D-Alg( A)( F ^ 0 ( B ,p),(B ,p)) = fl-Alg( A)( flk ® B / p ® 1),(B,p)).Tc k k k k this end we consider the 2-cells obtained by taking the horizontal composition of Ua ( B ,p) and Ub ( B ,p) k with cr(n,a.) : B •D k k ® B k for an arbitrary object (n,a.) of D k . Ua (B,p)°cr(n,a.) is k 0"(n, a ) u n ®B k JK® 1 n^®B k« k u y k cr(n +k) cr(u €^(n, )) k a(n) a f|®B n® B k 300 where p ( , ) is the image under the monoidal functor n u u (n,a.) = u (n,a) * : fl a k k ( ' A ) : n+k € n + k n • n. Hence U( ,a) : n n + k > A( A,B) determined by (B ,p) of * can be pictured as follows. n * * is the 2-cell in D-Alg( A) given by the diagram n 301 t n - a k-l _ 1 On the other hand, Ub ( B ,p) cr (n,a) is 0 k 1® t u k a(n, a) n^B K |i®s f c ® u. t n;® B> — — • n® B —-—> B Our first task will be to find a coequalizer for the two 2-cells ^(n, t Let X ( -a) :n l )U k t u„ n k (a +X< ' - O- >+k-l)(a +X( ' - l- )+k-2) 1 = u f > n be the morphism of f l given by n X<n,a> n + k n a )c 0 1 n a k 1 • • . ( a j ^ + X * ' " - ^ - ) +l)(a _ +X< ' 1 3 2 1 k n-1 a k-l a k-2 We simplify this diagram to n-1 n-2 1 n_a )c-l- )) 1 n-1 where the shaded region is understood to consist of arrows with no crossovers apart from those caused by base points "floating upwards". Let X ' ( n a > :t > t be the corresponding 2-cell in A( A ,B). This 2-cell can be pictured as follows. n n t k-i-l. n _ a B B X ' " Jc-i( 1 n a t ~ k-l n a _ 1 ) 1 ^(1, n-a^k+1) y' B t l a - a 0 • B n-a -k)^ 0 t B n-ao-k t o a Note that if (n, a) = (k,Jt), where Ji = <0,1, . .., k-l>, wehave \(k,W x( ' " ) t k = n k : n >t . In particular, \ n ( k ' w = id:t k » t . Also M k (lt , w =p . k 304 Lemma 2 In f l we have the relation: "X(n.a) JJ = (n-k+Uv.) ( X < '*) +k) n ( n > a ) Proof: X < »a) y j n na j can be represented pictorially by the diagram n+k-1 a k-l while (n-k+u ) ( X '*)+)c) can be represented pictorially by the diagram (n k n+k-1 a k-l • The corresponding relation in A( B ,B) is: X( »a> n « M , ) = t (n a n-k Mk ° X ( n , a ) t 305 Let S , :t u > t -*U)c be the 2-cell in A( B ,B) given by 5 , n ( n a n k k ( n =t ~ S n f l ) k B k X< -a> n u , that is, 5 ( , ) is the 2-cell k n a \(n, a) B Notethat 5(k,kj = 5k- Our U t n + £ u m is tos n o w B t n-k that the following diagram is a coequalizer diagram in A( B ,B). k (n,a) k U V S(n,a) * t u,, n t ~V n 1% Indeed we shall show that it is a split fork. First we check that it is a fork. Lemma 3 S(n, a) ° M , (n fl) u k - C • ( n # a ) t«C . K Proof: 5 (n.a) • < , a ) k u u n " ^ ?K • * n _ k = t ~ £ n k a > o t ~ u u n K ' ( n u (n o \ (n,a) t u k k • M ,a) k u k k k k by the relation following lemma 2. = t"- S k » X< -a) n K o t - 5 n Uk k k (See the following diagram.) • (n,a) 306 B • Let f \ ( ) :n-k n a » n be the morphism of f l given by ^<n,a) ^ (n, a) ^ fescnted = a 0 +n+ai-a -l+n + 0 +r +n-a _ -l_ l previously in chapter V. As before, let T\ ( na t k ) :t 1 n _ k corresponding 2-cell in A( B ,B) determined by the commutative monad (B ,p), so that ^(n,a) t 0 T \ t 0 " l r i = Note that n^k.) = T a a a - 1 l k Lemma 4 We have the following relations in fl: CO >>' fl) n ,a) = n {n k + kn, T\t ' k-l _ n_ a _1 • t be the n Proof: Both relations can easily be verified by representing the relevant morphisms pictorially. The relations in A( B ,B) corresponding to the relations of lemma 4 are (i* \< 'a> (»)* M(n, n • Ti •n a) = tn-*Ti , k ( n , ( n f A ) t = k a ) (X(^),-l. Proposition 5 t n + k u »t k ^ \ t " u n k k t ?k n is a spit fork, split by t n + V« t u « n \n, t U «X< 'a>U k a ) k ' " n k k ^(n, Uk K t n _ k a ) Proof: <) A 5(„, a) °Tl(„, )U ft = t*-*? • k k X(n^) t " 5 o t - n n n k • n n, )U U k ( a k by (i) k k k id. (B) From (ii)* we have u , ( n h e n c e 0 f l ) ^(n,a)Uk n n, )^ ( • X^-a) k a °n , t u k ( n = a ) ^ where the last equality follows from the diagram k K - T • = id, X(n^) l< , n t U k f l ) k U k = i d . •X(n^>U , k u 308 • Note that for the special case (n, a.) = (k,k.) the split fork of proposition 5 reduces to the split fork "k k u t 2 k t u„ a k ^ k split by t 2k t U, K a Tl t U k k )c which is the split fork associated with the universal t -algebra k for the monad (B ,t ,ri ,u ). k k k We now investigate the functorial nature of the split coequalizer of proposition 5. For this purpose we construct a functor $ : f | k k > A( B ,B), which is given on objects by $ (n, a.) = k k t n_k u . k 309 Since the morphisms of f l are obtained from those of f l _ it is clear that they are generated under k composition by morphisms of certain specific types. For each type of generating morphism F, of f l k we give the value of $ ( F,). Note that in the diagrams drawn to represent these generating morphisms we follow the k convention of chapter V and use lines of the form to depict arrows which map base points to base points. Type: SI £ = h+X+e: (n,a.) >(n,aj where h+e+2=n , a^-Ch andh+l<a . i n-1 a k-l a i h+1 h aj-i 0 There is a single cross-over which does not affect any base point. Note that if i=0, there are no base points below the cross-over. We set $ ( f ) = t k h - i Xt e + i - k u :t ~ u n k k k > t n _ k u k- 310 Type: S2 f = h+X+e: (n,.a) > (n, <a , . . ., a j _ 0 l f a +l, a ± i + 1 , a k-l > > wn ere h+e+2=n anda^h. n-1 »k-l a i+l aj^+1 h+1 h=a^ a i-l ao The single cross-over switches the base point a upwards. We set $ ( J)= id : t A Type: S3 f = h+X+e: (n,a) n - k k > (n, <a , . .., a ^ , a ^ l , a 0 i + 1 , u >* ~ k• n k ku , a _ >) where k 1 n _ k u h+e+2=n and a^h+1. n-1 a k-l a i+l h+l=a i h a i-l ai-i The single cross-over switches the base point a.^ downwards. We set $ ( J) = id: t k k >t n_k u . k Type: CI % = h+u+e: (n,a) > (n-1, <a , . . . 0 ,3.^,3.^-1, a _ -l>) where jc 1 h+e+2=n, a ^ ^ n and a ^ h + K a ^ There is a single collapsing of two points to one, which does not affect any base point We set 4> (f) = t - u t h i e + i k Type: C2 - u :t - u k n k l c | = h+p+e: (n,aj h+e+2=n and a =h. ± » t - " u . n k k 1 k » (n-1, <a , .. . , a 0 i r a i + 1 -l, , a _ - l > ) where k 1 312 The single collapsing brings together the base point a^^ = h and the neighbouring point h+1 above In this case we let $ ( f ) be the 2-cell k e+l+i-k B • B ^ k B »B ^(l,e+l+i-k) 4 e+l+i-k ,h-i thatis, * ( g ) - t n - - * ? ^ ! , * o t " X< 'e+i+i-Jc)u :t " u 1 h i 1 n k k Note that if h=l, Type: C3 u < 0 > 1 ( k = 1 :B £ = h+u+e:(n,a k » t n k k _ 1 u k » B. • (n-1, <a , . .., a^-i, a ^ - l , 0 a _ -l>) where h+e+2=n k 1 and a^h+1. The single collapsing brings together the base point a =h+l and the neighbouring point h below a . We i ± 313 use the same 2-cell as for the previous case and set $ (D =tn-l-k k Tvpe:N 5 u <i> ^ o th-i\(l-e+l+i-k) 1 |" = h+rf+e: ( n , a j U k . n-k t > t - " U . n U k k k > (n+1, <a , . . ., a _ , a + l , 0 1 i 1 a i k-l + 1 > where h+e=n ) and a _ <h<a . i 1 i A new point is introduced at the level h between the base points a _ and a±. In this case we set i $ (|)-t - nt h ] t i e + i - u :t - u k n k k * t " n k k + 1 1 u . k The morphisms of H are generated under composition by the seven types of special morphisms just k described subject to a number of relations derived in an obvious way from the relations (Pfl1) to (Pfl 17) between the primary generating morphisms of f l . We do not list these relations separately, since such a list is implicit in the following work. To show that $ extends to a functor on the whole of f l k k we check that the appropriate relations are preserved. First we consider the relations arising from the essential relations for primary morphisms (Pfl 1) to (Pfl8) .that is, from the relations ( f l 1) to (f]8). There are four types of relations derived from the relation (f]4): ( l + X ) ( X + i ) ( i + X ) = ( X + i ) ( i + X ) ( X + i ) . The interaction of a base point can occur in one of the three ways suggested by the following diagrams. 314 There are also relations derived from (P|4) in which there is no interaction with any base point. The first of the above configurations in which a base point is affected occurs in relations of the type pictured as follows. n-1 a n-1 k-l a k-l »i+l h-l=a. *1~1 »i-l ijoceoccMooc a 0 0 The image of each of these morphisms under $ is t ~ h k 1 _ i Xt e + 1 + i _ k u k :t n - k u k »t n _ k u k where h>l and h+e+2=n. In a similar way it is easy to check that the types of relations in which the other two configurations occur are also preserved under $ . The case where no base point is affected is also easy to check and depends on the k relation tX • Xt • tX = Xt • tX • Xt in A( B ,B). There are four types of relations derived from the relation (fT7): (u+1) (1+X) (X+l) X (1+M) First we consider relations of the type depicted as follows. n-2 n-2 The image of each of these morphisms under $ is t k h - 1 - i ut e + 1 + i - k u :t k n - k u k >t n - k - 1 u ) c where h>l and h+e+2=n. For the second type of relation derived from (f]T) we abreviate the diagrams and depict only the part which differs from the first case above. As before each morphim has the domain (n, a.) . The image of the left hand morphism under $ is the 2-cell k 316 B where h+e+2=n and h S l . This 2-cell is ^e+l+i-k ^e+l+i-k ^h-i which is the image of the right hand morphism under $ . k The third type of relation derived from (Pl7) in abreviated form where each of the morphisms depicted has domain (n,a.) is The images of the left and right hand morphisms under $ are exactly the same as in the previous case. k . There is also a fourth type of relation derived from (Pl7) in which no base point is affected and this relation is also preserved as can be seen by using the correponding relation: pt • t\ • Xt = X • tp, in A(B,B). 317 There are four types of relation derived from (fl8): (1+p) (X+l) (1+X) = X (u+1) . Thefirstof these in abreviated form in which each morphism depicted is understood to have domain (n, a.) is The image of the left hand morphism under $ is the 2-cell k je+l+i-k je+l+i-k t t h-l-i where h+e+2=n and h>l. This is the same as the image of therighthand morphism under $ . k The second type of relation derived from (fl8) in abreviated form in which each morphism depicted is understood to have domain (n,a.) is The images of these two morphisms under $ are exactly the same as in the previous case. k The third type of relation derived from (fl8) in abreviated form in which each morphism depicted is understood to have domain (n,a_) is 318 The image of each of these morphisms under $ is t ~ h 1 - i k Mt e + 1 + i _ k Uj :t c n - k u k *t n _ k - 1 u k where h>l and h+e+2=n. As before there is an evident fourth type of relation derived (P|8) from in which no base point is affected and this relation is also preserved under $ as can be seen by using the relation tp • At • t\ = X • pt in k A(B,B). The image of the left hand morphism under $ is the 2-cell k e+l+i-k * l,k X (1,e+l+i-k) 4 e+l+i-k where h>l and h+e+2=n, which is e+l+i-k J l,k *e+l+i-k x < i > (l,e+l+i-k) *e+l+i-k ^(1,e+l+i-k) e+l+i-k The image of therighthand morphism under $ is the 2-cell k This is the same as the image of the left hand morphism under <$. (See lemma V,12.) k 321 The second type of relation derived from (f|2) in abreviated form, where each morphism has domain (n,a.) is h+1 h=a h-1 The image of the left hand morphism under $ is k e+l+i-k B• t J l,k (1,e+l+i-k) X' •e+l+i-k -,(1, e+l+i-k) e+l+i-k J4 B T I T I ^ •* B jh-l-i •B where h>l and h+e+2=n, which is the same as the image of the left hand morphim in the previous case. The image of the right hand morphism is also the same as in the previous case. The third type of relation derived from (Pl2) in abreviated form, where each morphism has domain (n, a.) is h+l=aj h+l=a h h-1 The image of the left hand morphism under 4*^ is the same as in the previous case, while the image of the right hand morphism is given by the 2-cell 322 je+l+i-k ^e+l+i-k jh-l-i B These two 2-cells can be seen to be equal using steps given for the first of the preceding two cases. The evident fourth type of relation derived from (fl2) in which no base point is affected is also clearly preserved by $ . k (fl3): X (fl6): pX = p The evident relations derived from and 2 = 2 can easily be seen to be preserved under $ , so we are left with k and (fl5): x (n+D = i+n (fll): p" (n+D = 1. From (05) we have the relation where, as usual, each morphism has domain (n, a.). The image of each of these morphisms under $ is the k 2-cell t h - i nt e + i " u k ) c :t n _ k u k >t n _ k + 1 u w h e r e h £ 0 andh+e=n. k A second type of relation derived from (fl5) in which no base point is affected is also clearly preserved by 323 From (fl 1) wehave the relation (n, fl ), The image of the left hand morphism under 4> is given by the 2-cell k t'e+2+i-k t J <i> l,k t ^(l,e+2+i-k) 4 e+2+i-k where where h£0 and h+e+2=n. This is the identity 2-cell on t ,h-i n _ k u . k A second type of relation derived from (D1) in which no base point is affected is also preserved by $ k The evident relations derived from the non-essential relations for the generating morphisms of f l are also preserved by $ . To indicate why this is true we check one of the cases arising from the relation (Pfl 10). k Thus we consider the relation depicted by the diagram 324 where it is understood that the middle shaded parts are missing if i = j -1. The image of the left hand morphism under $ k is the 2-cell e+l+i-k •* B . (1,e+l+i-k) •* B 1 l,k ^e'-l+j-k t h'-h+i-j t h-i where h >h>0, a ^ h , a j_ <h', h' +2<a j, i< j-1 and h+e+2=h' +e' +2=n. This is the same as the image 1 x of the right hand morphism under namely the 2-cell B Proposition 6 $k Let ¥ : H k : Hk » A ( B , B ) is a well-defined functor. k • A( B ,B) be the functor corresponding to the composite 1-cell k k u£®1 ^k 0 g p *n®B k : *• B Thus ¥ is the composition k fl • f l k •A(B.B) *• A (B ,B ) k where $ is the (monoidal) functor determined by (B,p)andU * = A(u ,B). k A. ¥ k A> is given on objects by ¥ k (n,a.) = t u and for a morphism F.: (n, a.) n k k •» (m,bj off] A, ¥ ( |~) is the 2-cell k Proposition 7 A* ?k : *k >$k givenby natural transformation. Proof: 5 ( n , a j = S<n,a) = t"-*5 • X< '*>u n k k k / s a We show that the diagram ? (n, a) k l (n,fl) k \(m,b) • * (m,b) : k C (m,b) k commutes for each generating morphism |~: (n, A.) Type: SI g = h+X+e: (n,fl) »(m, b_) of f l . k »(n,a) where h+e+2=n , a ^ ^ n and h + l ^ . We have $ ( g~) = t h - i X ^ ^ ^ and * ( g) = t X t u . 1 h k Hence and e k 5 (n,a) • ¥ ( D k $ (D k k °£k(n,fl) k - t n _ k 5 = t - Xt h i =t " 5 n o X< - >u n k k e + i _ k u a k •t Xt u h k ot n _ k 5 e k • X< -a>u n k k • t ^ X t ^ X • X <'a> n k U ] c , which is the 2-cell The following diagram shows that the relation: holds in fl. X ("'a) (n+X+e) = (h-i+X+e+i) X ( n 327 Hence in A(B,B) we have \<n,a> oth\t This shows that Type: S2 12 = < e - t h - i Xt • X <'*>. e + i n 5 (n,a) • ¥ ( f ) = $ ( f ) • 5 (n,a) . k k £ = h+X+e: (n,a.) > (n,b) 3 Q ' • • •' i - l ' i l » i + l » a a + k a a k where h+e+2=n , a ^ h and k-l^' We have * ( f ) = id and ^ ( | ) = t X t u . h k Hence k ? (n,i2) • f ( | ) - t k i (T) and The morphism e k k n _ k k •5 (n,a) k $ • X < ^> u «»t Xt u n k = t " 5 €»X< ^>u . n k n k X < ' > (h+X+e) of f l of can be pictured as follows. n a h k k e k 328 This morphism is the same as X <'3->. Hence in A( B ,B) we have \( 'k> • t X t N 5n(n,b) Type: S3 n 8 VI) £ = h+X+e: (n,a.) h = a c • • •' i-l' i~l» i+l' ^ < We have and a a a i k > (n,h) - l e n where h+e+2=n, n a = t n _ k a^=h+l and ^ n a = X * ' >, so k = t ~ 5k o X <-k> u $ ( D ?k< ' -) k e = $ (|>5 (n,.a) . (n,a) • k h k 5k ° X n ( n , a ) ® t Xt u e h k k u , since i ( | ) = id. k k This case is very similar to the previous case. The morphism X < ^ (h+ X+e) of f l of can be pictured as ( n follows. 329 This morphism is the same as X ( »a). Hence in A(B,B) we have X< 'k n Type: C l % = h+(i+e: (n,a.) k * 0' • • • ' i - l ' i ~ l f = a We have and n a a a ) «t Xt h e = X ' ,so ( n » (n-l,b_) where h+e+2=n, a ^ - c h , h+l<a and ± k-l ^• - 5ic<n-l,b> • * ( D k $ (5~)°5 (n,a.) k a ) k = t^ut* *"*^®t ~ 5 1 - t n k _ 1 5 n ot - ut h k i •X k e + i k u U k • X< 'a>u , n k k 330 which is the 2-cell t The following diagram shows that the relation : X (n-l,b) (h+u+e) = (h-i+u+e+i) X <>a>) n holds in fl. Hence in A(B,B) we have This shows that \(n-l,b) o t Mt h e = t h _ i (jt e + i • X < -a). n £ (n-l,b_) « ¥ ( f ) = $ ( f ) ® £ (n,aj . k k k k 331 Type: C2 fc - < ^Qr g = h+u+e: (n,aj •••f > (n-l,b_) where h+e+2=n, a ^ h and a^, i + i ^ ' ••••> k-l~^ a - a The following diagram shows that the relation : \(n-l,h) holds in fl. (h+]T+e) = (n-k+i-l+M+k-i-1) ( h - i + X < ' X e + 1 + 2 i - k > + k - i ) X< -a) n Using the corresponding relation in A( B ,B) we obtain 5 (n-l,bJ k = t" - 1 - •* (Dk t"" "^ • tn-k+i-lpt^-iun 1 ^ otn-k+i-lpt - - u k i ot - -kX( ' >tk-i n 1 k •t 1 1 i Uk h _ i X CWe+l+2i-Jc>tk-i Ujc et h - i X e+l+i-k)xk^ .x< 'A>U n k o\(n, ) ^ & u 333 334 335 by lemma V,12. This shows that Type:C3 £ (n-l,b_) • ¥ (f) k k g = h+p+e: (n,.a) h - aQ' • • • ' i - l ' i ^ - ' < a a - = $ ( f ) ° 5 </2.) . n k k > (n-l,b_) where h+e+2=n, a^h+1 and a k-l~^" h+l=a We have the relation in fl: y(n-l,i2) (h+p+e) = (n-k+i-l+p+k-i-1) ( h - i + X < ' 1 e + 1 + 2 i _ k ) + k - i ) T< 'a>, n which"looks the same" as the relation used for the previous case, but involves the new h and h • A slight modification of the diagrams used before proves this relation. Using the corresponding relation in A( B ,B) we can show by the same argument as before that S (n-l,b_) ® ¥ (g~) = k k $ ( D • S (n, a.) . k k Type: N g = h+Ti+e: (n,a.) > (n+l,b_) where h+e=n, a _ <h<a and i fc = <a , .. . .a^.a^l, k a 1 i-l S (n+l,k) • * ( f ) = t k and i a _ +l>. 0 We have 1 n + 1 k K(T) • 5k ( /a.) n = t = t h _ i - 5 k Tlt n _ k + 1 ) c e + i •X(n+l,b) - U •t " 5 , t n k 5k •t h _ i ut e + i Uk • th'nt«u k o X < '3> u k k n k U k • X< 'a>u , n k which is the 2-cell The preceding two 2-cells can be seen to be same using the relation in A( B ,B) corresponding to the relation in f): X~< 'k> (h+T\+e) = (h-i+T\+e+i) X < ' A > . This relation is demonstrated by the n+1 following diagram. n 337 Let P :n ® k Since £ : ¥ k k k B > B be theunique2-cell corresponding to k > $ k k > A(B ,B). k K is a natural transformation, there is a unique 2-cell p : p( U ® u ) k such that for each object (n,a) of D <r(n,a) $ :n k u£®u = k p • n® B Pk B K k ]l5 (n,a) k $ (n,a) k -* B k >p k We now show that ' P(u;€ ®U ) k k p(u ®t u ) ^ p(u ®u ) k k k k P(u ® k is a coequalizer diagram in A( f l k - k 5 ) k ® B , B). This is a consequence of the following general result. k Proposition 8 Let be a A 2-category with tensor products and let D be a small category. Letts = o"p A : D > A( A, D ® A ) be the canonical functor. Then the diagram r g f is a coequalizer diagram in A( D ® A, B) if its image fcr(u) ^ gcr(u) »• hcr(u) po-(u) /n A( A ,B) under the functor A(a(u),B) = o-(u> :A(D® A, B) > A(A,B) /s a coequalizer diagram in A( A ,B )for each object u of D . EEDOf: Suppose y: g > k is a 2-cell such that y • oc = <p • (3. Then for each object u of D <pa("u) • cxcr("u) = (<f> • so there is a unique 2-cell ^ ( 7 j ) : hcr( u) cOcrCu) = > ka(U) ® |3)o"("u) = fO"("u) • such that the diagram (3aCu), 339 kcr("u) commutes. The 1-cells h,k :D ® A >B induce functors h„,k„:A(D®A,B) • A( A,B). We now show that the 2-cells ^(Tj") constitute a natural transformation between the two functors h o~,k„o":D M • A(A,B). Let |: u • v" be a morphism of D. Then the diagram commutes. (The lower "square" commutes because the vertical composite 2-cells kcr ( • <f o"( ID and <po~( v) • gu( |~) are both the same as the horizontal composite 2-cell y<j(J).) On the other hand, the diagram 340 oca fa(u) Vcr(lT) gcr(u) ha(u) (3a(U) fa(f) ha(D gcr(f) oca( v) ga( v) Ycr(v) ha(v) |3a(v) 4*(V) <p cr(7) ka(v) commutes using either the upper or lower 2-cell arrows in the left hand square. By applying the uniqueness property associated with the upper coaqualizer in this diagram we see that the diagram ha(u)- ha(D kadi) ka(D ha(v)- ka(v) commutes. Thus we see that 4- is a natural transformation, as claimed. It now follows that there is a unique 2-cell 6: h > k such that h had!) adD ka(u) for each object u of D. Then for each object u of D, we have 341 gcr('u) I I Ycr(U) O-(U) A- ^ > D®A ^ hcr(u) gcr(u) cr(TJ) D®A kcr(u) Hence 6 ° TC= f>, as required. • Corollary 9 PCuj^® u ) k P(u ® u ) p(u ® t u ) k k k k P(u£® 5 k k ) is a coequalizer diagram in A( D ® B , B). k k • From the general considerations in their construction, the two left hand 1-cells and the two left hand 2-cells in the above diagram can be interpreted as 1-cells and 2-cells respectively in n-Alg(A)(( f | ® B , " p ® 1),(B,p)). k k We wish to show that the whole diagram is a coequalizer diagram in this hom-set. First we show that p determines a strict morphism of commutative monads and that p commutative monads. k k is a 2-cell between strict morphisms of Lemma 10 p =n ®B k k -> B is a strict morphism of commutative monads. k Proof: First we show that the diagram t® i commutes. For each morphism !•: (n,aj > (m,bj offl k 0"(n,a) B | k crCT) n k ® B k 0-(m,b) and 0"( n, a ) B k Jrff) a(m,b) njeS, t® i n ®B k k 343 t n k + 1 u. m-k+l t We need to show that these two 2-cells are equal. It suffices to show this for generating morphisms |^of D . It is easy to see that they are equal for each type. As an illustration we consider a morphism of type C2. k | = h+ p+e: (n,aj £L. = < a > (n-l,bj where h+e+2=n,a—h and 0 ' • • -f i f i + l ~ l f a a a k-l - 1 > h+1 h=a. In this case t$ (lf)and $ (1+f) are each given by the 2-cell k k t 'e+l+i-k } <x> X(1,e+l+i-k) Xe+l+i-k Next we show that ,h+l-i For each object (n,aj of f l taking the horizontal composition of the second 2-cell with k C"(n,a) : B k > f] ® B k k gives $i,(n, a) 0"(n, a) 6 |o-rn(n)) k B n ®Bj k Il (n+n) k k a(i+n, l+a) $ (l+n,l+a) v according to the description of $ on generating morphisms of type N. This is the same as the horizontal k composition of thefirst2-cell with a (n,a). It is easy to see, in a similar way, that n ®B k k rt) ® i 2 n ®g k k J[-ii®i 't® 1 and n ®B k k flx B n ®B, k rt) ® i 2 n ®& _ k n^B, i"x®i k rt) ® i 2 using the description of $ Lemma k on generating morphisms of type CI and S1 respectively. 11 p : p( U ® u ) k k >p k k is a 2-cell between strict morphisms of commutative monads. Proof: We need to show that n;®B B K 't® i U QS k n;®e U k k n® B Taking the horizontal composition of the first 2-cell with o" (n, a.) gives B ^(n, a.) h n-k while taking the horizontal composition of the second 2-cell with a (n, a.) gives 346 ^n+l-k But clearly X < 1+n ' 1+a - • = 1+ X < 'a) ,so these 2-cells are the same. n ) Proposition 12 P ( U k € k ® U ) k P ( u ® t*u ) k p(u ® u ) k k k P(u ® 5 ) k is a coequalizer diagram in k D-AlgC A)( ( f ] ® B , p ® 1),(B,p)). v k k Proof: Let (g,oc): ( f l ® B , "p ® 1 ) — k • (g ,oc) be a 2-cell between morphisms of commutative monads such that If: p( U ® u ) k »(B ,p) be a morphism of commutative monads and let k k r o ( u e ® u ) = K « p ( u ® 5 ). p k k k k k Let (n,a) be an object of f l . The image of the above diagram under the functor k cr(n,a)*:A( f | ® B , B) k > A ( B , B) is the split fork k k ^(n,a) k u t n + k 5(n,a) u„ t " u, n k t 5v n which is split by t n + k t u„ u. k We have \\> ( , ) : t n a v • X ( n ' a ) U,, 1fcr(n,a) • M ( , > u = Ycr (n,a) n n _ k u k t n t u a k > gcr (n,a) ^<n,a> k U ° t 5 n k such that the diagram so there is a unique 2-cell n _ k u. 347 QO"(n, a) commutes. Because the coequalizer diagram is a split fork, we have the explicit formula *<n.a) " Y<nn,A> • Tl(n, )UkA Further, by the argument of proposition 8, there is a unique 2-cell 6: p 6cr(n,a.) =^( , ) =Tra(n,a.) • 7 \ n fl ( N A ) >g such that k u for each object (n,aj offl^.thatis, k gcr(n, a) We check that 0 defines a 2-cell between morphisms of commutative monads 6: p Pk k > (g ,oc), that is, 348 However, by hypothesis, Y : p( U monads, so k ® u ) k •> (g ,oc) is a 2-cell between morphisms of commutative 349 P 0"(n, ( u k® u k> a) g that is, Also, the relation t T i ( n a ) equal. = 1^(1+11, i+a) clearly holds. Hence the 2-cells in the diagrams (i) and (ii) are • We have now demonstrated that thefirstpart of the coequalizer hypothesis is satisfied. It remains to check the naturality condition. 350 Lemma 13 > B a 1-cell in A . Then the coequalizer diagram of proposition 12 is Let be h: A k preserved under the induced functor F h* :D-Alg(A)((n ® B / p ® 1),(B,p)) k k * D-Alg( A)( (D ® A, p ® 1),(B,p)), v k k where F h= 1 ® h:(fl ® A, p ® 1) > ( H ® B , p ® 1). v k v k k k That is, P ( U p(u^®t u h) k *^® * U h ) k p (l®h) , _ ~ * p(u^®u h) * p (1®h) k k k P ( u ® 5 h) k k is a coequalizer diagram in H-Alg( A)( ( f l ® B , p ® 1),(B,p)). v k k Proof: One canfirstcheck that it is a coequalizer diagram in D-Alg( A)( D ® A ,B). This follows because, for k an object (n,a.) of f l , its image under cr(n,a.) * : A ( f l ® A,B) k > A(A,B) is the split fork k ^(n,,a)"kh " tuh >t"uh n n k k k t 5 h n k which is split by t n+k u h * - k • -n(n, )^U h«\< ' > n a k a U k t u h < t - u h n n k h k k ^(n, a ) U h k A slight modification of the argument of proposition 12 establishes the result. Proposition 12 and lemma 13 amount to the coequalizer hypothesis for the construction of a lifted soft adjunction (F \G ,11 ,E ,r Sv.). We now describe this soft adjunction in detail by giving explicit formulas k k k k kl for the horizontal and vertical units and counits. • The horizontal counjt £ k : F -» 1. k k u For a commutative monad (B,p), E ( B ,p): F 0 ( B ,p) k commutative monads given b y p : n ® B k k k -» (B ,p) is the strict morphism of k > B. k According to the general construction of a lifted soft adjunction given in chapter in, there is a A A k k k p : p( U ® u ) k k A A modification n : £ V ® B > £ k k whose value at a commutative monad ( B ,p) is the 2-cell > p . Hence the diagram k k Frv (B,p) Fj&CB.p)—* e;(B,p) k > F£U(B,p) • (B,p) EJB.P) in D-Alg( A) corresponds to the diagram nj;®e in A.Let(h,oc):(B,p) 1®u p ( u j ® 1) k -* (B' ,p') be a morphism of commutative monads, where (B ,p) = (B,t,TI,U,X) and (B'.p') = (B'.f ,n',P'X).Then F;U(B,P) £^(B, p) •* (B.p) F U(h, ex) <h, ex) k Z F U(B',p') 1 (B'.p ) 1 k e^B'.p ) 1 is the 2-cell between morphisms of commutative monads given by the 2-cell 352 u^®1 n® f) ® B k 1® h B 1®h id ® B' n® 1 u ® k B' p' B' in A. Let k k p'k P ' ( u ® u' ) p ' ( u ® (t') u' ) k k (0 k p ' ( u ® ?' ) k k be the coequalizer diagram in fl-Alg( A)( ( f ] ® B' , p ® 1), ( B',p')), associated with the commutative v k k monad ( B' ,p'), that is, it is the coequalizer diagram a (B',p') k Efc(B'.P') ° F n ( B ' . p ' ) o F ^ v ^ B ' . p ) £ (B',p') o F V (B',p') 1 k k k k k n£(B',p') ^ > e (B'.p') k b;(B',p') of chapter i n . Denote 0 (h,a):0 (B,p) k • G (B',p') by h : B k k k > B ' . Then, taking k k the horizontal composition of the coequalizer diagram (i) with F 0 ( h ,a), we obtain the coequalizer diagram k k p'<u*€>;°uA> p ' ( u ® (t') u' h ) k k k k k P'(u ®S h ) k k p d®fi ) -—•P' (1®h ) k _ ^ P'(u;®u' n ) — k k k k (ii) k According to the general lifting construction £ ( h ,cc) is obtained from the coequalizer diagram (ii) and k then fits into the following commutative square of 2-cells in n Alg( A). _ 353 n (B',p')°F O (h, oO k k k E ( B ' , p ' ) ° F V ( B ' , p ' ) ° F O ( h , °° k £ (h, v k k k * e (B',p')°F O (h, oc) k k k cx)oF v (B,p) k k £ (h, k k oO (iii) (h, a)oE-(B,p)oF v (B,p) k k (h, od°E (B,p) v (h, oO°n'(B,p) where n (B',p') ° F O (h,a) = p' ( 1®h )and E (h,oc) ° F v ( B , p ) is the 2-celJ between morphisms k k k k k k k k of commutative monads given by the 2-cell n ®& k " k ^ k 1® h. id Dv® B k B 1® h cx n® B' 1 u »u P „ n® B k B' p' k in A. The square (iii) of 2-cells in fl-Alg( A ) arises from the following commutative square of 2-cells in A. P' (1®h ) K k P'(u ®u' h ) k k • P'k ® k) ( 1 k h cx(u ®u ) k oc = UE (h, oO k hp(u ® k k u ) k hp, k hp. We have introduced the notation t x : p' ( 1 ® h ) k that is, k k » hp for the right hand 2-cell in this diagram, k 354 1® h, ex. n ®S' k For each object (n, a.) of H A(fl ® B ,B') k K , the image in A( B ,B') of the coequalizer diagram (ii) in K under the functor cr(n,a) „ :A(flk® cx( u ® u )cr (n,a) k k B' k k B ,B') > K A( B K is a split fork. ,B') is the 2-cell o-(n, ) fl _ _ u ® u e n ®B K k k K n® 1®h B n® B' P' cx t while hp (n, a.) = h 5 k ( n ( S ) (t') n is the 2-cell B y{n, a) t n-k Using the evident splitting 2-cell, we see that cx cr (n, a) is given by k n 355 Lemma 14 For a morphism of commutative monads (h,oc):(B ,p) > (B',p'), E (h,cx) k is 2-cell between morphisms of commutative monads given by the unique 2-cell oc O"(n,a.) k = ex < n _ k >u foreachobject k The horizontal unit T ) : 1 (n,a.) of f l k . • -» 0 F . k k k To obtain results which we can also use later on, we consider the composite 2-functor 0 F ^ where k m>k>l. For each object A of A, O F^A = D ( k ® A, "p ® 1). We shall relate this object to the Eilenberg k Moore object for the k-fold composite monad ( H , " t , T i , p ) associated with the commutative monad k m v k v k (D ,"p) = (nm."t, ri, p, \)in Cat. Using the standard description of Eilenberg-Moore objects in Cat, v v v m this Eilenberg-Moore object is the category of "t -algebras for the monad ( , " t , k k v Ti . k v M ) . which we k 356 denote by 0^ m . The objects of C\kim can be considered to be triples (n, > mis a morphism of 0. A morphism |: (n, C\^andf:k morphism ?:(n,a.) > (n , a.') of <p ,a.), where (n,a.) isanobjectof > (n , <p',a.') in f \ a.) 1 ( m such that the diagram 1 commutes. We have the usual adjunctions n k, m n where "f k Uk k and " u are given on objects by f ( n , a.) = (k+n, k, k+a.) and u (n, f,a.) = (n,a.) v k v ] c k respectively, with the obvious extension to morphisms. For an object (n, <p, a.) of n " € (n, <f ,a) : (k+n, Ji, k+a.) k n >(n, <p,aj is the unique morphism of f) commutes. The universal cone associated with • n+k * C\ k>m n+kT\ is n: n k,m U vk € k c m , such that the diagram ktm nTi+k kf k is a 357 For each object A of A , ( D ® A, t ® 1 , T \ ® i , " p ® 1 ) is a monad in A , and we have a t ® 1 -algebra v v k )c v m n;®A X® L ^Qk.mA : Hk,m® k k * Oj^F^A = 0 ( D ® A, ~p ® 1) be the unique 2-cell such that A k m k m ©V n , ®A k m k,m A u m k ; F ^k m A F V k m F A A U ^mA F ni® A 'u ® 1 k n,® A k 't ® i k m v n ®A u ®i M k It is straightforward to check that this defines a strictly natural transformation ©k,m :n , ® k m > U F . K M One can check that, if A = Cat and category product is taken for ®, then 0 k j M A is an isomorphism. However, since a tensor product is a particular type of indexed colimit while an Eilenberg-Moore object is a particular type of indexed limit, one would expect that, in general, 0 ^ is not an isomorphism. kt 358 Lemma 15 T| A:A k -» U F A is given by the composition k k o-(k,Js,Js) f] ®A k ( k • U F A : k k Proof: According to the construction of chapter HI, T| A is the unique 2-cell such that k UF A k V F,:A. k TkA njJFJA v k k F A U F k A T]-UF A U£ F A — v k UF A UF£UF A k k v > UF A k TlvA where the second 2-cell is an Q F A-algebra. This second 2-cell is k k 'k"k.® cr(k,Js) 1 n ®A n ®A k k a(2k,k+Js) A 1 Mk> a( fl ®A k ff(k,Js) where the last equality is obtained using the fact that € (k,Ji) = 7T : (2k,k+JO k k —»(k,kj 359 The lemma now follows since v o-(k,k,Js) * < \ k ® e k,k k ic F A A * VJA A z F^A k v n 'u ® 1 m k k F ^k k F A A ® A k 0"(k,k,k) • n A k i ® A m „ „ -u € ® i k k 'u ® 1 fl;®A k tr(2k,k+k) A (T(2k,k+Js) ]lo-ru € (k,Jj,k)) k fl ®A k k A v k (k, k., kj «= u : (2k,k.,k+kj » 0 £ o T| 0 . k k k k k Lemma 16 r :1 k "* k ^k ° ^ l k k u ( M K ) • (k,k.,k.), which gives the last equality. k The vertical unit r : 1 A D K ® A 0"<k,k) 0-(k,k) Notethat € I u / s t n e identity modification. Proof: For a commutative monad (B ,p), r ( B ,p) is constructed from the 2-cell k • V (B,p) k U (B,p) • U(B,p) k K T| U(B,p) TlfcV (B,p) Tl O (B,p) k k = id Y UF^U (B,p) k • UF^U(B,p) k ue UF^V (B,p) k | UnJ(B.p) ue (B, ) k P a(k,k) a(k,js) id n^®B k 1® u. V f) ® B k 1 Pk Now p o-(k,k.) = 5 , so this 2-cell is k k Thus it is the identity 2-cell on u : B k k > B. It follows that 361 Tl O (B,p) K k U (B,p) k ^ „ *> U F U (B,p) k k k r\(B,p) u e (B, ) k k P U (B,p) k V (B,p) U(B,p) k is the identity 2-cell on V ( B ,p): 0 ( B ,p) k » U( B ,p). The lemma follows by the uniqueness part of k the universal property associated with 0 ( B ,p) = B , once we show that k k TLlUB.p) * 0 F 0 (B,p) U (B,p) k k k U E (B,p) k k k k is the identity 1-cell. Taking the horizontal composition of this 1-cell with V (B,| U(B,p) k O (B,p) Q (B,p) k k V (B k U(B,p) we obtain k 'u® k u k C-(k,k,k) s B k A » n a kfk v s ® B k "U € ® 1 K K > O (B,p) t®1 k 362 CT(2k,k+Jk) -+ B a(k,k) l (2k,k+Js) k K Pk M > B ( k $ (k,Js) k The last step can be checked from the definition of $ : f l k The vertical counit 8 : £ F k k k ° F T] k -+ A(B ,B). k k -» 1. k The vertical counit, evaluated at an object A of A, namely s A , is obtained from a certain coequalizer k diagram involving two 2-cells whose vertical composition with s^A coincide. Then s A fits into the k commutative triangle E j ^ A o F ^ A E F Ao ;Ti A k k F k *k* First we identify the 1-cell LetQ :n k k > C a t E^F^A. ( l \ , D ) denote the functor $ :fl ( k k k -+ A( B ,B) of proposition 6 for k k the particular case A = Cat, (B ,p) = ( f | , p ) . Thus Q is given on objects by Q (n, a.) = " t v k for example, if % = h+p+e: (n, a.) k k > (n-l,b.) where h = < a , . . . a a 0 i f i + 1 n _ k "u and, k - l , ..., a _ - l > k 1 is a generating morphism of type C2, then Q( J) is the 2-cell in Cat (that is, natural transformation) given K by the diagram extension to morphisms. 364 Now E F A : F £ 0 F £A K K • F A is the strict morphism of commutative monads given by the 1 -cell K K > fl U£ F A:n ® O F A K K 1® 0 fl K k k / K A: D K ® (H k > A( D k Q n k kf K ® A. Take the horizontal composition of this 1-cell with k » D ® A) ® U F A k K ® A,D ® A ). This functor can be decomposed as the composition k k ~ K -®A • cat(n k ,n ) k f k • A(n k We treat £ F A o F V F A : F U F A k and consider the corresponding functor K k k k k k k ® A , n ® A)_ k f k k > F A in a similar way. It is the strict morphism of k k commutative monads given by the composition n k ® u F k k — — • n A ® ( n k ® A ) k cn xn )® A k ( u k * , (fixnp® A x 1 ) 0 1 VP ® »n ®A 1 k Taking the horizontal composition of this 1-cell with 1® © , A gives k n k ® ( n k . k ® A ) = ( n fl The corresponding functor & n k x H k ( k • A( fl kf k a t ( n k f k k k k = 1 u : ~t u v ( ( \ and for a morphism ?:(n,a.) K ® A , n k ® A ) > (m,b_) we mv k k Now we look at the 2-cell n F A. Let Z : R k at an object (n,aj o f f l is k k A »"t u . nv k * ) n have R (F) k -®A , n where R is given on objects by R (n,a_) = " t " u k k ® A,D k ® A ) has a decomposition K „ K C (Dxn )®A—-—»>n ®A ) ® A — - — - — > k > k k k k » Q be the natural transformation whose value k that is, Z is the natural transformation £ : ¥ k k ( H , p). Let q : H v k Q k k:n k k x fl »fl k /k • 9 of proposition 7 for the case A = Cat, ( B ,p) = k k be the functor corresponding to k » Cat( Hjc, jt.Ok ) and let T : p ( u xu ) v k —> q v k k : corresponding to Z . Thus T is the 2-cell p : p( u ® u ) k k k k k be the natural transformation • p for the case A = Cat, (B ,p) = k k ( f l , p). Applying the 2-functor U to v k and then taking the horizontal composition of the resulting 2-cell with ] ® © k , k A : n ^ ® ( D k , k ® A) > n k ® O F ^ A gives the 2-cell k q k ® l in A. Finally, we observe that the 1-cell F T ] A : F A k 1-cell k k > F k O F^A in fl-AlgX A) is given by the k 366 n k 1® <7(k,k,k) • n ® (n ®A k(k k l®Q k k A : ® A) • n ® oF^ A _ k K in A. Note that the diagram commutes, where X is the isomorphism of categories which switches the two factors. It is now apparent that n k k A ° kT| A is obtained by tensoring the 2-cell F F k in Cat with A. Here XCT (k, ]&, kj is the section r • : —* (r, (k,k,k)). We describe s A in the special case where A = Cat and A = E, the category with a single object. For the k sake of simplicity, we identify D x I with D when D is a small category. Then s H is a 2-cell in k D-Alg( C a t ) ( ( f l , " p ) , ( f l , p)) for which we introduce the alternative notation 0 . The general s A is v k k k given by tensoring s II = 6^ with A. k 8 I = 6 fits into the commutative triangle of natural transformations (2-cells in Cat) k k k 367 T Xcr<k,k,]s) k "p(u x u )Xo-(k,]s,]s) • v k k q Xa(k,]j,Js) k 1 in which the upper 2-cell is a coequalizer 2-cell for the appropriate coequalizer diagram. Because each "section" at an object (n, a.) of f l of the coequalizer diagram involved here is a split fork, we have an explicit description k of 6 . Indeed, for an object (n,aj o f D , 6 (n,a.) is obtained as the composition of € (n,a.) with the K k morphism of H k k k given by evaluating the natural transformation •n t at the object (k,k.,k.) of D N o w k f &) . = "n , "u (k,k,]s.) {n k k v n ,a) '& {k (n T\ thus e (n a) = € (n,a_) ° " n . v k fJ k v ( n a ) (n>a) :"t (*rJt> n-k +k: (n,n-k+Ji) > t (k,Ji) v n » (n+k,n+jc), u ( k , i , k.) can be pictured as follows. k 368 369 L e t c = q Xo-(k,k.,kJ if)* k > f l . Then s A : E F A o F ^ T ^ A k k k k k > Aisthe2-cell between strict morphisms of commutative monads given by n ®A | k H ®A ®1 k 1 The functor c k :O >H k k is given on objects by c (n, a.) = (n, n-k+k.) . Thus the base points are k all "moved to the top". To complete the description of the vertical counit, we give the action of c on k morphisms. For a generating morphism F, = h+X+e: (n,a) ai<h and h + K a 1 + 1 , we have c ( | ) = " t h _ i k ^ t v » (n,a) of H e + i - k k of type SI, where h+e+2=n, " u (k,Js,Ji) k = ^-^X^^^k) = h-i+X+e+i-k: <n, n-k+k.) > (n, n-k+k.). Thus we still have a single switching, but it occurs "at a lower level" because the base point arrows are all shifted upwards. For generating morphisms of type S2 and S3, c ( J) is the identity. k For a generating morphism F, = h+X+e: (n,a) h+l<a 1+1 and h = < a , • .., a 0 i f a i + 1 > (n,a) of type CI, where h+e+2=n, a^h , - l , • • •, a _ - l >, we have k 1 c (T) = ^-^p-t^-^u^k,*,*) k = t - p t v = h i v v e + i - (k,li) k h-i+p+e+i-k: (n,n-k+Js) > (n-1, n-k-l+k.). Thus we still have a single collapsing, but again it occurs "at a lower level". For a generating morphism % = h+p+e: (n,aj and h = < a , .. ., a 0 i f a i + 1 > (n-1, bj of type C2, where h+e+2=n, a^h - l , .. ., a ^ j - l >, c (T) is given by the value of the natural transformation k 370 at the object (k, k., k) of f \ .™ s ( k i s ^ morphism of given by the diagram For a generating morphism T=h+7T+e: (n,aj * ( n - l , b j of type C3, where h+e+2=n, . . • r a j ^ - l < c (T) a.j=h+land h = < a , . . > k 0 is the same morphism of Pl^ as for the previous case. For a generating morphism |"=h+T\+e: (n,aj a _ <h<a i 1 i andb. = < a , .. . .a^ta^+l, . . . .a^.j+l >, we have 0 C (|) k » (n-l,b.) of type N, where h+e=n, = t -i n t« - u (k,Js,Js) v v h v +i kv k = "t - ^ te+i-k = h-i+T\+e+i-k:(n,n-k+k) h i v ( k f J s ) > (n+1,n-k+l+k). 371 c has the following simpler description. For any morphism j- : (n, a.) k -» (m,b) of Dv ,Cv(f) is the unique morphism of fl £ such that the diagram ^(n, a) (n, a) (n,n-k+Js) cr(f) (m, h) (m,m-k+]s) \tm, fc) commutes. This is an immediate consequence of the fact that 9 £: c£ » 1 is a natural isomorphism. The valueof c£ at an object (n,a) ofPlk istheimageof (n,a.) under the X * ' a* isomorphism which causes the n base points to "float upwards" (retaining their order). The image of a morphism f of C\ k is the morphism of f] k obtained from % by causing arrows which map base points to base points also to "float upwards" making the appropriate adjustment whenever there is an arrow which maps a non-base point to a base point. Such an arrow has its initial and image points moved according to the prescription for c£ on objects, with the resulting arrow crossing all intervening arrows. This completes the description of the lifted soft adjunction (F^Ofc.^fc.Efc.rfc.Sfc). We have seen that it is actually a quasi-adjunction, with vertical unit the identity modification. 372 VII. The k,m Soft Adjunctions and their Liftings By attaching to the quasi-adjunctions described in chapter VI we are able to produce more examples of soft adjunctions. As mentioned in chapter VI, for m>k£l, the adjunction f k, m (n,p) v k in fl-AlgC Cat) of proposition V,5 givesriseto a strictly natural adjunction (*k\m. k\m. k,m. k,m v h ) e : F F; k whose value at an object A of A is the adjunction f ( fit® A, p® v k.m®' (n ~ ® A , p ® 1) 1) v ^k.m® 1 k, m inD-Alg(A). Starting with the quasi- adjunction (F £, 0 , T) , £ , f , s ) of chapter VI, we can apply the attaching K K K k k procedure using this strictly natural adjunction to obtain a para-soft adjunction ( Fm'^k- O f c .l-kr, m k F' k , m ' l k, m t , k,m'°k,m • •k. J- k, m n-Alg(A) We now describe this soft adjunction in detail. 373 The horizontal unit T ) , : 1 k * U F m k m . This is the strictly natural transformation given by the composition k+'k.m 1 U F k UK v Fm „ k L e m m a1 For each object A of A, T ) „fK: A > ^ F ^ /s p/Ven by the composition k A o-(m,k,m) A „ • ^k,m ®k,m A A U.F^A _ Proof: T| mA is given by the composition k ( o-(k,Js,Js) 0 < \ , k ® k , k U <Pk\m A A k A U k k F k m A Taking the horizontal composition of this 1-cell with the universal cone v ^k m F k F ; A ^kF A A m V k m F A U Fm IA gives the 2-cell (1;®A o"(k,k,k) f\,k® A X^k® 1 "t ® 1 't ® l k k id f k ® k, m m 1 •*n ®A m 374 0~(k+m, k+m) 0"(m,m) where k+s=m. The morphism y +s : (k+m, k+m) k This is the same as " u € (m, k,m) : (k+m,k+m) v k k > (m,m) of f ) can be pictured by the following diagram. m > (m, m) . The lemma follows since 375 n;®A cr(m,Js,m) A • fl k r m v ® A v 't ® X€k® 1 'u ® 1 k k 1 n ®A m 0~(k+m, k + m ) J[c3-( U € (m,Js,m) ) A V k k O ®A m 0"(m,m) • The horizontal counit £^ :F 0 k m m > k 1. This is the para-natural transformation given by the composition V m k.m k U F K For a commutative monad kU k ( B , p ) , £ ( B , p ) : F O ( B ,p) k m m » ( B ,p) is the strict morphism of k commutative monads given by ~ . n;®e "k.m® 1 ~ . *n ®B k k A To complete the description of £ » k Bm as a para-natural transformation, we need to specify the 2-cell k f m F U (B,p) m Pk k F;u (h,oO £k,m(B,p) (B,p) (h, oO k WB'.p') (B'.p') 376 > ( B ' ,p') is a morphism of commutative monads. Ej^niCh.oc) is the 2-cell in where ( h,oc): (B ,p) D-Alg(A) given the 2-cell n;® 1® B > K n;® B • B K I® h. h, id n;®B' n® k K P'v in A, where ex is the 2-cell of lemma VI, 14. k The vertical u n i t r k > m : 1 » 0 e k k f m ° T| k f m 0 k = ft k/m . This is the modification given by kk v U k*k , u k u k ;u F k Uk^k. U m U k k^k F U k £ k k Lemma 2 For a commutative monad (b ,p), f (b ,p) is given by the 2-cell km JK,. t k,m (See lemma V,16.) Proof: First consider the composite 1-cell ft kf codomain of r m ( B ,p): U ( B ,p) > U ( B ,p) which gives the k k ( B ,p). Taking the horizontal composition of this 1-cell with the universal t -algebra k k ( m B O (B,p) = B k gives K 'u ®1 ^ k 0"(k,k,Js) n k k ® B n,® 1 n ®s C\Z ® B\ k k k x €k®i v k k 't ® k 1 id id flv ® B $(m+k,k+Js) k $ (m, Is) k 378 The morphism (J +s : (m+k, k+£) > (m, Js.) of H k can be pictured by the following diagram. k m+k-1 Thus we see that $ ( M +s) is k This shows that Q k f m k ( B ,p): 0 ( B ,p) k * O (B,p)is t , : B k The horizontal composition of the 2-cell f kf cr(k,Js,Js) m k ( B ,p) with u : B k ^ n ,K® k' g k n m k® k B k k t^ ®i m k.m" L >B. k > B is n ®B k } 379 The vertical counit s kr m : 6 k > m F k °F T] k This is the modification given by k j m » 1. 380 For an object A of A, J\ is the 2-cell in f|-Alg( A) given by the 2-cell 1 in A,where we have introduced the notation g k > m = fk, c u m Foranobject (n,aj of f l , e ( n , a . ) : (n+s,n-k+m) m depicted as follows. km k k ( m :n m •D m and = > (n,a.) is the morphism of f l m It is perhaps instructive to check directly that (F ~,0 , T ) , E k k ?m k ( m , r For a commutative monad (B ,p), the composite 2-cell F;O (B, ) k (B, p) is the 2-cell in f~)-Alg( A) given by the 2-cell P k fm , 8 ) is a para-soft adjunction. kfm 382 in A. Taking the horizontal composition of the left hand 2-cell P ( uj^ ® ^ ( ® ^ k , m ^ 1 k o"(n,a.) :B > H^® k m v / ^ n B , where (n,a) is an object of f l ^ . gives the 2-cell k P 0"(n,fl)Ti k k(m = tn-*u n k krm = \"-H u s k in A(B ,B). This 2-cell can be expressed as 4> (n+sTi) for the morphism k k n+sT\: (n,n-k+k.) 2-cell P ( u k k ( i n ® > (n+s, n-k+Jj.) of D D(e® k ( m k . Taking the horizontal composition of therighthand 1) withe (n,a) gives the 2-cell £ k ( u k ( m e k f m (n,a> ) in A( B ,B). k 383 Consider the composite morphism (n,n-k+Js) n+srl u • (n+s,n-k+Js) k,m k,m ' : e (n a) »• (n,<a , 0 a _ >) Jc 1 of P l . This morphism can be depicted as follows. k The image of this morphism under $ is the identity 2-cell on u : B k modification equations for the soft adjunction. For the other modification equation, consider the 2-cell k k > B. This establishes one of the 384 A 385 0"(m,n>) n;®'A H;®A 't ® s 1 0"(m,ro) 0~(m+s, s+ m) while therighthand 2-cell is A 'U ® 1 •n ®A rc® A K kfm I ©j: 0"(s+m, s+m) A Jl ^ ( m , m > ) m D;®A a(m,uj) The composition of these two 2-cells is the identity since the composite morphism k,m ( 'ID) ° (sTl+m) : (m,m) e m of Plm is the identity, as can be seen from the following diagram. > (m,m) m ® i rc® A 386 V A t sTi+m 6 (m/lD) k m P r o p o s i t i o n1 The natural monad structure determined by the soft adjunction ( m' k''Hk,m'£k m>nc,m' k,m) F U 8 B ,p) •= B , where ( B ,p) is a commutative monad, is the o n ( k induced monad structure ( B , t , , n , , u k k m k m k / m ). Proof: We need to show that the "multiplication" is u k ( m . Taking the horizontal composition of T) O (B,p) kfm u (B, ) k U* ;f| ,mC) (B,p) F k k k • u F ; u ( B , p) P k * u F u F ; O ( B , p) k k m k k U^mWB.p) ic ;u (B, ) F k U G k with V (B,p):O (B,p) k P k ,m(B.P) >( B ,p) we obtain k 3^L 0"(m,Js,m) n, ®B k m u ®1 k n ®B m k |ej k f B «i n ®B, k, m m $ (m+s,s+Jj) v B u k,m k,m < 'in) : (m+s, s+Ji) e m k P ( , e (m,m)) B u k k m kfm > (m,]0 can be pictured as follows. n® k 388 B l k,m • It follows from proposition that the lifted 2-functor associated with the para-soft adjunction ( m.U .nk,m.£k,m. k,m.8k,in) F ; r isthe k Eilenberg-Moore functor 0m. We now go through the lengthy procedure of checking the coequalizer hypothesis for the construction of a lifted soft adjunction between F„ and 0 . We already know that there is a quasi-adjunction between these two m 2-functors, namely (F m, 0 , T| , £ , r^,, s ) . One would perhaps expect that we would arrive at exactly the m m m m same quasi-adjunction by the new route of lifting from the soft adjunction (Fm> " k''nk: ,£] , ,r] ,s ). l l fm However, we shall see that a slight variation of the first quasi- adjunction is obtained. The relevant modifications for the coequalizer hypothesis are as follows. C m Cfm k(m 389 F FmUm • m k^k,m U V m k K, m m K "k,m "k,m ^k,m^k,m = F id » / •* 1 m k U "k,m F F 'k,m ;u m k m V r m F ra"k,ra m k.m V F m k U "k,m Thenotation Q k > m = 0 £ k k/in °T) 0 , krm z k k f i n = V k f I t l °e k ( m for a commutative monad (B, p) 0 (B, p) k v U k m( 'P) B V „(B. Z k Pl k,m< .P) m^.P) k,m( -P) B ft UJB, p) is the universal t -algebra k rm l k,m B has been introduced here, so that For a commutative monad ( B ,p) , a n ®v 1® u k,m k m ® B nj® k m k 1 m n ®B m k,m k,m r n ®B k in A and b B m K ®i m ( B ,p) is the 2-cell in fl-Alg( A) given by the 2-cell k g , ® n m n ®s I v n;«s, m m k k ( B ,p) is the 2-cell in D-Alg( A) given by the 2-cell 1 ® *v k,mm uK ,t m„ n ®e m l i ® ? m k , n ®B, n ®e - m n k k 1® u k, m in A. Consider the two 2-cells obtained by taking the horizontal composition of U a Ub k m ( B , p ) with cr(n,a) :B Ua k m >fl ® B m m m k ( m where (n,a) is an object of H ( B ,p) and m ( B , ) ocj(n,a) is P 9k.m®1 „ 0"(n,a) k,n\ K,n\ H vk ® B ^ k u n m ® * m le k > m ®i n;®B $ (n+s,n-k+k) v 'k,m *k ]UkK, m e iU< n ^>) B $k ( n ' < a 0 a k-l» . 391 B t B jn-k+s using the notation of chapter VI, where h = <a -k, . . . ., a _ -k>. k m 1 a -k k ub k,m( .P) °o-(n,a) is B where b_ = <a -k, k ,a _ -k>. m 1 By arguments similar to those used to establish proposition VI,5 we have 393 Proposition 2 u t n + m u m (n,fe)m u t n _ k V " V ^ m Y - t ^ U . in t k,m /s a sp//fforfc,spit by t n4m u « t u -« t"u n_k n m ^(n,fe) u 1 m" m m m A u where b_ = <a -k, .. . ., a _ -k>. k Let m m :n„ > A( B ,B) be the functor corresponding to m U n ®B m Thus ¥ k,m® k,m „ U ^n ®B m k Pk * k B is the composition km _ n • 1 k,m _ T k „ •D; m We define a functor $ given in chapter VI. $ m r K k >m :D k,m *• A ( B , B ) *• A (B , B ) _ k m • A( B ,B) by a slight modification of the definition of <$ m m m has the same value as $ on objects and on all generating morphisms of fl except m m those of type C2 and C3. > (n-1,a.') of fl ,where h+e+2=n and For a generating morphism | = h+u+e: (n,aj m either h=a^ and a.' = < a , . . . , i f a i + i ~ l f • • • > m - l a a - 1> o r 0 a! = < a , ... j a i - ^ a j - l , . . . , a _ - l >, we l e t $ 0 m x k ( m h+l^ai and ( ? ) b e the 2-cell 394 te + l + i - m 1 (1,e+l+i-m) i<3> l,m Xe + l + i - m where j = X (k, s) ( i ) h-i i+s if i<k, i-k m t ifi>k. is a functor by essentially the same argument as the one given in chapter VI to show that $ is k a functor. P r o p o s i t i o n3 Vk,nrVm >* , k m 9'venby Y , ( n , a ) k m « Y , , k ( n a ) = t«-"lf kfni • X("-^b>u n where b_ = <a -k, .. . ., a _ -k>, is a natural transformation. k m 1 Proof: It suffices to show that the diagram %, (n,a) ^k,m( '3) n m *k.m(^ i,m(n',a') ; > K*W'*') commutes for every generating morphism of D . We do this only for generating morphisms of types SI and m C2. the checking of the remaining cases involves similar ideas to those arising in these two "test cases" in the manner of proposition VI,7. 395 Type: SI f = h+X+e: (n,aj > (n,a.) whereh+e+2=n , a ^ ^ n andh+Kai. h+1 h We have t - Xt h i e + i _ k t " Xt u h Km(D and Hence = k e m u m if i<k, ifi>k t^Xt^i-X *v.,<n,a.) • *k.m<D = " k , / ^ " - ^ 1 m ^ • *k,m(T>. whereb = a -k, . .. ., a ^ - k ^ < Jc and i,J'^, r a (n s) ( = • t ^ x , ™ • X ("" ^> u„ k which is the 2-cell If i<k, we have the relation in D: \(n-k,k) (h-i+X+i-k) = (h-i+T+e+i-k)'X ( <22>, n-k as can be seen from the following diagrammatic representation of the the left hand composite morphism. If i>k, we have: \(n-k,h) (h-k+X+e) = (h-i+X+e+i-k)X< n_)c '!2>, as can be seen from the following diagrammatic representation of the left hand morphism. Hence, using the corresponding relations in A( B ,B), we obtain r , (n,a.) •i (J) k Type:C2 A' = < a £ = h+p+e: (n,a) c • • •' i ' i + l ~ l ' a = * , (|;«Y (n,fl). kim m a k m kfm > (n-1,a') where h+e+2=n,a =h and i a k-l~^* ^e+l+i-k B 4 (Notethatu^ Ifi>k, i > kfm 1 ( k o = u<^> U k m (D lfm e+l+i-k .) - th-kptetv On the other hand, $ k m ( f ) is ^e+l+i-m B + e+l+i-m • B where j = X< ' >(i) = \ i+s ifi<k, [ i - k ifiSk. k s Suppose 12*. Then V k f m (n-l a') o ¥ f k f i n ( f ) is jn-m-1 whereti= <a -k, . . . ., a-^-k, a k i + 1 - l - k , . . . .,a _ -l-k>. m 1 The relation: X<n-k-l,b') (h-k+TT+e) = (n-k-m+i-l+M+m-i-1) (h-i+X < ' 1 holds in f l , and is demonstrated pictorially as follows. e+1+2i_m_k > + m - i ) ' X < ~*>h) n 400 Using the corresponding relation in A( B ,B), we obtain Y k f m (n-l,a'> • yk,m(T) - t - -% n m r r a »X(n-lc-l,b') .th-lc teu U m ^e+l+i-m The left hand portion of this diagram is M ] ^h-i 402 by lemma V.12. This shows that Y k fm (n-l,a') • ¥ , (T) - $ , (D • * , (n,a.) k m k Now suppose that i<k. In this case Y (n-l,a.') o k/m m ( 5) is ^e+l+i-k while $ KFIN <S)«Y , <n,a) is k m m k m for the case i>k. •e+l+i-k B *• B ^(1,e+l+i-k) •h-i •* B e+l+i-k X (n-k-l,b')| t n-m-1 B This follows from the relation in f l : (h-i+Xd»e+l+i-k) j )~(n-k,fe) which can be demonstrated pictorially as follows. (Xtn-k-l.b'J+i) -i+X( ' 1 ( h e + 1 + i - 405 n-k-1 Note that the condition a i + 1 - a S 2 is implicit in the description of 5. This implies that afc-a^k-i+l i for i<k, so h-i<a -k. • k p Let :fl ® B k > m m and let P , : P ( u k A. *k,nr V m B. m k > B be the 1-cell corresponding to the functor $ m ® k,m) :n » A( B ,B) m m * Pk, m be the 2-cell corresponding to the natural transformation u k f m k r m A. * $ , . Thus for each object (n,a) o f f l , k (T(n,a) m m n „ n;®B u k,m® k,m _ u J ¥ k , m ( n , a ) $k,n>' > a £ n ®B > k m k,m k Pk B 406 , ^n-m where h = <a -k, .... ,a _i-k>. k Pk,m : m (ri ® B m m. P®1) * ( B ,p) is a strict morphism of commutative monads and V p k m isa 2-cell between strict morphisms of commutative monads. This follows using arguments similar to those used to establish the analogous results for p and p in chapter VI. Indeed k K k k , m k,m V k,m ' Pk( k.m® k,m k,m) U t U » „ » P < £ ^k,m U k k,m® U k,m> » Pk,m Pk( k,m®5 , ) u k m is a coequalizer diagram in f ) - A l g ( A)( ( D ® B , p ® 1 ) , ( B , p ) ) and, furthermore, Uie appropriate naturalil v m m condition can be checked to see that the adjunction ( F , O , T | k m k ( m ,E 'k,m *k,m^ where m>k>l, satisfies , k fm i the coequalizer hypothesis for the construction of a lifted soft adjunction. We denote the resulting lifted soft adjunction by ( F , O , T | m m k / m , E ^ . r ^ . s ^ J . We now describe this new soft adjunction in detail, and compare it to the quasi-adjunction ( F r o . 0 , T l , E , r ^ , 8 ) between the same two 2-functors. m m m m The horizontal counit E k m :F 0 m » 1. m For a commutative monad ( B , p ) , E commutative monads given by p nk> m :E k m ©F m V k m k m ( B , p ) : F 0 ( B ,p) m :(Pl ® B , p ® 1 ) v k fm >E k m m m » ( B ,p) is the strict morphism of > ( B , p ) . We have a modification m such that for a commutative monad ( B , p ) , the 2-cell 407 F;V. (B,p) £ v (B,p) m - ^ - ^ F O (B,p) ±2 k m 1 > (B.p) k, (B,P) fi m WB,P) in D-Alg( A) corresponds to the 2-cell in A. Let (h ,oc): (B ,p) £ tx k m • (B ,p') be a morphism of commutative monads. Then it can be verified that 1 ( h ,cx) is the 2-cell between strict morphisms of commutative monads given by the unique 2-cell k,m P'k,m( : 1 ® h) m * h Pk,m such that oc k( cr (n,a.) = m oc ( n - m > u m for each object (n,a.) of f l ; that is, m B cr(n,a) m „ • Hi® B 1® h. P , • k m oc m *> B k,m B' p' k,m ( t l ) n- 408 The horizontal unit For an object U ^lk,m : ' * M F. M A of A, T| A:A > 0F K(M is the unique 1 -cell such that M U V m F A X m m k,m F m V u F k A V m m K m m F ™m A A k m 'Kjin k m K U m F^A m k, Mm k^U F;A K U F:A V K 'Hk,m' lk,m T Th 'k,m m A A - id k m Q F^A-algebra. Taking the horizontal composition of Uus 2-cell with MJF^ gives where the second 2-cell is an V F^:O F^ K K cr(m,Js,iD) A K> M "u ®1 - k »*\, ** m CJ(s+m, s+ ID) A l ^ n ( n w i D ) ) n ®A M (T(m m) f From the proof of proposition V.18 we see that T) K( ^ •. A > F^A U M CAN *As° ^ obtained by 409 using the universal cone UF;A=n;®A mm U m mm F Q F A = t ®1 m v A Z m m m mm F m A mm m UF A=fl;®A m and the t ® 1-algebra obtained from the vertical composition of the 2-cell v m tT(e (m,m) ):a(s+m, s+m) > a(m,m) with the 2-cell km UF;A = f 1 ® A m ^k m F A Q F A=~t ®1 k K m k m *t ® 1 s U m IA F u f fl;®A • m A H;®A n ®A 'u ® m k o"(m,k,m) v x® 1 m J[ 0-rt U € (m,Js,m) ) f l ® A sv k k 0"(s+m, s+m) k n ®A. 0"(2m,m+m) A t ® i m -t ® i s -» D ® A m 410 that is, we use the 2-cell 0"(2m,m+m) 0"(m,m) This 2-cell is the image under 0":f] • A( A ,Hm ® A ) of the morphism of f ) m depicted as m follows. This morphism can be given more simply as u ( X m ( s ' k > +m): (2m, m+m) > (m,m). Proposition 4 For an object A of A, T | a(m,X ' ( 8 l t ) k ( m A:A- -> UmFj^A is given by the composition , ) m, m m m m host Taking the horizontal composition of this 1-cell with V F m m U Fm ^A A m m U m ; m m F A m m V m m m F m ^m m F A A UFIA gives "u ® m A • nA m, m® A rj-(m,X ' ,II!) (8 Dr® lc> A 't ® i m 0;®A a(2m,m+rri) 0" (m, m) Since u € ( m , X < ' > ,m) v v m S m K = p ( X <'*>+m), the result foUows. s m 412 The vertical unit r ^ : ! » ^J-},, \, ^ 0 m n P r o p o s i t i o n5 f m kr is the identity modification. Pioof: For a commutative monad (B ,p), rj^ ( B ,p) is constructed from the 2-cell m (0 From the proof of lemma 1, we see that the horizontal composition of the 1 -cell U £)c, (B,p)°Tl O (B,p)with m is m k(m m 0~(k+m,k+m) Thus O E , (B,p)°Tl O (B,p)= u m k kfm m m k ( [ n :B >B . m k Taking the horizontal composition of the 2-cell 0 n , ( B ,p) ° T ] U ( B ,p) with m V kfin (B,p):O (B,p) k k m k fm m * (B,p) gives P K,m® : u k B m > nk,m® B •H ® B m m m | P , k Pk,r PkK,m®"k,m> 0"(m,m) n ®B m | p m k > m B Pk,r k,m L Thus we see that the 2-cell (i) is k,m 1 1 id. m 415 This now gives 0(B,p) U (B,pV U (B,p)m V m IKnAp) & \ / u m e k f m ( B , P ) = id To prove the proposition it suffices to show that . , u m ( B , ^ 0 (B. ) kfn P N P • ) „ „ U F;U (B. ) B B D e ( , ) m krm B we obtain $ (2m,m+m) ktm t^m(M a ' +™>) (8 m m k) P m is the identity 1-cell. Taking the horizontal composition of this 1-cell with B B U (B,p) P B 417 The vertical counit 8 k)in : £ , F ° F T) , k m m m -> 1. kf Lemma 6 For each object A of A , the composite 1-cell *A m £ FIUTrA m isgivenby c ®1:H ®A F A • F" A >n ®A. m m )c,m m A m Proof: Using the methods given in chapter VI, it is straightforward to verify that this 1-cell is obtained by tensoring the 1-cell X0-(m,X ' ,m) ( s fl; k ) n *n , m with A, where q , i s the functor given by p k m k m n: m for the case (B ,p) = ( , m v p ) . It is easy to see that this functor has the same values as those of c on all generating morphisms of D except possibly those of type m m C2andC3. The value of the above functor at a morphism g = h+u+e: (n,aj type C2, where h+e+2=n and h=a and a' = < a , . . . / a i 0 i f a i + 1 » (n-1, a.') ofPl of m - l , . . . , 3 , ^ - 1 > (or of type C3 with h+l=ai and a.' = < a , . . ., i _ i , a.^-1, . . . , a ^ - l >)is the value at (m, X < > ) ,m) ,of the natural s a k 0 transformation ^e+l+i-m 1 n m , m v u^ < 'm n: '•^(^e+l+i-m) > n: -^e+l+i-m n: ,h-i n: where j = X < ' > ( i ) . k s Since u ' v < : (m, X * ' > ,m) = (m, i,m), we obtain the same value as that given by s > 1 ( m k • 418 Proposition 7 S k,m~ S rrr EEQQI: For an object A of A, S i s obtained from a coequalizer diagram involving two 2-cells whose vertical k( composition with s „A coincide. Then S kr k ^ fits into the commutative triangle n. F;A°F;f| A m k m k,m m m 'K,m Jc, m 1 By similar considerations to those made for the construction of S in chapter VI, it suffices to describe k S k rm E for the case A = Cat, A - E, and then obtain the general description of S „A by tensoring with A. kr For an object (n,aj of Pl , the natural transformation m n where h - a - k , . < k nv TH a _ -k>, evaluated at (m, X< ' *,m) is the morphism s m ^(n,b) of fl . Then we have m K 1 + r n : • (n+s,n-k+m) (n,n-m+m) s JI(n,a.) k( = S Jl (n,a) (Ti ki (nfb) +m) = k,m< 'a) Cl^fe) ™) e n = 6 (n,a), m as can be seen from the following diagram. 4 419 420 Summary of the constructions in chapters VI and VII. Form>l,the quasi-adjunction (F ,0 ,'T) £ ,r 8 ) is obtained from the original quasi-adjunction m m m> m m> in (T) ,£,id,id) by attaching and lifting according to the following scheme. (T), m m m m m m m m e, id, id) The triangle (1) can be thought of as "commuting" in the sense that the soft adjunction given by the longest side is produced by attaching from the soft adjunction and natural adjunction given by the other two sides. Triangle (2), which corresponds to a lifting, "commutes up to isomorphism" in the sense outlined in propositions 111,10 and 11. For m>k>l, we have Uie soft adjunctions and natural adjunctions shown in the following diagram. ((+)" v V v hn ) v ^k,m' k,m' k,m' k,m ' B y _ (5) r V*k> ^k,m' ^k,m> t I. C^nV m' £ X 8 'k,m'*k,m ^ (6) (<P ,V ,h ,e ) k k k k ^k,m' k,m' k,m' k,m ^ V h •> u. e Triangles (3) and (5) correspond to attachings (that is, they "commute") and triangles (4) and (6) correspond to liftings (that is, they "commute up to isomorphism"). ) k,m> k,m' k,m ' Therighthand quasi-adjunctions in the last two diagrams, namely ( F , 0 , T| , £ , r , 8 ) and m m (F ,O ,T| ^,£^,^,8^ J , C ^ m m m m m \ , k m m ^k,m differ from T ] a n d £ in that they each contain a "twisting" which depends on k. However, in forming the m m compositions ^ 0 »i» , Q F;fj m m m „ 0 m m and F T1 E V pv »" ' * . pvQ , m m m k p v > F v "> m t p. m m m these twistings "cancel out" so that these composite para-natural transformations coincide with "Om » u « F'Tl F v m m m • u F;u m m and 5L> respectively. Then, for each k, the vertical unit independent of k. 0 £ 'mm m m m m m ^0 F m m •u £ F — m m and counit s m m K > m v coincide with * F v m and s , and hence are m 422 Bibliography [DBL] Beck, J., Distributive Laws, Lecture Notes in Mathematics 80, Springer-Verlag, (1969) 119-140. [BIC] Benabou, J., Introduction to Bicategories, Lecture Notes in Mathematics 47, Springer-Verlag, (1967) 1-77. [2DM] Blackwell, R., Kelly, G.M. and Power, J., Two-Dimensional Monad Theory, Journal of Pure and Applied Algebra, 59 (1989) 1-41. [ERA] Bunge, M.C., Coherent Extensions and Relational Algebras, Trans. Amer. Math. Soc. 197 (1974) 355-390. [TDM] Fakir, S., Monade Idempotente Associee a une Monade, CR. Acad. Sci. Paris Ser. A-B 270 (1970) A99-A101. [A2C] Gray, J.W., Formal Category Theory: Adjointness for 2-Categories, Lecture Notes in Mathematics 391, Springer-Verlag, 1974. [CPO] Gray, J.W., A Categorical Treatment of Polymorphic Operations, Lecture Notes in Computer Science 298, Springer-Verlag, (1987) 2-22. [LAD] Jay, C.B., Local Adjunctions, Journal of Pure and Applied Algebra, 53 (1988) 227-238. [2CL] Kelly, G.M., Elementary Observations on 2-Categorical Limits, S ydney Category Seminar Reports, 1987. [CTL] Kelly, G.M., Coherence Theorems for Lax Algebras and for Distributive Laws, Lecture Notes in Mathematics 420, Springer-Verlag, (1974) 281-375. [E2C] Kelly, G.M. and Street, R.H., Review of the Elements of 2-Categories, Lecture Notes in Mathematics 420, Springer-Verlag, (1974) 75-103. [SAD] MacDonald, J.L. and Stone, A., Soft Adjunction between 2-Categories, Journal of Pure and Applied Algebra, (to appear). [CWM] Mac Lane, S., Categories for the Working Mathematician, Springer-Verlag, 1972. [FTM] Street, R.H., The Formal Theory of Monads, Journal of Pure and Applied Algebra 2 (1972) 149-168.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Monad-like structures in 2-categories and soft adjunctions
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Monad-like structures in 2-categories and soft adjunctions Stone, Peter 1989
pdf
Page Metadata
Item Metadata
Title | Monad-like structures in 2-categories and soft adjunctions |
Creator |
Stone, Peter |
Publisher | University of British Columbia |
Date Issued | 1989 |
Description | One of the fundamental concepts of ordinary category theory is that of an adjunction. There are analogous notions in 2-category theory one of which is the "soft adjunction" of this thesis. In order to construct examples which exhibit the full generality of this phenomena two constructions for modifying soft adjunctions are described: an "attaching procedure" and a "lifting procedure". These two procedures are shown to be inverses of each other in an suitable sense. A special type of "commutative monad" structure on an object of a 2-category is described and it is shown that this structure can be modelled by the category of finite ordinals and all functions in the same way that the ordinary monad structure can be modelled by the category of finite ordinals and non-decreasing functions. By a standard argument for such a situation where there are 2-category objects with structure a certain "strict" adjunction" is obtained; that is, an adjunction which is essentially the same as an adjunction in ordinary category theory. Starting with a slightly extended version of this strict adjunction examples of soft adjunctions are obtained by means of the attaching and lifting procedures. The relationship between the the various soft adjunctions which arise is investigated. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-10-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080429 |
URI | http://hdl.handle.net/2429/29299 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1989_A1 S77.pdf [ 13.69MB ]
- Metadata
- JSON: 831-1.0080429.json
- JSON-LD: 831-1.0080429-ld.json
- RDF/XML (Pretty): 831-1.0080429-rdf.xml
- RDF/JSON: 831-1.0080429-rdf.json
- Turtle: 831-1.0080429-turtle.txt
- N-Triples: 831-1.0080429-rdf-ntriples.txt
- Original Record: 831-1.0080429-source.json
- Full Text
- 831-1.0080429-fulltext.txt
- Citation
- 831-1.0080429.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080429/manifest