MONAD-LIKE STRUCTURES IN 2-CATEGORIES AND SOFT ADJUNCTIONS By PETER STONE B.A. , Cambridge University, 1965 M . S c , Memorial University of Newfoundland, 1973 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE 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 this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of The University of British Columbia Vancouver, Canada Date 1 2 * . Gdk-DE-6 (2/88) (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. ( i i i ) Contents Abst rac t ( " ) Acknowledgements ( i v ) I n t r o d u c t i o n 1 I . Soft Ad junc t ions ° H.2 -Monads 4 7 m. The L i f t i n g Const ruc t ion 107 I V . Commuta t i ve Monads 175 V . Composi te Monads 230 V I . The L i f t e d Quas i -Ad junc t ions 291 V I I . The k,m Soft Ad junc t ions and their L i f t ings 372 Bib l iog raphy 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 the rich structure 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 the first category together with an assignment of a morphism of the second category to each morphism of the first category 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 some fixed "universe" 2 [CWM; 1,6]. The first achievement 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-established field with the motivation coming from applications 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 the field of 2-categories is that of finding a "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 weak quasi adjunctions. More recently, B Jay considered local adjunctions 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 the first point 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 a framework for 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 of finite ordinals 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 tk of the endo-l-cell t of the 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-category to the 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 quasi-adjunction 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 soft right adjoints 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 a final remark 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 Ca t ) , 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 H (HRZ) g g' 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 S ' f a gf a g'f a g? a gf'a g' <f a a g'f 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) *• A(A,C) ( * f > ' , f ) I > f ' o f is a bifunctor, that is, a functor of two variables. This is the horizontal composition which can be pictured as in diagram (HRZ). The category composition within each hom-set category A( A ,B) gives the vertical composition, 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 For each 1-cell f: A > B of a general 2-category A, there is an identity 2-cell f f which acts as a two-sided identity for vertical composition. For each 0-cell A there is an identity 1-cell 1 A : 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 A0( A ,B) the set of objects of the category A( A ,B), the sets A0( A ,B) are the hom-sets of a category A 0 whose objects are the 0-cells of A and whose morphisms are the 1- cells of A. The composition A0(B,C)x A0(A,B)i > A 0(A,C) 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 C a t 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 . If D represents the 2-cell g ° i p ° f . Then, by the interchange law, the 2-cell f f 9 g' is ^ ' o t p = ( g ' < x p ) a ( < p ' o f ) = ( < f ' ° g ) o ( f ' o t p ) . Where there is no danger of confusion we shall denote horizontal composition by juxtaposition — vp 'o ip = i p ' * 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 0 : A 0 > X0 for which each function A 0( A ,B) » X 0 ( F A , F B ) given by the restriction of F 0 extends to a functor F A > B : A ( A , B ) > X (FA.FB) such that the horizontal composition is still preserved; that is, the diagram 10 A(B,C) x A (A,B) •* A(A,C) FB, C x FA, B X(FB. FC) x X(FA, FB) commutes for all objects A ,B ,C of A. A^,C X(FA,FC) For example, for each object A of A we have the hom-set 2-functor A( A, _ ) : A > Cat. For a 1 -cell g:B > C, A(A,g) = g*:A(A,B) » 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 • Cat reverses the direction of the 1-cells but not the 2-cells. For a 1-cell g: B > C, A( g,A) - g*:A( CA) > A( B ,A) is the functor given by g * ( i p ) = <pog and for a 2-cell oc :g > g' between 1-cells g,g':B » C the natural transformation A(ot,A)= ot*:g* > (g' )* is given by oc*(f) = f°oc: f°g > f°g'. Let F ,6: A > X be two 2-functors. A para-natural transformation <P : F > G consists of a 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 » Gf°cpA indexed by the 1-cells f:A > B of A as depicted in the diagram Ff Gf FB cpB •* GB such that the following conditions are satisfied. (PN1) Ifoc:f »f is a 2-cell of A between 1-cells f,f :A > B , then cpf o(cpBocpA) = (Goc° cpA) • cpf, that is, FA cpA GA FA Ff cpf Gf Ff FB <PB GB FB (PN2) cp( 1A) = I D : * A > * A cpA FA • GA 'FA *(1A) = id 'GA FA GA (PN3) Given 1-cells f:A cpA -» B andg:B > C in A, (Gg° cpf) o (cpg o Ff) = cp(gof), <PA Gf cpf cpB that is, FA F ( g o f ) <PA cp ( g o f ) GA G ( g o f ) FC cpC GC By reversing the direction of the 2-cells in this definition we obtain the notion of an allo-natural transformation. We shall be concerned mainly with para-natural transformations so we omit the definition. The terminology here is different from that 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 strictly natural transformation. Stated more simply, a strictly natural transformation cp : F » G consists of a family of 1-cells cpA: FA » GA, indexed by the objects of A, such that FA cpA •* GB for each 2-cell oc : f » f' of A between 1 -cells f,f': A > B. Let cp : F > G and 0: G » H be para-natural transformations between 2-functors F ,G ,H: A > X. Then the composite 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 0f Hf FB GB HB <PB 0B 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 > X be two 2-functors and let cp, 0 : F » G be two para-natural transformations. A modification a: cp • 0 consists of a family of 2-cells aA: cpA » 0A, indexed by the objects of A, such that for each lrcell f: 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 <P cp' 0 0' a' o a : cp' o cp > 0' o 0 is defined by (a ' ° a)A = a'A ° aA. The interchange law a ' o a = (0 1 o 8 ) • ( a ' o cp) = (a 1 o 0) o (cp1 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 r f we can define a strictly natural transformation GcpF :GHF > GH'F by (GcpF)A = G( cp( FA)) where A is an object of A. More generally, if cp : H » 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 Gcp FA GHFA GH' FA GHFf GHFB G* Ff GH1 Ff Gcp FB GH' FB 15 Given 2-functors and para-natural transformations F F' the diagram of para-natural transformations F'F F'cp F'G *'F (p'G G' F G'cp G'G does not necessarily commute, although it does if cp1 is strictly natural. Indeed, evaluating at an object A of A, we have a 2-cell cp' cpA in the diagram cp'FA F' FA G' FA F'cpA cp'cpA G'cpA F'GA cp'GA G'GA Proposition 1 In the situation above cp 'dp: cp 'G ° F'cp > G'cp o cp'F is a modification. Proof: For each object A of A, 16 17 cp'FA G' FA G'cp A F' FA F' Ff F' FB G'GA G' Ff cp'Ff G' FB G'cpf G' Gf cp' FB G'cp B fcp'cpB G'GB F'cpB F'GB cp'GB Monads and Adjunctions in 2-Categories • A monad (B ,t , T i , u ) in a 2-category A consists of an object B of A, a 1-cell t: B • B and 2-cells Ti: 1 >t,u:t 2 »t such that (Ml) u • tTi = u o nt = id (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 (f ,u ,r\,e): B » A in a 2-category A, also denoted by f B Ti u € consists of objects B ,A of A, 1-cells f: B > A, u: A > B and 2-cells T\ : €:fu » 1 such that u€ • Tiu = id and €f • f r \ = id, that is, the diagrams -» uf, uf u U€ f U f €f commute. Given two adjunctions (f ,u ,T\,€) : B > A and (f ,u' ,T\' ,€') :A > A', there is a composite adjunction (tn,uD,T\D,&°):b > A' with f° = ff, u D = uu', Tp = uT\'f » riand€D = €' •feu'. 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 i-algebra (A,v,|) fortius monad consists of an object A of A, a 1-cell v: A > B and a 2-cell 5: tv > v such that 19 | • T\V = id and % • 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 fork is a fork, as above, which has a splitting 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 • d such that foe = gp, let 5 = g<p: c » 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 t 2V t v 5 is a split fork in the hom-set category A( B ,B), split by Tit V t2V TiV t V 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 domain A, a morphism of {-algebras oc: (v,g) > ( V ) is a 2-cell cx: v > v' such that the diagram 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 -» Cat (which reverses the direction of 1-cells but not 2-cells) as follows. Given a 1-cell g: A' > A, we have a functor Alg(g.t) :Alg(A,t) » 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 > g' between 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 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 > B such that w' 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. 2 3 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 tb' b' 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 ^ t B B Let u: B > B be the evident forgetful functor which forgets the t-algebra structure and let 5: tu > 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). v(a) tv(g) v(g) tv(a') 5(a') v(a') commutes by the naturality of g. In this way we obtain a unique functor w :A B w 6 such that 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 f: B » B such that 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 f u J» B B 1 B B t Proposition 2 f B c B is an adjunction in A. Proof: U6 • T\U = 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) » (B'.t'.n'.U') consists of a 1-cell h: B > B' and a 2-cell a : t'h > ht such that 27 If oc = id, we call (h ,<x) a strict morphism of monads and denote it simply by h:(B,t,TllM) » (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.) > (g,|3) between 1-cells (h,oc),(g,p):(B,t,ri,u) > (B1 ,t' ,tY ,u') is a 2-cell <f: h » g of A such that h 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 V:Mon(A) >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\' ,u1) respectively, with associated universal t and t' -algebras ( B ,u,5) and ( B',u' ,5'). Then we have an induced 1-cell V ( h, oc) = ( Mx): B * B' which is the unique 1-cell such that (h, a) B' 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. Soft Adjunctions and the Attaching Procedure 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 > 1 x- A vertical unit r and a vertical counit s which are respectively modifications r : 1 y • U £ ° U T) and s : £ F ° F T) • 1 p. 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 FT) A FA • * FUFA The following modification equations are required to hold. 30 (i) (Us°T|)«(UEFoT|T|)o (rF°T|) = id, (ii) (E°sU)*(EeoFT|U )* (e°Fr) = id; that is, the composite modifications given by the following diagrams are the identity 2-cells on T): 1 > UF and E : FU » 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-) quasi-adjunction. If, furthermore, T) and £ are both strictly natural transformations, then we have a strict 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 adjunction (cp, v ,h ,e): F > F consists of a para-natural transformation cp : F > F, a stricdy natural transformation V: F > F and 31 modifications h : 1 -> vcb, ercpv- -* 1 such that evaluating at any object A of A gives an adjunction (cpA,VA,hA,eA):FA > 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 UF UF and let £ :FU- -* 1 be the para-natural transformation given by the composition v u . . . e FU FU 1 Let r: 1 > U £ ° UT) be the modification given by the diagram T |U UcpU UVU 3 2 35 UF U* UF The other modification equation can be checked in a similar way. • If ( c p D , v D , h D , e D ) : F • F D is another para-natural adjunction, then we can attach again to the 2-functor F to obtain a para-soft adjunction (FD,U,T)D,ED,rn,8n). It is straightforward to check that this 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 ( tptp n, V Va, V h Dcp • h , e D • < p D e v D ) : F > 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 > A are 2-functors. Suppose that there is a para-natural adjunction (<p,V,h,e): U * U,whereU:X > A is a 2-functor, so that we have the situation indicated schematically by the following diagram. 36 A T) V and let s : EF ° F T) > 1 be the modif ication given by 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 c 1 B T\ U € of lemma 2. We show that these adjunctions give rise to a para-natural adjunction (cp, V ,h ,e) : V » V. Define cp :Y » V and V: V > Y on objects by setting cp(B .t.ti.u) = f and V( B ,t,Ti,u) = u respectively. Let (h,oc): (B ,t,Ti,u) > (B' ,t',T\' ,u') be a morphism of monads. Then the diagram 38 V (h, oO V(B,t,n, U) * VCB'.t'.n'.M') v(B,t,Tu u) V(B,t,Tb M) commutes, smce it is v C B w . n ' . u ' ) V(h, a) (h, oO VCB'.t'.n'.M') where the canonical adjunction for the monad ( B' ,t' ,T i ' ,u') is f B' B' Tl U' €' Thus we see V: V > V that is strictly natural. T o describe cp as a para-natural transformation we need to define cp (h, a), where (h,a):(B,t,ri,u) » (B1 ,t' .ir1 ,p') is a morphism of monads. Thus we let V(B . t , T t u) <P(B.t,Tu p) V(B,t,U lO Y(h, oc) YCB'.t'.n'.M') cp (h, oc) cpCB'.t'.n'.M') V (h, a) •* V(B,,t ,,n,.Ml) be the 2-cell 39 1 h B • B • B' f B : • Bl • 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) • (B' ,V ,T\' ,u') be a morphism of monads. Then (i) 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 0 : A • Mon( A) be the 2-functor which assigns to each object A of A the trivial monad (A, 1 A ,id,id), extended in the obvious way to 1-cells and 2-cells. We can take the object A for the Eilenberg-Moore object YFQA, but also VFQA = A .whence (cpFoA.VFoA.hFgA.eFoA ) : Y F 0 A » V F 0 A is the trivial adjunction 1 A ( ' A id 1 For a monad ( B .t.tl.u), F 0 V ( B ,t,Ti,u) = ( B , 1 ,id,id). There is a strictly natural transformation £ : F 0 Y > 1 where £( B ,t,ri,p) iFoWB.t.Ti.u) > (B.t.Ti.u) is the morphism of monads given by (u , 5 ) : ( B , 1 ,id ,id) > (B ,t ). (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) F0V(B,t,Ti, M) • (B.t.Ti. u) F0V(h, a) FnVCB'.t'.TV.M') E(B',t',Ty,u') (h, a) (B'.t'.n'.M') commutes, s i n c e (h, a) B • B' 5' u' Lemma 6 Fo A J Mon(A) T) = 1 V £ is a strict adjunction. Proof: ^ F 0 A = 1 F 0 A : F 0 V F 0 A * F 0 A and ve(B,t,Ti,p.) = 1 g : YF 0V(B .t.n.M) » Y(B,t,n,M). • We can now apply the attaching procedure using the para-natural adjunction (tp, V ,h ,e): V > V to construct a para-soft adjunction ( F 0 ,V, T|0, E 0 ,r0 ,s0). 42 f| = l Mon(A) CP V The horizontal unit T ) 0 : 1 > VF 0 is the identity natural transformation, since it is the composition 1 VF„ VF„ of two identities. The horizontal counit £ 0 : F 0 V > 1 is given as follows. For a monad (B ,t,Ti,u), £ 0 ( B ,t,T\,u) is the composition F0cp(B,t,n, M) E (B,UP) FoVCB.t.u u) »• FoVCB.t.n, u) *• (B.t.n, p) which is (B, 1B, id, id) (B , 1g , id,id) (u,5) (B.t.n p) or (B, 1B > 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'), E0( h,oc) is the 2-cell between morphisms of monads e 0 (B,t ,Tb M ) F0V(B,t,n, u) • (B.t.UM) F0V(h, oc) £n(h, oc) FoVCB'.t'.Ti'.M') (h, oc) (B'.t'.n'.M') B' The vertical unit r 0 : 1 > VE 0 °T)0V. For a monad (B.t.Ti.u), T)oV(B,t,U u) VCB.t.ri, u) • VF0V(B,t,u M) Ye 0(B,t,Ti, u) V(B,t,n, u) B | Ti B We can check directly that ( F 0 , V , T | 0 , E 0 ,r 0 ,8 0 ) is a para-soft adjunction by verifying the two modification equations. The first modification equation is trivial while the second one follows because F0V(B,t.Tu u) (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 p x 1 •D*D l x v p 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 strict monoidal functor (D,+,0) • (D', + *, 0') is a functor which preserves the monoidal structure, thatis, $ (0)=0 ' and $(f+5~) = $( T) + ( T) foreach pair of morphisms Tand Tof D-Such a monoidal 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 and u: c+c » c such that the diagrams c=0+c• T\+C • C+C C+ T[ c+0=c C + C + C u +c C+C C+ (J 48 commute. Regarding the strict monoidal category (D, +, 0) as a 2-category D_with a single object, a monoid ( C , T I , 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 to fit in more readily with subsequent ideas. The category A has as objects the finite ordinal numbers 0,1, . .., n where for n>l, n={0,1,...,n-1) and the morphisms are all non-decreasing (monotonic) functions % : n > n'; that is, functions 5 such that 0<i<j<n ?( j ) . Ordinal addition on the objects of A extends to a bifunctor "+": A x A > A . For two morphisms g : m » m' and £ :n » n' of A |+5 : m+n > 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 > 1 and u : 2 > 1. Hence the morphism pictured above is Tt+ u+1. 49 The diagrams T \ + l i+n l+M u+l 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- ^ - - ^ = lj o • 0 o' For k>0,let u <k> :k -» 1 denote the unique morphism, which can be pictured as follows if k > l . Thus u ( 0 ) = Ti, u ( 1 ) = 1, u ( 2 ) = u, u ( 3 ) = u(u+l) = TJ(l+u) and we have the recursion formula u(u ( k ) +l ) = u(l+u ( k >) = p ( k + 1 ) . An arbitrary morphism | :m »n of A can be expressed in the form T = TT(n,0> +"p(ml) + +p"<mn-l>, where rrij^ is the number of elements in the subset (J)" 1 (i) of m fori=0 , l , . . , n - l and 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(n) ( ]J(k 1 ) + 7J(k 2) + +7j(kn)) = l T < k l + K 2 + + kn> which is the "general associative law". Suppose ( B ,t ,ri,|j) is a monad in a 2-category A. For n>0, define u <n) : t n * t recursively as follows: u<0> - Ti:1 - > t uU> = 1 :t — —* t u<2> - u:t2 • t u<«> = u • u n ' "M :t2 Proposition 1 General associative Law for a monad u(n) o o U ( k 2 > o o U ( k n ) ) = M(k 1+k 2+ + kn> for n>l. (GAL) Proof: The case n=l is trivial so we start by considering the case n=2. We must show that u « ( u ( k i ) o M ( k 2 ) ) = u(k!+k 2) (A) for any kj_, k 2 , which we do by induction on k 2 . For k2=0 we have u •(p (k 1 ) o U ( k 2 ) ) = u P( U < k l ) on) as required. t For k 2=l we have u •(M ( 1 C I ) ou(k2))= u »y(ki>t _ u ou(k1+l)> as required. Assume that (A) holds for k 2 - l where k2>2. Then u » (u ° u <K2>) = = U < k l + k2>. 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 <n> • (p <ki> o u (k2) o o M (kn)) = k-,+ +k n-i J M ( k 1 + . . . . + k n _ 1 ) by the inductive hypothesis. = u (k!+lc2+ +kn) j by m e case n=2, which we have already proved. Proposition 2 Lef be (B ,t ,ri,u) a monad in a 2-category A. Then fAiere /s a un/'gue monoidal functor $:A > A(B,B) suchthat$(l) = t, $("ri) = nand$(IT) = u. 53 Proof: For an object n of A , where n>l, we set $ (n) = = t n and for each m>0, we set $ ( y ( m ) ) = u (m) p o r a g e n e r a l morphism % :m > n of A , express | in the form I = ]T(mo) + Tr (mi ) + +ll<rnn-l) where m.^ is the number of elements in the subset ( J ) - 1 (i ) of m for i= 0 , 1 , . . , n-1 and 1^+11^+ = m- Then set $ (F) = u (mo > ° u <mi > ° <>|i ("Vi-l >. This is clearly the only 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 > m' and 5:n » n'of A . We must also check that <K?°D = #(?)•$(!) for any two morphisms f: m > n and 5 : n > k of A . In view of (B) it suffices to check this for the special case % = u <ki>-t-u <k2> +.. . . +u (kn>, S~ = ]T< n>. In this case $ ( ? ° T > = <K7T<n> o(^T(k 1) +TJ(k 2) + +7(kn>)) = $ ( ] I ( k l + k 2 + + k n > ) = U< k l + k2 + +kn>) = p (n) e (u (kj.) o u (k2) 0 <>(i <kn>) by the general associative law for the monad ( B , t ,TI , u ) , = $( lT< n >) ocH7J<k1)+7J(k2> + +7(Jcn>) = $ ( ? ) • $ ( ? ) . A general composition 5 ° | can be expressed as a sum 5iFi + + 5pF p where 5 = ^ + + 5p> l= I i + + ? p and each summand has the form just considered. Hence = t ^ T i J - ^ T i ) ] 0 ° [ * ( I p ) » $ ( F p ) ] 54 = [ * (? i )o °$(5p)] • [ $ ( T i ) « » . . . . . o *(T p )] = *(Ti+ + ? p ) ° * ( F i + + T p) = <KT) •$(£). • We shall often omit $ from the notation and, for a morphism f : m » m ' of A , write $ (T) = ? : tm • tm', simply taking off the "bar". This is consistent with the notation used already in 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 n : t m + n » t m ' + n while that corresponding to n+|":n+m > n+m' is$(n+f) = t n g: t n + m >• t n + m ' . Corollary 2 Given a monoid (c.Tt.ij) in a strict monoidal category (D,+ ,0), there is a unique monoidal functor$:( A , + ,0) > (D,+ ,0) such that$( l) = c, <Kn) = :U ano* $(7T) = M-Proof: This result follows from proposition 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= h o f c where IQ-.TR > s issurjectiveand |j:s > 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 * S SUCN that |j ° %Q = £. This factorization is clearly unique. • 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<k)+m:h+k+m > h+m+1, 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 T(p)=h+k-l 8(p)-h h+m Lemma 5 For any (non-identity) collapsing morphism g:n' — — » n of A there are unique elementary collapsing morphisms plf ..., p r where r^n such that J = P"r ° °Pi a n d l ( p j + 1 ) < «(pj)for j = l , . . . , r - l . Proof: Express f in the form | = p(k0> + p<kl> +....+ p ( k n - i >, where k i>l for each i . Then we have |" = (]J(k0) +n-l)(k0+TJ<kl> +n-2)(k0+k1+p"<kl) +n-3) (k Q+ +kn_1+lT<kn-l>). 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. P i P2 P r - 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' » n of A has a unique factorization F = p"(n, j p) o o p~(n'-l, j x) as a composition of primary collapsing morphisms, where p=n' - n and n ' - l > j 1 > . . . . > jp>0. 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. 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. Lemma 7 Any (non-identity) injection f: n' > n of A has a unique factorization f = S"(n-l,i q) o o S"(n' as a composition of primary injections, where q=n • -n and 0 < i 1 < . . . . <i q<n. Proof: 5 is determined completely by its image in n. Let i q be the elements of n , taken in 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~c by 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(k>+m:h+k+m » 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 re lat ions fo r the p r i m a r y morph isms 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 relat ions f o r the p r i m a r y morph isms 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 the right in 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)= (g+s-l+n•)(m+s-l+5) for two morphisms £: m •» m 1 , 5 :n ' of A . (s+r l)(n+s-l)= (r l+s)(s-l+T l) (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)= (s+u)(-n+s+i) (PA 6) The last relation is illustrated pictorially below, where this time the 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) = [ S"(n-l,i)p~(n-l, j-1), i<j, 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 the 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 > f between functors f ,f':D » A(A ,B), there is a unique 2-cell a: f — » f (where f and f are obtained as in (i)) such that V where oc„ = A(A,oc). A functor f:D — » A(A ,B) gives for each object u of D, a 1-cell f(U) :A » B and for each morphism f~: 7J » v"of D, a 2-cell f("|~) :f( IT) > f( v~). In particular, CTQ^.D » A(A,D®A) gives for each object u of D, a 1-cell crp /\( u) : A > D®A and for each morphism f : u » Vof D, a 2-cell crp A ( f ) : ^( u~) > CD,A^> 1 1 1 3 1 The univesal property of D® A can now be restated as follows. 61 (i) Given a functor f:D > A(A,B), there is a unique 1-cell f:D®A • B 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 > f between functors f ,f':D » A(A ,B), there is a unique 2-cell oc:f » f (where f and f are obtained as in (i)) such that, for each object u of D, f f(u) f f(u) Where there is no danger of confusion we shall write cr = <TQ A . When a tensor product D® A exists in 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 A(ID : A > D*A is the inclusion functor or sectional u given by crp A( u~)( <p) = ( u , <p)where <p is a morphism of A. It can be 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 > D®A extends to a 2-functor of two variables Cat x A » 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 > B is a 1-cell of A. Then we have the functor 0"r 'D,B , g D * A (B, D® B ) A (A, D® B) where g* = A( g ,D® B). Hence, by the universal property of D®A, there is a unique 1-cell D®g: D®A > D®B such that for each morphism £ : u > v of D aD,A(17) * J l a D A ( F D®A D® g D® B aD,A ( v ) B | % B<-V D®B Given a 2-cell a: g • g1 between 1-cells g, g': A » B of A, we have a natural transformation D,B A (B, D® B ) I oc* A (A, D® B ) Hence there is a unique 2-cell D®oc : D®g » D®g' such that for each object u of D D® g A • D®A | i D ® a D®B D®g' 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 • is a functor between small categories D and E. Then we have a functor crr -> E 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 > E®A such that for each morphism £ : u > v of D a D , A ( 7 ) A H ^DJ^ D®A a D , A ( v ) f ® A E® A a E , A f ( u ) E® A ffE,Af(v) Given a natural transformation ^: f > f between functors f, f : D > E , we have a natural transformation E,A A (A, E® A) Hence there is a unique 2-cell <p®A : f®A » f'®A such that for each object u of D 64 f ®A f ® A ^E,A f ( u ) | a E Al f ' ( u ) E 0 A *E,A f ( u ) This makes -®A : Cat > 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 * A and - ®A : Cat > A to be compatible in a suitable sense. Firstly, given a 1-cell g.A > B in A and a functor f-.D » E the diagram D® g E® g D® B f®B E® B must commute. For each morphism of g: u » vofD, the horizontal composition of both (E®g)( f® A) and (f®B)(D®g) with W 7 ) 11 %JV D® A is the 2-cell a D , A ( v ) ffEBf(u) E®B a£>Bf(v) 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 > g' be a 2-cell between 1-cells g, g': A > B of A and let <p: f > f be a natural transformation between functors f, f : D » E. Then we require that f ® A E® g D®A J [ ¥ ® A E®A J | E®oc E®B f ® A E®g' D® A D® g D®g' f ®B f ®B E® B For each object u of D, the horizontal composition of both of these 2-cells with ap A(If) : A > D®A is g a f(u) J | a B J | ^ F R < P ( U ) E ® B 9 W ( 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 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 of an indexed colimit [2CL]. The functor CJQ ^ or its image in A( A ,D®A) constitutes the "universal (u', V) indexed by pairs of morphisms £ : u * u', 5 : v •* v' of D and E respectively. Suppose given a functor f:D><E * A(A,B). On the one hand there is a unique 1-cell f :(DXE)®A * B such that 67 a D X E , A U V ) A Jl °"DXE,A(?'5 } ( ° X E ) ® A -aDxE,A ( u' V' } f ( u , v) f ( U', V ) for each pair of morphisms g : u » u' , 5 : v > v' of D and E respectively. On the other hand there is a unique functor fg : D » Cat( E, A( A,B)) such that, for each pair of morphisms f": u" > IP , 5~ : V > v5 of D and E respectively, fo(?)(¥) = f(T. T) as 2-cells in A(A,B). For each morphism | : u > u' of D we have a natural transformation f f / T ) : * foCu1) between functors f0(TD ,f 0( u1): E > A(A,B). Hence there is a unique 2-cell f0TTD E® A I f0Tf) B such that f (u , v) J]i(5,5) f ( u1, V) for each morphism 5 : v » v' of E. This defines a functor A(E®A, B) -» f 0 7 p so there is a unique 1-cell fD : D® (E®A) * B such that for each morphism g : u > u' UD, E® A ( 1 J ) E® A J, aD, E® A^ F) D ® ( E ® A ) -ffD, E® A(^) -*B E® A Thus f11: D®( E®A) » B is the unique 1-cell such that D, E® A A | a E , A ( ? ) E ® A Jl °"D, E®A<F> D ® ( E ® A ) aE,A ( v l ) aD, 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 A E , A ( V ) A D , E ® A ( u ) A l a E ^ ( 5 ) E ® A J l a D , E ® A ^ D ® ( E ® A ) a E / v , ) aD, E® A<U'> in the universal co-cone of D® (E®A) corresponds to the 2-cell °"DXE,A( u",v) A JlaDxE,A(F,5) (DxE)®A 69 0-DxE,A^',V) 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-Monads and Algebras A (strict) 2-monad ( T ,T| ,J1) defined on a 2-category A consists of an endo-2-functor T : A > A and strictly natural transformations T): 1 > T , Ji: T 2 > 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. Proposition 9 Let (D, +, 0) be a strict monoidal category and let A be a 2-category with tensor products. Let T = D®-: A- > A and let T|: 1 - > T , J 1 : T 2 > T be the strictly natural transformations given by T]A = cr D A(0): A > D®A v p ® 1 | I A : D ® ( D ® A ) = (DxD)®A - •—• D ® A where v p is the functor of two variables given by the monoidal addition. Then ( T , T), Ji) is a strict 2-monad. Proof: First we show that the diagram 71 TA • T2A commutes for each object A of A. NotethatTT|A: TA > T 2 A is 1 ® a D A (0) :D®A- D® ( D®A). For each morphism | : u > u' of D we have V A ( T 7 ) l ® a D A ( 0 ) A J l ^ D A ^ D ® A : »-D®(D®A) "p ® 1 (Dx D)®A *• D ® A V A ( U ' } °D, D ® A ( U ) °D A ( 0 ) f ii * "D ® 1 A z£ • D ® A | 0 D , D ® A ( ^ ) D ® ( D ® A ) = (DxD)®A * D ® A °D,D®A ( u , ) V D > A ( u , 0 ) A I V o A ^ 5 (DxD)®A 'p ® •D ® A V D i A ( u ' , o ) 72 Hence the diagram D® A 1®°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 TA T|TA • T2A commutes. First note thatT)TA :TA • T2A is CXD)D®A (0> : D ® A * D®( D®A). For each morphism | : u > u' of D we have V A ( U ) A | a D , A ( ? ) D ® A . JD, D ® A ( 0 ) VP ® 1 »>D®(D®A)=s (DxD)®A *• D ® A % D A ( 0 , u ) Jl V D A ^ ' ^ ( D X D)®A * D ® A V D , A (0 , U ' ) 73 V A ( U ) V A ( U ' } Hence, by uniqueness, the diagram °D, D ® A ( 0 ) D® A • • D ® ( D ® A ) 112 (DxD)®A 'p ® D® A commutes. Lastly we show that the diagram JJTA TUA commutes. Note that T JiA is 1® (-p® 1 ) D ® ( D ® ( D ® A ) ) = D®((DxD)®A) »-D®(D®A) Let | : u » u' , 5 : v > v' and V : w » w' be morphisms of D. Then 74 A Jl °D,A ( V ) D® A | °"D. D® A<5) D® (D® A) | °"D, D® (D® A)<D D ® ( D ® ( D ® A ) ) 1 ® (v p® 1 ) v p ® | s D ® ((D x D)® A) »• D® (D® A) £ (DxD)®A *• D ® A A Jl ° " D x D A(5.v) (DxD)®A Jt a D, (DxD)®A(F) D ® ( ( D x D ) ® A ) etc. = A Jl ° D x D , A ( ? ' ^ (DxD)®A '—> D® A JlaD, D® A (Ti D ® ( D ® A ) s etc. = A | °D, A (^ +v ) D® A 1 °"D, D® A(T) D® (D® A) = (DxD)®A—P_®—U D ® A A J l aDxD,A ( 5' 5 +^ (DxD)®A " P ® 1 » D® A A Jl°D,A(^ + 5 + ^ D ® A On the other hand Ji TA is D ® ( D ® ( D ® A ) ) s ( D x D ) ® ( D ® A ) p® 1 •* D® (D® A), 75 For morphisms % : u » u' , 5 : v > v' and V : w > w' of D , as before, we have A | °D,A ( V ) D® A JI°"D, D® A ^ ) D® (D® A) 1 °"D, D®(D® A)(T) D®(D®(D®A)) v p ® 1 "p®1 = (D x D) ® ( D® A) > D® (D® A) = (DxD)®A *• D ® A A ! ° D , A ( v ) D® A i crDxD, D® A ( l . ? ) ( D X D ) ® ( D ® A ) 'p ® 1 D® (D® A) £ (DxD)®A etc. A J l aD,A ( v ) D® A | aD, D® A ( ? + ^ D® (D® A) = ( D x D ) ® A — P ® 1 » D ® A A l aDxD,A (* + ^ (DxD)®A " P ® 1 > D® A A | cr A ( | + 5 + v) D® A as before. We obtain the desired commutative square by uniqueness. 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 proposition 9 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 > B be the corresponding 1-cell, that is, the unique 1-cell such that aD,B ( 1 7 ) Hu) for each morphism % : u » u' of D. We show that the diagrams 77 (ALG) D® B V B ( 0 ) D®(D®B )-112 ( DxD)®B D®B D®B B commute. The first diagram commutes because $( 0) = 1 Q. To show that the second diagram commutes let £ : u > u' and £ : v » v' be two morphisms of D. Then ' D x D . A ^ °DxD,A^ '5) (DxD)®B 'p ® 1 D®B aDxD,A ( u'' V , ) V B ( U + V ) B H.B(* + 5> D® B <K u+v) <{>( u' +v') On the other hand, °D, B ^ *(u)$( v) B Jl $(D$(T) B $(u')$(v') *(u') ° D , D ® B ( v ) $(V) B Jl °b B ( ^ D®B i°D, D ® B ( 5 ) D®(D®B) 1 ® p °D,B<U'> °D,D®B ( V , ) D® B °D,B ( U ) & 1°D B (F D® B • °D,B(V ) + & 1°D, B ( 5 ) D®B-°D,B(V') also. $(u) $(u') $(v) Conversely, suppose that p:D®B B is a 1-cell such that the diagrams (ALG) commute. Let $: D > A (B, B) be the corresponding functor, that is, for an object IT of D, $ (ID is the 1 -cell 79 B ff(u) D® B and for a morphism g: u > 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 the first part 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' respectively. A morphism of 1-algebras (B ,p) > (B',p') is a pair (h,a) where h:B » 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) T2B T 2 h JiB id T2B' JiB1 Tp' " P' Given two morphisms of T-algebras (h,oc):( B ,p) > (B' ,p') and (g,(3):(B ,p) > (B' ,p'),a 2-cell between morphisms of T -algebras i f : (h, a) > (g, (3) is a 2-cell i f : h > g such that P . „ P 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) > ( B' ,p') is called strict if oc = id, in which case we denote the morphism by h:(B,p) » (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 ~* T-Alg s(A) Tl U £ 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 is the structure map, £( B ,p): FU( B ,p) * (B ,p) is p:(TA,JiA) » (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, v p ® 1 ). Recall that, strictly speaking, Jl A is the composition of "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) » (B',p') of let £(B, p) FU(B,p) FU(h, a) (B,p) £ (h, a) (h, oc) FU (B1, p')-£(B', p') •(B\ p') be given by the 2-cell 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 ) T) U £ 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 A ® B -•n of A . lcr(I) cr(n) for each morphism £. m Conversely, a A -algebra (B , p) gives rise to 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,oc ( 1 )): (B ,t,ri,u) » (B' ,t',T\J ,u') be a morphism of monads, that is, a 1-cell in Mon( A). Let (B ,p)and (B' ,p') be the A-algebras corresponding to these two monads with structure maps p: A ® B » B andp1: A ® B ' > B' respectively and let be $:( A ,+ , 0 ) > A(B,B), : ( A ,+ , 0 ) > A( B' ,B') the corresponding monoidal functors. Then we have the composite functors 84 A (B, B) A (B, B' ) A A ( B', B' ) A (B, B1 ) whereh«= A(B,h) and h*= A( h,B'). For each object n of A , h„<Kn) = htn and h*$'(n) = (t') n and-we have a 2-cell B- B a' (n) B'. (t' ) n n copies Lemma 12 ex : h*$' > given by cx(n) = ex'n> is a natural transformation. Proof: We need to show that the diagram (V)mh a (m) (t ' ) n h-a (n) ht' commutes for each morphism f: m > n of A , that is, 85 where £ = and £' =4>( ?'). It suffices to show this for the generating morphisms T\and p., but this follows immediately from the definition of a morphism of monads. • It follows from lemma 12 that there is a unique 2-cell a : p'( 1 ®h) > hp such that p t n B A, B A ® B B id 1® h oc. B' a A , B' ( n ) • A ® B' P' B' (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 O-(O) p B — * A ® B 1 id 1® h oc B' CT(0) • A ® B' identity B' 86 is immediate. To show that "p eg) 1 p A ® ( A ® B ) £ ( A * A ) ® B »-A®B *• B 1 ® (1® h) A ® (A ® B') = (A xA )® B' id 1® h a 'p ® 1 A ® B' P' B' 1 ® p p A ® ( A ® B ) »• A ® B * B 1® (1® h) A ® ( A ® B' )• 1® a 1® h 1 ® p A ® B' P' B' let m and n be two objects of A. Then cr(m,n) v p ® 1 p B * (A xA )® B • A ® B id 1® h id 1® h oc cr(m, n) (A xA )® B' 'p ® 1 • A ® B' P' C7(m+n) , B • • A ® B mfn 1® h id V B' a(m+n) • A ® B' P' 87 while <T(n) 0"(m) 1 ® p p B — — — > A ® B — • A ® (A® B) ^ A® B - > B B' o-(n) • A ® B' 1® h ® (1® h) cr(m) • A ® (A ® B') 1 ® oc 1® h oc Z1 1 ® p ' A ® B' p' ->• B1 cr(n) . p rj(m) p B • A ® B *• B »• A® B -1® h V id 1® h oc B' o-(n) •A® B' P' B' fj(m) • A ® B' P' B' B »• B *• B •^ nri-n B * B ry(n) oc(m>^ B'-(t') n •B' (t') r B' 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) > (B1 ,p') is a 1-cell in A-Alg( A). Let t B B B ^ — * A ® B P- B « 7 1 ® h id o c ^ 88 Then we can show, by induction, that B B oc' (n) cr(n) A ® B id 1 ® h oc B' • (t')r •B' B' cr(n) A ® B' for each object n of A. The case n=0 is immediate and we have t n t B B'-B B ™ < n > (t') n •B' P' B' B 2liL> . A ® B P — * B ^ i 2 _ * A ® B £ „ B B' id 1 ® h a id 1 ® h A® B' cr(n) ~ P' by using the inductive hypothesis, B' (7(1) • A® B' p' B' a( n) a( l ) 1 ® p p B • A® B • A ® (A® B) • A® B -id 1® h id 1®(1®h) 1 ® a 1® h oc B' a(n) • A ® B' cr(l) A ® (A ® B') 1 ® p' A ® B' P' "p ® 1 • »• A ® B 1® h 1® h id id B' a( 1, n ) (A X A )®B' 'p ® 1 A ® B' since (h ,<x) is a 1-cell in A - Alg( A), (rf 1+n ) p B 1 • A ® B id cr( 1+n ) • A ® B' Let | : m » n be a morphism of A. Then B A ® B £ » B 1 ® h A ® B' or(m) o ^ P' B' (rfn) 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 I1)) »(g,|3 (1>) be a 2-cell between morphisms of monads and let (h,oc) and (g,|3) be the 1-cells in A-Alg( A) corresponding to (h,cx <X)) and (g,(3 (1>) respectively. Then, for an object n of A, we have B Hence <p : ( h ,cx) • (g ,(3) is a 2-cell in A -Alg( A). Conversely, it is clear that a 2-cell in A -Alg( A) 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 (h,cx):(B ,p) > (B',p') in A-Alg( A), the corresponding morphism of monads is (h,oc ( 1 )):( B ,t ,T\,(j) • (B'.t'.Tr" ,u') where rx ( 1 ) = ocO"( 1). Going in the opposite direction, if (h, J3): (B ,t ,T\ ,u) > (B' ,t' ,T\' ,u') is a morphism of monads, we shall denote the corresponding morphism of A-algebrasby (h,"J3"):A » (B',p'). Thus "J3"cr( 1) = |3. Let (E ,t ,T\ ,Li) 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 vp:A xA > A is given by the monoidal addition. If v$ : (A ,+,0) > Cat( A , A) is the corresponding monoidal functor, this monad can also be denoted by (A , v t , vTi, vu) where~t = 1) : A » A is the functor given by "t( |) = 1+| , VT\ = rQ: 1 > v t is the natural transformation given by vT\( n) = ti+n: n > n+1 and vp= M):( v t ) 2 >vt is the natural transformation given by "u(n)= p+n:n+2 > n+1. For 92 an object A of A, (A®A, vt® 1 , v ,n® 1 , "p® 1) is just the free monad (A®A , , 'p® 1). Indeed, the tensor 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 > E and let A be an object of A. Let $ : (D,+,0) » Cat( E ,E) be the corresponding monoidal functor. Then we have a monoidal functor ¥ : (D,+,0) > A( E®A ,E®A) given by the composition $ - ® A (D,+, 0) * Cat(E.E) »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)® 1 A Jl °E, A ( ? ) E®A J ,#( I ) ® 1 E®A °"E A ( p ( u , e ) ) A Jl°E, A ( p ( E ® A °f_ A (p(u ' ,e ' ) ) a D x E , A ( u ' i ) A J l a D x E , A ( 5 ' 5 ) ( D x E ) ® A a D x E , A ( U ' ' e , ) °E, A ^ ° D , E ® A ( U ) p ® 1 E®A A ! ° E A ( 5 ) E®A J l ° D , E ® A ( ^ D ® ( E ® A ) s ( D x E ) ® A E®A °E,A(e') ° D , 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) (h,oc):(B.p)- (B' ,p') is a morphism of D-algebras if and only if the natural transformation oc corresponding to the 1-cell oc satisfies the conditions: (A) a ( 0 ) = id:h »h, (B) $(v) *'( v) for each pair of objects u,v 0/ D. *(u) $'(u) $'( u+V) (ii) /.ef (h,a), (g,|3): (B ,p) > (5' ,p') be two morphisms of D-algebras. Thena2-cell (f: h > 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 transformation from $ 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 tr( v) cr( u) 1 ® p p B * D ® B »> D ® (D® B) *- D® B B 1 ® (1® h) 1 ® a ® h a D ® (D®B' )• 1 ® p ' D® B' P' B' cr( u,v) "p ® 1 p B • (DxD)®B — »-D®B 1® h (DxD)® B' 1 ® h oc 'p ® 1 -*• D® B' B' 96 This gives (B). (A) is immediate. (ii) This follows by generalising the argument used to compare the 2-cells of Mon( A ) with those of A - A l g ( A ) . * - • Proposition 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 - A l g ( C a t ) x A > D-A lg(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 - A l g ( C a t ) » D-Alg(A) is a 2-functor. Let (h ,oc) : ( E,p) > (E'.p 1 ) bea 1-cell in D-Alg( Ca t ) . Let ¥ and ¥' be the composite functors $ . - ® A ( D , + , 0 ) and ( D,+, 0 ) Cat (E, E) C a t ( E ' , E ' ) ® A 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 $ ( " v ) ® 1 E®A E®A h® 1 oc( v ) ® 1 E'®A 4>'( v ) ® 1 E®A h® 1 h® 1 E'®A 4>( u ) ® 1 E® A cx( u ) ® 1 h® 1 E'®A $ ' ( u ) ® 1 E'®A $ ' ( u ) ® 1 97 cx(0)®1 = id:h®1 »h®1and $( v ) ® 1 $( u)® 1 E®A ' »• E® A > E®A h® 1 oc( v )® 1 h® 1 cx( u)® 1 h® 1 E'®A $'( v )® 1 E'®A-4>'( u)® 1 E'®A $ ( U + V )® 1 E®A — • E®A h® 1 oc(u+ v)®1 h® 1 E'®A • E'®A $ '("u + V ) ® 1 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 aCe) cr(ID p ® 1 A • E®A • D®(E®A) = (DxE)®A —•• • E®A 1 ® (h® 1 ) h® 1 D®(E'®A) = (DxE')®A p ' ® E'®A 98 a(e) *( u)® 1 A • E®A *- E®A h® 1 Tf(u) = cx(~u)® h® E'®A-$ ' ( u ) ® 1 E'®A cr(e) ( j ( u ) ® 1 A *> E® A *> (DxE )® A ( Ixh)® 1 (DxE')®A E® A cx ® 1 h® 1 p' ® 1 E'®A cr( u,e) (DxE)®A ( Ixh)® 1 (DxE')® A E® A a ® .1 h® 1 E'®A p 1 ® 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 $ ( u ) ® 1 E® A *• E®A $ ( u ) ® 1 E®A > E®A <p ® 1 PC u ) ® 1 g ® 1 # g® h® 1 h® 1 E'®A-* ' ( u ) ® 1 E'®A E'®A-oc( u ) ® 1 * ' ( U ) ® 1 E'®A 99 for each object IT o f D. Hence <p® 1 : (h® 1 ,cx® 1) > (g® 1 ,(3® 1 ) is a 2-cel l i n D-Alg( A ) . It is clear that the preceding constructions make-®A:D-Alg( Ca t ) > D-Alg(A) into a 2-functor. It is easy to see that for a f ixed object (E,p) o f D-Alg( C a t ) , (E,p)®- : A » D-Alg (A) is also a 2-functor. In particular, for a 1-cell g: A > A1 in A , 1 ®g: (E®A ,p® 1) > (E®A' ,p® 1 ) is a strict morphism of D-algebras. • An alternative derivation of the soft adjunction of chapter I W e now give an alternative construction of the para-soft adjunction described at the end o f chapter I. Let H denote the category which has one object 1 (and one morphism). There is a trivial monad structure on I for which the corresponding A-algebra structure map is the unique functor A x II = A • H. W e denote both of the functors A x I > I and A * I by f 0 . L e t u 0 :1 » A be the inclusion functor given by u0( 1) = 1. Then, since 1 is a terminal object i n A , we have an adjunction A , I \ u 0 id given by the natural isomorphism I ( f 0 ( n ) , l ) £ A(n,u0( 1)). The unit T I 0 : 1 > u 0f 0 is the natural transformation given by T \ 0 ( n ) = Li : n > 1. A s mentioned previously, there is a "left hand" monad structure on A with sructure map given by the monoidal addition "p = "+":A xA > A. Then we have ( A , vp) = (A /\,"r[/u), where "t : A > A is the functor given by "1(1") = 1+1 , "r\: 1 • vt is the natural transformation given by v T i ( n) = T\+n: n > n+1 and vu : ( v t ) 2 > "t is the natural transformation given by ~u(n)= u+n:n+2 > n+1. 100 Lemma 17 Let u 0 : " t u 0 > u 0 be the natural transformation given by M0( n) = u : 2 • 1. Then ( u 0 , " u 0 " ) : ( U ; f 0 ) > ( A , " p ) and f 0 : ( A , " p ) > ( I , f 0 ) are morphisms of monads and the adjunction fr in Cat enriches to the adjunction fr (A , VP) H id in A-Alg( Ca t ) = Mon(Cat), fhar/'s, to the adjunction (A,vt.vT\1vM) , 1 TIQ (U 0,U 0) I ( J Proof: ( I , l.id, id) id, since (u 0 e vnu 0 ) ( ! ) = U 0 ( l ) v nu 0 ( 1 ) = u(Tl+l) = 1. 101 since p0( l ) v uu 0 ( l) = p(p+i) = p(i+ p) = p0( i r t u 0 ( l). Thus (u 0 ,p0):(II,1 ,id,id) » (A,"t , v Ti, vu) is a morphism of monads. f 0:( A,"p) > (2, f 0)is clearly a strict morphism of monads. 1 since p 0f 0(n) vtTi0(n) = u(l+ p <n>) = u <n+1> = Tt0vt(n).Thus n 0 : 1 > (u0,p0)f0 is a 2-cell in 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 ® V p ® 1 ) t "* ( I ® A , f 0 ® 1) TiQ® 1 ( u 0 ® 1, " p 0 ® 1") 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 > 1 ® A is a natural isomorphism A = H ® A. Let p0: A ® A — • A be the composite 1-cell fo ® 1 A® A > H®A = A. Then p0 is the structure map for the trivial monad structure on A; (A,p0) = (A, 1 A , i d , i d ) . Hence we have the following adjunction in Mon( A). PQ ( A ® V p ® 1 ) ( " (A, P0) TIQ® 1 (ff(l),"ff(IT)") i d Note that 1 A | a ( u ( n > ) A® A o-(i) Let A 1 Non(A) Tl V £ 103 be the quasi-adjunction obtained by applying proposition 11 to the current situation. F is given on objects by FA = (A®A,s/p®1) = (A® A,"t® 1 /TI® 1 ,"u®1) and V is the evident forgetful 2-functor. T): 1 > 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) > (B ,p). For a morphism of monads (h ,oc): (B ,p) > (B' ,p'), £ (h ,cx) is the 2-cell between strict morphisms of monads given by P A ® B B 1® h rx A ® B1 p' B" As before, let F 0 : A > Mon( A ) be the 2-functor given on objects by F0A = (A,p0) = (A, 1A ,id ,id), with the obvious extension to 1-cells and 2-cells. By varying A the adjunction (A® A , v p ® 1) r^® 1 (A, P 0) ( ( T ( l ) , " f f ( M ) " ) ^ gives rise to a strictly natural adjunction (cpo.^O' ^ 0' e o ) : F * Fo« where e 0 is the identity modification. Hence, by means of the attaching procedure, we obtain a para-soft adjunction (F 0 ,V,T| 0 ,E 0 ,r 0 ,s 0). ...> M o n ( 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 The horizontal unit T) 0 : 1 > VF0. For an object A of A, T) 0A is the composition T|A a ( 0 ) V FA • Vcb0A A ® A VF0A The horizontal counit E 0 : F 0 V • 1. For a monad (B ,p) = (B ,t,fl,p), £Q( B ,p): (B ,p 0 ) ——> (B ,p) is the morphism of monads given by the composition (B, P 0) (cr(l),"o-(p) ) ( A ® B, vp® 1) (B, p) , that is, it is (t,"p"):(B ,p0) • (B,p) or (t.p): ( B, 1 B ,id,id) > (B.t.n.u). Note that "p"cr( n) = p<n+!> : t n + 1 > t n for each object n of A . Suppose (h ,oc): (B ,p) » (B' ,p') is a morphism of monads. Then £ 0 ( h ,oc) is the 2-cell between morphisms of monads given by o-(i) , p B » A ® B id cr(l) A ® B' The vertical unit r 0 : l . >Y£ 0 oVT] 0 . For a monad (B ,p), r0( B ,p) is the 2-cell T|V(B,p) Vcb0V(B, p) V ( B , p) • VFV(B, p) • VF QV(B, p) (7 (0) A ® B 1 7* A ® B V E ( B , p) V ( B , p) c r ( l ) B |ff(T\ 0(o)) A ® B cr(0) The vertical counit s0: E 0 F 0 o F 0 T | 0 >1. For an object A of A, s 0 A is the 2-cell between morphisms of monads given by 106 F0Vcp0A FQVF0A V0VFQA (A, P 0) | id (A, P Q) Thus we see that (F0,V,T|0lE0,r0ls0) is the same soft adjunction as that obtained in chapter I. The 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 V F 1 i Mon(A) 107 HI. The Lifting Construction for Soft Adjunctions Let (F ,U,T| ,£ ,r,s) be a para-soft adjunction where F: A > X and U :X > A are 2-functors. Let Q denote the para-natural transformation U £ ° T) U: U > U and let m : Q ° Q > Q be the 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 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 ) > A . Note that U = VM : X > A . Let 0 = VM : X > A . Then the para-natural adjunction (cp , v ,h , e ) : V > V described in chapter I, whose value at a monad (B ,t ,T\,U ) is the canonical adjunction (f ,u ,T\ ,e): B > B, gives rise to a para-natural adjunction ( c p , v , h , e ) : U >0 where cp = cpM, V = V M , h = hM and e = eM . Note that h = r: 1 • • O = V cp. The following proposition summarises the situation. Proposition 2 Given a para-soft adjunction ( F , U , T ) , £ , r , 8 ) between 2-functors F : A > X and U : X » A , there is a 2-functor 0: X » 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-soft adjunction (cp , v , h , e ) : U > 0 such that for each object X of X, (cpx, vX.hX ,eX) : UX > Ox 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. 115 Lemma 3 For each object A of A T|A UFA T)A T)T)A T] UFA UFA UFT)A 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 UFA T|A T|T)A T|UFA UFA UFT)A UFUFA l O F A o Q F A U£FA UFA 116 U F A , U P U F A U £ F A _ U F A T)A / T ] U F A \ T ) U F U F A X ^ U F A T1T1UFA J). \ TIUEFAJI T]T ]A\ ^UFA U F U F U F A U F U F A U F A UFA ' UFA ^ .UFUFA T)A UFA T|UFA \T]UFUFA T|T|UFAJ[ \ TIUEFA| UFT]A UFT)UFA UFT)T)A^ UFUFTjA UFUFUFA UFUFA UEFA ^ UFUFA ^ UFA ,T]UFUFA X'HUFA UFT1A >^ T|UEFA]J UFA ,V UFUFUFA \ * V UFUEFA UEFUFA UFUFA KUE FA 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 > UFg °T)A /s a morphism of QF B -algebras from to Proof: 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) »X(FA,X). For each object X of X let £X: F UX • X be a chosen coequalizer "object" for the two 2-cells aX and bX, so that we have a coequalizer diagram 123 a X £ X o F Q X o F V X E X o F V X nX ex b X 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 a Y o F U g e Y o F Q Y o F V Y o F U g Consider the diagram b Y o F U g a Y o F U g E Y o f f i Y o F V Y o F U g bY o F U g ( E g " F Q X ° F V X ) o ( E Y ° F Q g ° F V X ) g o a X g o e x " F Q X ° F V X nY o F U g E Y ° F v Y o F U g - * e Y o F U g nY o F U g C Y o F V Y o F U g - » - e Y o F U g E g o F v Y g ° e x o FVX g o n X eg g ° h g o bx A initially excluding the arrow for Eg. The left hand and middle arrows are the 2-cells given as follows. 124 FUX FUg FVX FQX FUY FVY FQY FVX FVY 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. j * of the right hand square shows that n: £ ° F V » £ 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. A* r. Let Q denote the para-natural transformation U £ ° T) U : U > U and consider the modification A. A. A. c: V » V o Q given by the diagram 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. A. Using the uniqueness part of the universal property of UX, it follows that r: 1 > 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 r A - A • > n FA ° FTi A £ FA ° Ff]> FA ° FT)A ^ £ FA ° FT)A ; ! • £ FA ° FT] A bFA ° 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 A coequalizes the two 2-cells aFA ° F T|A and bFA ° FT)A. Proof: aFA © F T]A is the 2-cell FA FTI A FT) UFA FUEFA FUFA • * FUFUFA »- FUFA £ FUFA ££FA £ FA FUFA £ FA FA while bFA ° FT|A is the 2-cell 135 FUFA FT] UFA 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 pA such that FT] A FA FT] A FUFA sA £ FA 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. Proposition 7 Given a para-soft adjunction (F ,U ,T| ,£ ,r,s) for which the coequalizer hypothesis holds, there 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 Lemma 8 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 uex UX • »• UFUX * UX T|UX UFUX' T|T)UX TjUFUX TIUEX T)UX UFT]UX UFUFUX-uFuex UFUX UEFUX U££X uex UFUX uex •* ux which is mX. Hence Uex o T|UX = cpX:UX » UX.Letg:X > Y be a 1-cell in X. Then Ug ux T|UX UFUX uex ux UY T]Ug T]UY ClFUg UFUY ueg ueY UY- • UY Og VY A A 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 1 OF- VF UF . Hence we have immediately that T) = T). The horizontal counit £ :FU > 1 is given by the composition A. A. F* £ FU The following proposition relates £ to £. FU' Proposition 9 A A. A. A. Let p: £ ° F cp » £ and q: £ > E ° F cp be the modifications given by the following diagrams. F ^ U . F0£ P : FUFU Then p and q are mutually inverse modifications. 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 l t 2 = tu °\2T\ =t(p °Vn.)= t 2. The relation p • Tit = p • tr\ gives immediately that (iii) 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 ©Tit2 = pt ©Tit2 =(p ©Tit)t= t2. The relation p©pt = p © tp gives immediately that (iii) 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 <k) : tk > t is defined recursively by: M ( 0 ) = n . ] > t, p(l> = 1 ;t » t, U ( 2 ) _ u . t 2 , t > p(k) = p « pk-lt ;t 2 > t fork=3,4, , or equivalently, if $: (A,+ ,0) > A( B ,B) is the monoidal functor corresponding to (B ,t ,TI ,p), then p(k) _ $(TJ(k) ).LetkTi:0 > k be the morphism of given by 154 k.T\ = T\ + + T\ :0 * k k summands and write T l k = T \ o oT\:1 > t k V J k factors sothat$(kTJ) = T\ k. ( 0T[ is the unique morphism 0 > 0 and T\° =1:1 » 1.) Lemma 12 For any monad ( B ,t ,r\ ,U ) in a 2-category A, we have the relations (0 t h T\ k 8 n h = n h + k . (ii) y(h+l) o t h u (k+l) = M(h+k+l)t (iii) p(h+l) .fn. 1 1 = t ; h,k>0. Furthermore, if ( B ,t ,TI,U ) /s an idempotent monad, we have (iv) t h T i k = n k t h , (v) thu<k> = u<k>th, (vi) t n k •u<k + 1> = t k + 1 ; 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)(n+TJ(k+l))h^ _ 7J(h+k+l)> (iii) ' 7 ( h + 1 ) ( l + h n ) = 1 ; h,k>0. The left and right hand sides of (i)' are different representations of the unique morphism 0 > h+k, the two sides of (ii)' are different representations of the unique morphism h+k+1 > 1 and the two sides of (iii)' are different representations of the unique morphism 1 > 1. (iv) is clear and for (v) it suffices to show that tu < k ) = u * k > 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 2 from the proof of proposition 11. 155 Assume that the formula holds for k. Then, since T i k + 1 = tT\k © T\ and M ( k + 2 > = u © tu ( k + 1 ) , we have t T l k+l o p ( k + 2 ) = K ^ k e T l ) o p « t M < k + 1 > = t 2 T\ k ©tTi • M • t u ( k + 1 ) , = t 2 Tl k • T\t • (J o t p ( k + D = t 2Ti k o t p ( k + D = t(tT\k « t M < k + 1 > ) = t k + 2. • Lemma 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 ) . t h + k » t 2 ; h , k > l . Proof: First note that MM = tu <3>, since MU = Mt • t 2 M = tM • t 2 M = t(M ° tM) = tu ( 3 >. N o w assume that the formula holds for some h , k > l . T h e n p ( h + l ) M ( k ) = ( u otu<h>)u<k> = ( U o t p ( h ) ) t o t h + l p ( k ) = Mt o t M < h > t o t h + l p ( k ) = Mt «t(M ( h > t « t h U ( k ) ) - Mt o t ( M < h > M ( k > ) = Mt « t 2 M ( h + k _ 1 ) = t M ( h + k ) , that is , t p(h) u(k+l) _ M ( h ) ( u l u W t ) - KM oMOt)t)o n(h)tk+l = tu »tM< k H • p(h)tk+l = tM o(tp(*> o u(h>tk)t = tM » M ( k ) M ( h ) t = tM • p ( h + k - D t 2 = Mt op (h+k-1) |2 = p(h+k) t = tM<h+k>. 157 Lemma 14 For an idempotent monad (B ,t ,n ,M) in a 2-category A, we have the relation ^(h+D^k _ nkM(h+l) : th+l • t k + 1 ; h , k > l . r tkM (h-k+i) if h > k > . T \ K _ H if h<k ; h,k>0. Proof: If h=0 or k=0, the relation holds trivially. For h=l and k=l, we have TIM =r\\ • M = t 2 and MTI «= tT\ • M = t2-For h,k>l,wehave p(h+l)^k = ( y .o u (h) Q ^ k - l = (tn °M • M ( h )t)n k _ 1 = (Mn •M(h)Onk~1 = M ( h )tn k - 1= tM ( h )n k _ 1. that is, 1 t h + 1 B »• B • B t k t t k - l t jk-1 t Using this result repeatedly, we obtain the required formula for p < h + 1 > Ti k . A similar calculation gives the same formula for T\kp (h+i) • 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 > n+k is identified with n+kT\ and every morphism n+k > n+1 is identified with n+p * k ) . Then, denoting the equivalence class containing a morphism £ by [ f ] , we have [n+kT\]= [kT\ +n] and [n+p * k ) ]=[p"(k>+n]. The operations of "+" and composition in A induce well-defined operations of "+" and composition in , so that ( A ,+,0) becomes a strict monoidal category. We 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 . (i) (h+kT\)h.T[ = (h+k)T[ (ii) TJ(h+l)(h+TJ(k+l)) = TJ(h+k+!) (iii) p" ( h + 1 ) ( l+kT\) «= 1 (iv) h+kri = kT\+n (v) h+p"<k> = 7 ( k ) + h (vi) ( l + k T \ ) T J ( k + 1 ) = k+1 159 (vi i) hTi+kTi = (h+k) T[ (v i i i ) TT<h> +U<k) = l+7J(h+k-l) (ix) ] I ( h + 1 ) + k T i «= kT\+M" ( h + 1 ) = [ h + 7 j ( h _ k + 1 ) if h>k, L (k-h)n if h<k. Proof: These relations clearly hold because there can be at most one morphism between any two objects o f A. • Note that ( i ) , ( i i ) and ( i i i ) actually hold in A . Composit ion in is determined by the relations ( i ) , ( i i ) , ( i i i ) and (v i ) , or, more precisely, by the obvious "translations" o f these relations obtained by adding an n to each factor which occurs. For example, (v i ) implies that (n+l+kn)(n+Tr ( k + 1 )) = n+k+1. Similar ly, the operation " + " is determined by the other relations. Observe that al l morphisms o f A except for k "n.: 0 > k, k>0 are isomorphisms. Hence al l the objects n>l o f A are isomorphic to each other, which means that the skeleton o f A is the category 2 w i th two objects 0 , 1 and wi th a single non-identity morphism 0 • 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) > A(B,B) such that $ ( 1 ) = t, $("ri) = -n, and $ (TT) = u. ErQQf: In order that $ becomes a monoidal functor we must set # (n) = tn,<Kn+kTi) = t nT\ k and <Kn+u<k>) = t n u ( k ) for n, k>0. Wi th this definit ion, all the relations of lemma 15 are preserved under Since these relations determine the structure o f (A,+,0) as a monoidal category, i t fo l lows that $ is indeed a 160 monoidal functor. For example, if p>q>r>0, the unique morphism | :q » r is |=r-l+p <<J r + 1> and the unique morphism 5 : r > p is 5 =r+ (p-r) T[. <*-r 5 5 0 5 is the unique morphism q > p , that is, 5 ° f =q+ (p-q) T\, hence $( S 0 T) = t^riP-q. Now $(?) = t r n p _ r and$(f) = tr-1p(q- r + 1>,so 4>( 5") • $(T) = trTiP-r o tr-lM(q-r+l) tr( ts-r-nP-s • r i q - r ) 0 t r _ 1p (q-r+D tq-nP-^ • t r r i < 3 - r • t r - 1p (q-r+D-t^TiP -^ • f r - 1 ( t T r 5 ~ r • 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 » q is ?=q-l+p (p-q+D and the unique morphism "5 : s » r is T=s+(r-s)r\- T+T:P+S » q+r isq+r-l+U<P+ s _ cJ-:r+1),So4>(T+T) = t c J + r _ 1p (P+s-q-r+l) _ On the other hand $("!)0 $(T) = t q _ 1 M (p-q+D o t s r i r - s jq+s-lp(p-q+l) ^ r-s t q+s-l tr-s u (p-q-r+s+1) s i n c e p _ q > r _ 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 -Alg( A) •* A-Alg( A) is induced by the quotient functor Q: A > 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 „ p A® B i ® B- B If (h ,<x): (B ,p) » (B' ,p') is a morphism of idempotent monads, then its image in A -Alg( A) is (h,oc(Q® 1 )): (B,p(Q® 1)) » ( B' ,p'(Q® 1 )), as given by the following diagram. Q® 1 p A® B 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 0 :A > A-Alg( A) be the 2-functor defined by F 0A= (B ,p 0) where p 0 : A ® A >A is the structure map for the trivial idempotent monad structure on A . F 0 is defined on 1-cells and 2-cells in the obvious way. Let U : A - Alg( A) > A be the evident forgetful 2-functor. Then we have a para-so ft adjunction (F0,U,T|o,Eo,ro,So) where T| 0 = 1 ands0 = id. 162 For an idempotent monad (B ,p), E 0( B,p) = (t,"p"):(B ,p0) > (B ,p). For a morphism of idempotent monads (h,"oc"): (B ,p) > (B',p'), E 0( h,"oc") is the 2-cell between morphisms of monads given by the 2-cell t = pad) B • B cx B' V = p'o-(l) B' in A. For an idempotent monad ( B ,p) = (B ,t,ri,M), r 0(B ,p) is 1 The "multiplication" for the natural monad structure on (B ,p) = (B ,t ,T\,p) is given by the 2-cell TVjlKB.p) UE0(B,p) U(B,p) • UF0U(B,p) • U(B,p) Tl0U(B,p) UF0U(B,p) T|0T|0U(B,p) = id T|0UF0U(B,p) T|0UE0(B,p) = id S TVjU(B.p) UF0UF0U(B,p) UF0UE0(B,p) UE0F0U(B,p) ue 0e 0(B,p) UF0U(B,p) UE0(B,p) UFQU(B,p) UE0(B,P) 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 0 ,U,T] 0 ,E 0 , r 0 , s 0 ) . Then we have 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 t 0 h v e whose value at an idempotent monad is the canonical adjunction f B t ' B n u € . Let Q 0 denote the composite para-natural transformation U£ 0 ° T)0U: U > U. Then there is a whose value at the idempotent monad (B ,p) is the universal t-algebra 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 0 ( B ,p) is the 2-cell in A -Alg( A ) given by t, u ) where p 0 is the structure map for the trivial idempotent monad structure in each case. On the other hand, b 0( B ,p) is 165 (B,p0) ( 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,p0),(B,p)). Now Ua0(B ,p) and Ub0( B ,p) are the 2-cells t 2 u 15 which have a coequalizer in A( B ,B) given by the split fork Ut t2u t u associated with the t-algebra (u ,5) and split by t 2 u -TltU t u t U TlU Proposition 17 ut ( t . V ) t u ( t , V ) u t5 is a split fork in A-Alg( A)( ( B ,p0),(B ,p)), split by ( t . V ) t u T(lU ( t , V ) u Proof: TlU (u,"5") ( u , V ) Because (u,5) is a t-algebra, it is immediate that (u,"5"): ( B ,p0) > (B ,p) is a 2-cell in A -Alg( A). Then ?: (t ,"u")u > (u ,"5") is a 2-cell between morphisms of idempotent monads since u t B > B * 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 F0h*:4-Alg(A)((B,p0),(B,p)) * &-Alg(A)((A,p0),(B,p)), that is, ( t .V)tuh (t ,V)uh * ( u , V ) h t?h 168 is a coequalizer diagram; indeed it is a split fork, which is split by rituh Tilth ( t , V ) t u h « - ( t , V ) u h « ( u , V ) h . • Since the preceding results show that the soft adjunction ( F 0 ,U ,T)0 ,£ 0 ,r 0 ,s0) satisfies the coequalizer hypothesis, it follows that there is a lifted soft adjunction (F0,0, T], £ ,r,s). As one would perhaps expect, we shall see that this lifted soft adjunction is precisely the evident strict adjunction (F 0, U, T), £) with T) = 1. 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 0A is constructed from the 2-cell T|0UF0A U£ 0F 0A which is the identity 2-cell on 1 ^ : A » A. The horizontal counit £ : Fo0 > 1. For an idempotent monad (B.p), £ :Fo0(B ,p) »(B,p) is (u,"5"):(B ,p0) » (B,p). A. * According to the general construction of a lifted soft adjunction, there is a modification n 0 : £ 0 ° F 0 V > £ whose value at an idempotent monad (B ,p), F0v(B,p) e0(B,p) Fo0(B,p) ; • F0U(B,p) > (B,p) | n 0(B, P) E(B,p) is the 2-cell (B,p0) (B,p0). ( t , V ) (B,p) (u,V) Let (h ,oc): (B ,p) > (B' ,p') be a morphism of idempotent monads. Then ( t , V ) e 0(B, P) F0U(B,p) • (B,p) F0U(h,a) E 0(h,a) ^ (h,oc) h is oc (l) (B,p) F0U(B',p')-(h,oc) e0(B',P') (B',p') (B;P') 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 E0(h,oc)°F0v(B,p) n0(B',p') °Fo0(h,cx) E(B',p')oF0D(h,cx) E(h,oc) (h,rx)oE0(B,p)oF0v(B>p) (h,a)on0(B,p) (h,oc)°E(B,p) Using the evident splitting we see that £ ( h ,oc) is (B,pQ)-(rToO ( u , V ) (B',P0) id (B',p0) ( t ' .V ") ( t , V ) cx (i) (B,p) ( h , a ) (B'.p') id. Hence £ : Fo0 > 1 is strictly natural. 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 V(B,p) U(B,p) U(B,p) T|0U(B,p) T)0U(B,p) r0(B,p) UF0U(B,p) UF0U(B,p) UF0V(B,p) u U£ 0(B,p) 1 Un0(B,p) U(B.p) U£(B,p) 171 This 2-cell is 1 Hence r\ B ,p) = id. The vertical counit 8:£FO°FoT|0 * 1. The vertical counit sA : E F0A ° F0 T| OA » A, evaluated at an object A of A, is obtained from a certain coequalizer diagram involving two 2-cells whose vertical composition with s 0 A coincide. Then sA fits into the commutative triangle 172 Now n0FQA = id, since the universal 1 ^ -algebra associated with the trivial idempotent monad F0A = (A,p 0) is 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 0,U,T) ,£) by attaching via the para-natural adjunction (dp, v ,h ,e): U > 0. The preceding discussion shows that the lifting construction retrieves the original strict adjunction (F0,0, T), £). 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 P 0(B ,P) F0f)U(B,p) F0U£0(B,p) F0U(B,p) * F0OF0U(B,p) * F0U(B,p) sU(B,p) £F0U(B,p) E(B,p) F0U(B,p)-£ 0(B,P) (B,p) It follows that (B,p0) (B,p0) id (u,"5") (B.p.) — 0 ( t . V ) ( t , V ) (B,p) (B,p0) | id (B,p) ( t , V ) q0(B,p) F0U(B,p) FoTloUCB.p) F0UF0U(B,p)' id F0f|U(B,p) F0ue0(B,P) F0U(B,p) F 0UF0V(B,p) id F0v(B,p) \ £ 0 ( B , p ) n0(B,p)J Fo0FOU(B,P)- F0U(B,p) (B,p) F0U£0(B,p) " £(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 commutative monad (B,t,Ti,p,X) in a 2-category A consists of an object B of A, a 1-cell t : B » B and 2-cells T\ : 1 > t, p : t 2 > t and X : t 2 » t 2 such that the following relations (illustrated by the corresponding commutative diagrams) hold. (CM1) p • Va = p • Tit = id tTl lit (CM2) (CM3) X 2 = x o x = id (CM4) tX«Xt®tX = X t « t X « X t 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 * t and u : t 2 > t as follows: T\5:5-X H —» G x 5 -» (e,x) where e is the unit element of G, p S : G x S x S-(g,g',x) i— — > G x S -» (gg'.x). It is well known that this defines a monad ( t ,Ti ,p) on Set [CWM]. Now define a natural isomorphism X : t 2 > t 2 by: XS:G x S x S (g.g'.x) i — -* G x S x s -» (g'.g.x). Then (Set ,t ,Ti,p ,X) is a commutative monad. Let Pl denote the category whose objects are the finite ordinals and with morphisms given by all 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 » m' and 5 :n > n', |+5 : m+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 > D which is a monoidal functor ( A , + , 0) > (D,+, 0). Along with the morphisms T\ :0 > 1, p :2 » 1 which generate A , we single out for special attention the isomorphism X :2 >2 given by X(0) = 1 and X (i) =0 . 178 We can represent morphisms of fl by means of "arrow diagrams" just as we did for A. Thus X :2 > 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) x2 = I o 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) 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= T A o f P where f A : m > n is a morphism of A and fp : m > m is a permutation with the additional property that if i<j and = T ( j ) , then fp(i) < fp (j), that is, fp does not 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 A the monotonic part of T; we call the factorization of the proposition the canonical factorization of the morphism f. Pioof: First we describe a method of constructing the arrow diagrams for £ A and f p. Take each point i of n in turn. If the inverse image of 0, ( f ) - 1 (0), contains m0 points, introduce m0 points into the domain of FA and draw arrows from these points so that these arrows all come together at 0. In general, if ( f~)_1 (i) contains rc^ points, introduce m± points into the domain of £ A above any points already there and draw arrows from each of these points to come together at i . Having constructed £A in this way, we obtain f p by connecting the points of ( f ) _ 1 (i) with those of ( ? A ) b y "parallel" arrows. Thus for 180 we obtain the factorization For a formal description of | A and |p, let i : 1 > n denote the injection given by i (0) = i and let : m± • m denote the composition of the unique order preserving bijection > ( | ) - 1 ( i ) with the inclusion ( J ) - 1 (i) > m. For each i we have a unique morphism u <mi) : m.^ > 1 and the diagram r m > n A. k 1 m± > 1 TT { mi ) commutes, |^ : m » n is then defined to be the sum N | ^ = Tj<mo> + Tr<ml> + + "jl'ron-l* : rtiQ + m x + . . . + rtv,-! > n. |p : m > m can now be defined as follows. Consider the codomain of |p to be the ordinal sum m0 + +. . . + where m.^ is the number of elements in (T) - 1 (i) for each i . For each i let the restriction of |p to ( T ) " 1 (i) .that is, Tp | ( | ) - 1 ( i ) :(|") - 1(i) > m0 + +. . . + 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 ^ ' ^ i k + l > k+1 isgivenby X(l.fc)(i, = k if i=0, k-1 ifl<i<k. 182 In particular X * 1 ' 1 * = X. Therelation X ^ ' 1 * = ( X + h - 1 ) ( l + X + h - 2 ) ( h - l + X ) follows immediately from the diagram Similarly, X ^ 1 ' * * = ( k - l + X ) ( k - 2+X+ l ) ( X + k - 1 ) . Forexample, X * 2 ' 1 * = ( X + l ) ( 1 + X ) and X < x ' 2 > = ( 1 + X ) ( X + l ) so the relations (fTTjand (f|8) can be written in the form: ( D 7 ) * (7+D X * 1 - 2 ) = I d + j T ) , (f ]8)* (l+p) X ( 2 - 1 > = X (p+l ) . We have the recursion formulas: X < h + i , i > = ( X + h ) d + X ^ ' 1 ) ) , Xd,k+1) _ ( k + X ) ( X ( l , k ) + 1 ) ; which could be taken to be the formal definitions of X < h' 1 > and X <1 •k > in terms of X. We adopt the 183 convention that X < 1 ' ° ) = X * 0 ' 1 * = l . By the well-known result that any permutation can be written as a 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 <h' 1 > is represented by the diagram h i • : 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 ( J c' 1 )+m, where k>l, an elementary permutation. It is a special type of cycle. 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 • n where n>2, there are unique elementary permutations o"p, <Sp-i, o^, such fnaf T- Vp ° O p - l ° ° and ^/"(Fi) <#("rl i + 1) for i=l, . . . , p - l . 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 > n has such a canonical factorization. Given a permutation g: n+1 » 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 * n can be written in canonical form F = F Q o 7f q_ x o o F L Then g'+l: n+1 • 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 ° ( Oq-i +D ° ° ( F x +1) . 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 Q +1) o (F Q_! +1) o . . . . . .o (F X +1) . 186 n n-1 **************** * \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ . \ \ . \ \ \ . \ \ \ * * * * * * * * * * * * * * * * • \ \ \ \ \ \ \ \ \ \ \ \ \ \ V * * * * * * * * * * * * * * • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' •* ************** ' \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** **************** **************** ******* JE** ******* •\\\\\\>\.\.\\\\\' **************** • X S \ \ \ \ \ \ \ \ \ \ \ \ ' **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ " **************** • \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** ' \ \ \ \ \ \ \ \ \ \ \ \ \ \ ' **************** '\\\\\\\\\\\\\\.' **************** • \ \ \ \ S \ \ \ \ \ \ \ \ \ ' **************** **************** j + 5r<n-j,l> Since j+X ( N _ 3 » i) is uniquely determined as the composition g ° ( g'+l) _ 1, we have the canonical factorization in the second case. • Examples 1. L e t j M » 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 ( 3 ' X ) (X~(2' ( X+2) . °1 °2 °"3 2. X ^ ' ^ r k + l * k+l has the canonical factorization = (k-l+X) (k-2+X+l) (X+k-1) which is the formula given previously. 187 k k-1 We can picture an elementary permutation 0" = h+X <k' 1 > +m by a diagram of the form h+k+m. h+k ********** \ \ \ \ s \ \ \ \ \ \ *********** \ \ \ \ N \ \ \ \ \ \ * * * *!•*. ******* - * > - W > \ \ \ \ * * *\* * * * * * * * \ \ \ A \ \ \ \ \ \ \ * * * * * * * * * * , * * * * * * * * * * , \ \ \ \ \ \ \ \ \ \ \ * * * * * * * * * * * in which the shaded region represents X <k' x* and the unshaded region corresponds to "parallel arrows". Again 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 \= o"p ° crp_i ° ° o~i of a general permutation | :n > n , where a i = n i + X ^ i ' 1 * + m± andhi+kj^ +nii = n fori = 1 ,2 , . . . ,p , can then be pictured as follows . 188 h j+k j+m ^ h l + k l x x x x x x x x v X X \ X X X X 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 " f I f ^ i / i ^ ' 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 • 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 h i + k i + m i h 2+k 2 h p+k p+m p 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 (03) and(fl4). Lemma 3 The relations (03) and (04) imply that the following relations hold for h > 0 and k > l : (03) * ( X + h ) X<h+l,l> =1+ X < h , l ) ( (04) * ( h + X + k ) \(h+k+l,l) = X < h + k + 1 ' 1 > ( h - l + X + k + 1 ) . PjQQf: ( 0 3 ) * ( X + h ) X ( h + i , D = ( X + h ) ( X + h ) (1+ X ( h ' x > ) by the recursion formula = 1+ X * 1 1 ' 1 * using (03). The proof can also be given in the following diagrammatic form. 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~1:n > n where rj-^ and cr2 are elementary permutations and 0{( rj1) > !H( cr2) . Then, using the relations (fl3) and (f|4), we can obtain one of the following: either two elementary permutations ' and F 2 ' with Fj 1) < M( F 2 ') = M( F x ) and pr a single elementary permutation F w/Yh F) = J^Fj) and |~= F = F 2 ° F x . Proof: Lei = hj_+X<ki'1>+mifori=l,2, where k^l.Then we have h^k^rr^ = h2+k2+m2 = n-1 and h2+k2Si1+k1. Case (i): h2+k2<h1. In this case cr2 only moves points which are unaffected by oyso and 0"2 can simply be interchanged to obtain the result, that is, set a x ' = cr2 and a 2 ' = cy At a purely algebraic level, only the monoidal category properties of + and composition are involved. Case(ii): h2<h1<h2+k2. By successive applications of the formula (04)* followed by one appbcation of the formula (03)* we obtain ? 2 o ?! = (h2+X<k2'1)+m2)(h1+Y(kl'1>+m1) = (hi+l+ X^l" 1-1) +mi) (h2+ X ^ " 1 ' x> +m2) h 2 + k 2 - l Case (iii): h1<h2-By successive applications of the formula (fl4)* we obtain F 2 o 7j = (h2+X~<k2'1>+ni2)(h1+X<kl'1>+m1) = (hx+ D 4m{) (h2-l+ X<k2' 1> +m2+l) Case (iv): h x = h2+k2. cr2 o o-j. = ( h ^ X ^ l ^ l " ^ ' 1 ) ^ ) = F. h l + k l h2+k2+m2 h2+k2 By repeated applications of lemma 4 we obtain: Proposition 5 Let T~ F q ° ^q-i ° ° 0"! where (j ± is an elementary permutation for i = l , . . . ,q. Then fhere are elementary permutations F j ' for j=l, . . . , r, where r < q, such fhaf 194 5 = 0"R' ° VT_i o ° O"!1 and #(Fj') < #(F j + 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 means using relations (f]3) and ( f l 4 ) . • Proposition 6 (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 the composite permutation 5 o g can be obtained in canonical form by purely formal algebraic means 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 > n of H namely: 5 = 5A ° 5p where £p is the switching part of f and | A is the monotonic part of £ with each of |p and T A given in their respective canonical forms, that is, | ^ = 7J(m0) + TJOti!) + + T J ( m n - l ) , where m± is the number of elements in ( ( i ) or ( f ) _ 1 (i) for i = 1 , . . . n, and F P = F p o F p _ ! o o vlt where each cr j is an elementary permutation and 9<( 0" j) < M( F j + 1 ) for j = 1 , . . . , p -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> - MU+p) (m-2+7). p <m> ;m » 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) (p+m-2) . The associativity relation: (02) Fd+TT) = P " ( P + D , can be represented pictorially thus: 196 More generally, the equality of the two expressions for p (m> given above can be established by repeated 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" ( m ) ) = ( F ^ + D l l 1 ' 1 1 " , (08) * )T(p"(m>+l) = (l+'p<m>)X"<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 clear from the 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(m)+i) = (7+1) (1+X) (X+l) (l+7(m)+D by(07), = (7+D (1+X) (7(m)+2) (X<1'm)+1) using the inductive hypothesis, = (7+1) (7(m>+2) (m+X) (X^-^+l) = (7<m+1>+l)X(1'm+1> using the recursion formula for X <1'm + 1'. (ii) Diagrammatic proof. 200 We call a morphism V :h+k+m > h+l+m of the form V = h+p ( k ) +m , where k>0, an elementary A-morphism or an elementary monotonic morphism. As we have seen in chapter II, an arbitrary morphism of A , | ; m » n, can be written in the canonical form T = P~(K0> + " p ( k l > + + "p<kn-l> where k± is the number of elements in ( f ) - 1 (i) for each i , and so can be written as a composition > vn v n - l v l where each V.^ is an elementary A-morphism of the form = + p(ki.) + 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 CT ov" = V o crq o o F l t where v' is an elementary A-morphism and 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 ° ° ^ i ° ° F l t where the morphisms are elementary permutations, the morphisms V j are elementary A-morphisms and we may assume that the composition cr s° vs_i ° 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 ( k l ' 1> -i-m! bean elementary permutation and V = h2+ u < k 2 + 1 ) +m2 bean elementary A-morphism, where h1+k1+m1=h2+k2+m2=n; h x, t h 2, m2>0 and k l fk 2>l. Then we have the following expressions for v ° cr : n+1 > h2+m2 =1. (CM) If h1<h2 and h2+k2<h1+k1, v" °F= (h^\<kl-k2'1>+m1) (h2-l+7J"(kl+1)+m2+l) = 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.) (US) // h 2 S i 1 andh1+k1<h2+k2, \T°F= (h 2+F ( kl + 1 )+rri 2) = v! (In this case all the switching of cr is "unnecessary".) (PCM1) If h1<h2<h1+k1<h2+k2, \T orJ= (h 2+F ( h2 + k2" hl" kl>+m 2) (h1+X<hl"h2'1>+h2+m2) <h 2-l+F ( hl + kl _ h2 + 1>+ 1^+1) = v"x °F ° \T2, where V x , v 2 are elementary A-morphisms and cr' is an elementary permutation such that v1° <s' has no unnecessary switching. (In this case we have "partial commutativity".) (PCM2) /fh2<h1<h2+k2<h1+k1, v" oF= (h2+M+m2-l) (h 2+X ( hl + kl~ h2 - k2 ' 1 )+m 1 ) (h2+F(k2)+m2+l). (This is another case of "partial commutativity".) Furthermore, these relations can be obtained by purely formal algebraic means using the relations (fl2), (fl6) and (08). Proof: Case (CM): hyhj and h2+k.2Shx+ki • 2 0 2 h^+k 1+1^1 h l + k l j h2+k2 h2+k2+m2 : N 2 + M 2 0 0 203 using relation (fl8), 205 206 Hence V ° a = (h^ X <ki_ K2' D +111!) (h2-l+ p <ki+l> +m2+l) 208 209 using relation (Pl6). Hence V* ° F = ( h 2 + " u ( k l + 1 ) + m 2 ) = V. Case (PCM1): h 1 < h 2 < h 1 + k 1 < h 2 + k 2 . 212 Hence V ° a = (h2+ M < h 2 + k 2 _ h l - k l ) ( h l + \ (hx-h2,1) +h 2 + m 2) (h2-l+ y ( h l + k l _ h 2 + 1 > +m-,+l). Case(PCM2): h 2 <hi<h 2 + k2 < h i + k i -216 Hence V ° cr = (h2+ u+m2-l) (h2+ X (h 1+k 1-h 2-k 2, l) + r r i l) (h2+ (j <K2> +m2+l). The relations of lemma 8 can be given in abbreviated diagrammatic form as follows. (CM) • l + m l £2+K2 — (k^ T S ^ j h 2+k 2+m 2 h2+n^ h 2+k 2-l h 2 - l ->2 x ^ JJ 2' > w h2+m2 h l + k l ~K2 (US) h1+k1+m1 h l + k l N. "2 2 £-<klrl) H2 + K2 + M2 h2+k2i h2+m2 (PCM1) 218 hj+kj+mj ^-(k^l) h2+m2 h2+k2 h 2+k 2-l ^-(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 be a permutation also given in the canonical form ? p = F Q O C T q . ! ° • ? r where is an elementary permutation for each i and JW(F L) < # " ( F I + 1 ) for i<q. Then there are indices ilr . .. , i k iv/tf? OSi-j^ i 2 < ij^q such that if Fp= % ° V i ° o T i i -tfjen f Ao |p is the canonical factorization of f"= f A ° £p tv/tf? monotonic part f^ and switching part |p (which now contains no unnecessary switching). Furthermore, this can be achieved by purely formal algebraic means using the relations (02), (06) and (08). Proof: The problem is to remove unnecessary switching from 5 p. Factor f A as f A = Tc where Ti injectiveand f c is surjective. Then f = f A ° 5p = ?i ° fc ° 5p- W e 0 2 0 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 = | A ° f p and S = SA° Sp where f p and f A are the switching and monotonic parts of f respectively, while Sp and 5A are the switching and monotonic parts of 5 respectively. Then T ° T = T A 0 T P ° I A 0 Fp • We first compute S p ° I A -f A has a (canonical) factorization F A = ^ P 0 V I 0 0 V i -where each v ± is an elementary A-morphism of the form v ± = h± + p ^ i * + m.^ and Sp has a canonical factorization Tp = F q ° Fq_! o o F l t where each CT j is an elementary permutation and M( cr j) < cr j + 1 ) for j = 1, . . . , q - 1. Then 5p° ?A = ° q 0 °q-i 0 0 a i 0 v p 0 v p - i 0 0 v x so we can use the relations ( f l 7 ) * and ( f l 8 ) * repeatedly to obtain Sp ° f A in the form 5p° F A = V 0 V J ' O ......° V o F s' o Fg^" o o Fj', where 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 o ^ - oF v" o F V - 1 - o o Fi", where the Vi"and a j " are elementary A-morphisms and permutations respectively. The A-morphism V u " o V y . ^ " o o can be put into canonical form v u v u - l v i using the relations (f~11) and (02), while the permutation a v " 0 0"v_1" ° o Fj_" can be put into canonical form 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 ( D 8 ) , so that finally we 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 monoidal functor $ : (fl,+, 0) -> A( B ,B) such that: $(l) = t: B > B, $( ri) = n • 1 » t. <KIT) = M : t >'t2 and $( X) = X : t 2 » t 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 ~%: m • n of A can be written in the form |"« 7<k0) + "p<kl> + + "p^n-l), where is the number of elements in (fD _ 1 (i) for each i and we have $(D = 5«= P ( k0> ° p < k l > o o p ( V l ) : F > t m, where p<ki> = f ( " p ( ki ) ) for each i . We needto defined on permutations sowe set $("X(k'1>) = X ( k ' 1 >: t k + 1 » t k + 1 , where X(k,l) is defined recursively by •X<l'i>=X, X(k+l,l) = X t k o t X ( k , l ) t which corresponds to the recursive formula for X ( k • 1 ' : X(k+l,l) = (Y + k ) ( 1 +x (k ,D >. X ^ ' 1 ' is the 2-cell 224 k copies Then for an elementary permutation <T= h+X <k' 1 > +m we must set $ ( a ) = t h X < k • 1 > t m and for an arbitrary permutation \ : n > n given in canonical form T = F q o F q_! o o F x where = h±+ X < ki' 1 > +111^ ^ for each i , we must set $ ( D - 4>(Fq)» c^Fq.! )o e ^CFj). By writing a general morphism of in the canonical form | = | A ° F, p , we see that $ is uniquely 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, = crq ° ° r j l t while T has the canonical factorization 5 = t r ° o t x , we have S~+T = ( n + T r ) o o ( r H ^ ) o (Fq+m) © © ( O ^ + m ) . Now crq+m) < #(n+ xx), so this is the canonical factorization of 5+5- Thus we have <KT+T) = $(n+ 5") e$(T+m) = tn4>(5~) • <KI~)tm = *(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. According to proposition 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 = ( I A ° 1 P ) + ( ? A ° T P ) = ( F A + ? A > ° ( T P + 5p), so we have $ ( | ~ + T) = $ ( I A + T A ) 0 $(Tp + Tp) = (*(|^)o $( 5" A ) )»($(Tp)° * ( T P ) ) = ($(f A ) ° $ ( F P ) ) ° ( $ ( ? A ) ) » ( $ ( T P ) ) = $(D°<K?) . • 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 » n where n>2 and 0<i<n-2 is called a primary 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 (k'1>+m as a composition of primary permutations. For a general morphism F,: m > n of D, we have the canonical factorization T= Ij ° lc ° TP 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 f a c t o r i z a t i o n 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 obtained from (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 the right of each factor which occurs. 227 (s+n)( T[+S-1) = (Tl+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) (s+"X)( T\+S+1) = (n+s+i)(s-i+X) (Pf|15) (S+1+M")(~X+S+1) = (X+sXs+i+p") (PD16) (s+"X)( p+s+l) = (ir+s+i)(s+i+X) (Pni7) Proposition 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 m^ ?3 ^ compositions of primary injections, primary 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 have a corresponding monoidal functor 4>: ( f l ,+, 0) > A( B ,B). Let p : P)®B > 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) > ( B' ,p') in fl-Alg( A) can also be regarded as a pair ( h,oc ( 1 ) ): (B ,t,Ti,p,X) • (B' ,t' ,T[' ,p' , V ) where cxd) = cxa(l):t'h • ht.thatis, t _ _ cr(l) _ p B f l ® B B id 1® h ex. B' n® B' cr(l) P' such that (h,a ( 1 ) ):(B,t,ri,p) » (B'.t'.iy.p') is a morphism of monads and t 2 We shall call either (h ,oc )or (h ,a <1>) a morphism of commutative monads, hoping that it will be clear from 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 , t , r i ,u ,\) is a commutative monad, then its image in A -Alg( A ) is the monad ( B ,p( J® 1 )) = (B ,t , T i , p ) . If ( h , o c ) : (B ,p) > (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 )) > ( B',p'( J® 1)), as given by the diagram J ® 1 ^ _ p A ® B D® B 1® h id A ® B" n® B1 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 ) > ( A , + ,0 ), which can be obtained by regarding A as a quotient category of fl. If Q: A » A is the quotient functor, we have the following commutative triangle of monoidal functors Q (A, + , o) (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 0 >k is kri = k+k+ +k ( k summands). The diagram k+kri kT\+k k > 2k < k is a coproduct diagram. For k>l, let p k: 2k > k denote the unique morphism of fl such that the diagram commutes. Thus p k is a "codiagonal" or "folding map". In particular, p j is just p : 2 > 1. Mk can be pictured by the diagram 2k-l k-1 It is easy to check that for k+s=m, p"m = (p'j.+ p's) (k+\(s'k>+s) Hence we have the recursion formulae Fk+i = (Hfc+u") (k+X^-kJ+l), Fk+l = <M + U"k) (1+ X^'^+k) . 231 The diagram Uk+k k+ Pk commutes, thus we see that (k,kri, pk) is a monoid in the monoidal category (Pl. +. 0). Let A be a 2-category which has lax limits, or at least Eilenberg-Moore objects, and suppose we are given a commutative monad ( B ,t ,\) in A. Let $ : ( Pl, + , 0) » A( B ,B) be the corresponding monoidal functor. Writing, as usual, $(f) - 5 for a morphism 5 of Pi, the image of (k,kri, pk) under$isa monad ( B .t* ,T[K ,p k) in A for each k^l, which we call the k-fold composite monad associated with the commutative monad (B ,t ,Ti,p ,X). We denote the Eilenberg-Moore object for this composite monad by B k and the corresponding universal cone by (u k ,5k). Since this universal cone is a tk-algebra, we have 232 We shall show that there are adjunctions fk,k+l Bk c ' B K + 1 nk,k+i U k ' k + 1 € k ( k + 1 such that the diagram of adjunctions k,k+l commutes. First we define f] Lemma 1 is a t k -algebra. EffiQf: The condition involving r i k + 1 is clear. 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 ( k + 1 : B k > &k+lt0 be the unique morphism 1-cell such that is a ik-algebra. Proof: The condition involving T \ k is clear and the condition involving is a consequence of the following relation in A( B ,B). 237 For 0<i<k, we define u ( i ) k ( k + 1 : B k + 1 > B k to be the unique 1-cell such that j(i> >k+l" k,k+l 5k , = B k+l L e t u k ( k + 1 = u < ° ) k r k + 1 : B k + 1 » B k and let t k f k + 1 = u k , k + 1 f k ( k + 1 : B k » Bk. Lemma 3 *k, k+l : Bk * B k is the 1-cell induced by the morphism of monads (t ,X< k ' 1 >):(B,t k 1 T l , c ,Mi t ) » (B,t k ,Ti J t .M k ) . Proof: (t, X * k' 1)) is clearly a morphism of monads and we have f k,k+l -*B k+l" k,k+l t k Now Tiuk :(uk,5k) (^tUk.tSk •X ( k ' 1 > U k ) is a morphism of tk-algebras, so we can define k+i : 1 » t k ( k+i10 be the unique 2-cell such that t k,k+l 240 Similarly, we have a unique 2-cell u k ( k + i : (t ) t (| c + 1) 2 > t k ( k + 1 such that 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\k( k + 1 as the unit of the adjunction that we are constructing between fjc^+i and k + 1 . 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 k ,5k). By taking compositions of 1-cells of the form u k > k + 1 : B k + 1 • B k we obtain various 1-cells B k + S > B k for s>l. To describe these 1-cells let a. = <a 0,a l f , a s_ 1> denote an increasing sequence of s elements ofm = k+s = {0, . . .. ,m-l}. For each such sequence let Ti ( m a ) : k • m denote the morphism of f l given by ^<m,A) = A0+^\+ a 1-a 0-l+Ti+ a 1-a 0-l+T[+. • • • • m-ag^-l. 241 Thus Ti ( n w a ) : k > m is the unique order preserving injection whose image does not contain the points of the sequence a. Let T\ ( n i j a ) : t k > t m be the corresponding 2-cell in A( B ,B). Lemma 5 is a i^-algebra. Proof: L e t u ( a ) k m : B m > B k denote the composite 1-cell B • In particular, taking the sequence < 0, i - 1 , i + l , k> in k+1 in which the only one element i with 0<i<k is omitted, we obtain a unique 1-cell u < i > 1 j c + 1 : B k + 1 > B k such that Proof: The second 2-cell is 243 The next result is immediate from the definitions. 244 Lemma 7 For 0<i<k-l, we have u B Jc,k+1 ,<i> l,k U ,<i+l> k+1 >k+l 1, k+1 By induction from lemmas 6 and 7 we obtain the following decomposition. Lemma 8 B k+1 , k+1 »k+l l,k+l • • 245 Lemma 9 • Using the result of lemma 9 we define X ^ ' 1 * : B k + 1 > B k + 1 to be the unique 2-cell such that 246 (k,l) k+1 k+1 k+1 k+1 k+1 X<k,l) J K + 1 Since the k-fold vertical composition [ X *k, ] k is the identity 2-cell on t k + 1 , it follows that the k-fold horizontal composition [ ^ (k, l) ]k j s m e identity 1-cell on B k + 1. Thus, in particular, we see that (k' 1 > is an isomorphism. Lemma 10 (k,l) ,<i> >k+l •* B l,k+l k+1 U ,<i+l> >k+l' — > B if i<k , .<0 > 5 k+1" l,k+l B if i = k Proof: (k,l) ,<i> l,k+l >k+l >k+l The lemma follows from the relation r l i + 1 t n k _ i _ 1 if i<k, . tT\k if i=k, which follows from the relation in D: X<k'x> (i7\+l+(k-i)Tl) = if i<k, if i=k. ((i+1) T\+l+(k - i - D n> . 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: The first 2-cell is 249 The result follows by lemma 7. Generalizations of lemma 11 can be obtained by using the following result. Lemma 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 2 be 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 k = id , we obtain the first triangle identity for the adjunction. 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 Proposition 15 The diagram of adjunctions Hence f k ( k + 1 f k - f k + 1 . Since u k T i k k + 1 = T\uk, we see that 1 This establishes the desired relation between the counits. By composing adjunctions of the form fk,k+l B * ( ' 1 B k + i ^ k + l Uk,k+1 € K > K + 1 we obtain adjunctions 261 Lettjcm =uk,mfk,m: &k > Bk. Then t k / k + 1 : B k > B k is the unique 1-cell induced by the morphism of monads (t, X <k-8>): (B ,t k , T i k , u k ) > (B ,t k , T \ k ,Mk). Lemma 16 For m>k>l, T\ k m: 1 > 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 k m : ( t k > m ) 2 —> t k f m be the unique 2-cell such that l k , m we obtain a monad structure ( B k , t k m , T i k m , p k / i n). Lemma 17 For m>k>l, € k t m : f k r m u 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 1fk ( m. Using the decomposition of lemma 7 we have ' Proposition 18 The Eilenberg-Moore object for the monad ( B k , t k ( m , T i k ( m , p k m ) can be identified with B and the associated universal i.^m-algebra is given by ( t k f m , 5 k f m ) . PjBQf: It suffices to show that B m has the appropriate universal property with respect to the monad ( B k . t k , m , Tlicm- Mk,m)- F ° r u i e 1-cell universal property let 265 be a t k f m-algebra. Now Let w: A > B m be the unique 1 -cell determined by the above tm-algebra. Then 266 w Hence w is unique. It is straightforward to check the 2-cell universal property. Proposition 19 The adjunction f k,m Jk,m :k,m is the canonical adjunction arising from the monad ( B k , t k m , T i k ( m , M k f m ) . Proof: The 1-cells f k ( m , u k T m and the 2-cells T\K? m ,ek ( m coincide with those arising by the canonical construction. This is immediate for u k ( m , T\k, m m & e k , m- ^ o r ^k, m w e have k,m Hence 5 k , m f k , m = M k, m - as required. 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 ,tk ,r\k ,pk)and (B' ,t'k ,r\'k ,p'k). Suppose (h ,cx): (B ,p) > (B' ,p') is a morphism of commutative monads. Then we have a morphism of monads (h,a<k>):(B,tk,Tik,Mk) » (B'.t'k.n^.M'k) where, as before, k copies Indeed, with the evident description for 2-cells, we have a 2-functor Ck: Pl-Alg( A ) ( k , k r i , p k ) is a monad in D, there is a unique monoidal functor J k : (A ,+, 0) --» Mon( A ) . Since -» ( ( " ] ,+ , 0) with Jk(l)=k, Jk(Ti)=kri and J k (p )= p k. Then C k is induced by J k in the following way. For a commutative monad (B ,p), C k(B ,p) = ( B ,p (J k® 1)); if (h,oc): (B ,p) morphism of commutative monads, C k( h ,cx) is the morphism of monads given by the diagram P -> (B'.p1) isa A ® B J k ® 1 n® B B 1® h id ® h a A ® B' J k ® l n® B' B' 270 Now suppose that A has Eilenberg-Moore objects. Then we can compose C k with the Eilenberg-Moore 2-functor V: Mon( A) > A to obtain a 2-functor 0k: fl-Alg( A) > A given on objects by 0k(B,p) = 0k(B ,t,riJu,X)= Bk. We have a para-natural adjunction (<p,y,h,e):V > V whose value at 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 P ] C )v k,h k,e k)= (cbCk,VCk,hCk,eCk):U » 0k where U : D-Alg( A) > 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 Bv For m > k > l , there is a para-natural adjunction (<P k / m,V k f m,h k ( m,e k ( m ) : 0k » 0 m whose value at a commutative monad (B ,p) = (B ,t ,r\,ii ,X) is the adjunction nk,r : k,m The para-natural transformation cP k / m is given on morphisms as folows. If (h ,cx): (B ,p) » (B' ,p') is a morphism of commutative monads, then cp k, m ( h ,a), that is, Ok(B,p) 0m(B,p) O k(h,oc) U (h,oc) m Uk(B',p') *k,m(B' ,P') * UjB'.p1) is the 2-cell given by 271 where the adjunction ^Ym u' k' m e'k,m is associated with the commutative monad (B',p')= (B' ,t' ."n.1 ,p' ,V). We have the following commutative 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 left hand commutative monad structure which has the fl-algebra structure map vp : D x n > D given by the monoidal addition, that is, "p( f ,5) = 5+5. Let "<J>: (H,+, 0) > Cat(D,ri) be the corresponding monoidal functor. We writev$( l ) = vt; then v$( k)= "t k, where v t k (m) = k+m. For a morphism f:m » kof fl we write V$(T)= ~ f t m >"tk; thus v?(n)= |+n:m+n > k+n. In this way we obtain a commutative monad (D/p) = <n , v t . v Ti . v u, v x) . 272 We also have a right hand commutative monad structure described as follows. Let (fl ,© ,0) denote the monoidal category obtained from (D,+,0) by "reversing the addition", that is, |© 5 = 5 + This operation is a functor p'rOD > f l where pv(|~,5~) = The diagrams commute, so we have a corresponding monoidal functor $ v : (("] ,© ,0) > Cat( D ,fl). 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 Zn :n » n be the self-inverse isomorphism which reverses the order of the elements of n, that is, 2 n (i) =n-i for 0<i<n-l. Then, for each morphism |: n > m of f l , let A(J) = 2 m ° T ° 2 n : n > m. Note that, because of their symmetry, the generating morphisms T i , p and X are all unaffected by A. We also have, for example, A (1+1J) = u+1 .In general, for two morphisms <• and 5 of D we have A(f+5)= £ + f,, which shows that A is a monoidal functor as claimed. Indeed A : (fl,+, 0) • (fl ,©, 0) is clearly an isomorphism of monoidal categories. Consider the composite monoidal functor (n.+,o) • (n .e .o) • cat(n.n). The corresponding fl-algebra structure map is o n — — • o n — — -n which gives a commutative monad (fl, vp(Ax1)). We write $ V A ( 1 ) = $ V ( 1 ) = t v ; then $ v ( 1 ) = ( t v ) k where ( t v ) k (n) =n+k. For a morphism |:m ^kofflwewrite $"A(T) = 5 " : ( t " ) m > ( t v ) k . Using this notation tiie commutative monad ( f l , p "(Ax 1)) is (fl , t v , r\", p v, X v ) . Then for each k>l we have the k-fold composite monad (fl, ( t v ) k , C n , v ) k , p k ). In order to avoid using parentheses we write ( t v ) k = t£and ( T \ v ) k = r^.Thus, for example, : 1 * *k*s m e natural transformation whose value at an object n of D is the morphism ( l t v ) k (n)=n+kT\:n » n+k. Let (n, 9) be a t^ -algebra, where n is an object of D and 0 : t k n > n is the algebra structure map. Such a t^ -algebra gives rise to a pair (n, <p) where <p: k > n is the composite morphism nrj+k e~ k • n+k *> n Conversely, suppose we are given a pair (n, <p) where *p:k > n is an arbitrary morphism of D. Then, since n+kr\ nT\+k n • n+k<« k is a coproduct diagram in D, we can define 0 : n+k » n to be the unique morphism such that the diagram n+kri commutes. Then the diagram n+k+k 0+k n+k n+U 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 > n is a morphism of D. With this identification a morphism of t^-algebras ?:(n, *p) »(m, \p) is a morphism |: n > m of D such that the diagram 274 k n — *• m i commutes. Rather than work with the complete category of t^-algebras, we make use of the full subcategory fl £ whose objects are pairs (n, .a) where a. = <a0, , ak_1> is a strictly increasing sequence of k elements 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 k is a morphism | :n » 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. = <a0, , ak_1> inn, letm+^ = a.+m denote the sequence <a0+m, , 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 k) 2 (n) ^ ^ ( n ) • t£(n) orn+pk:n+2k • n+k. Since the free tk-algebras are objects of the reduced category f l k, it is clear that we have an adjunction fk n _ i n k ^k uk *k obtained as a restriction of the canonical adjunction associated with the monad (D, t k , T i k , p k ). For an object n off!, f k(n) is the free tk-algebra just described. For a morphism % :n ^mofPl, f k ( | ) = |+k: (n+k,n+k.) > (m+k,m+k.). the diagram k n+k — »rn+k ?+k commutes, as required. u k : f l k » f l is the evident "forgetful" functor and we have u k f k = t k . The counit € k : f k u k > 1 is the natural transformation whose value at an object (n, a) of D k is the associated algebra structure map, that is, the unique morphism € k(n, a) : (n+k, n+JO > (n,a) suchthatthe diagram n commutes. The right hand commutative triangle shows that € k (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 drawing parallel arrows. The triangle identities for the adjunction (f £, u £, r\£, € £) are given by the commutative triangles The functor v p: f l x 0 > fl given by monoidal addition induces a functor fl * fl £ > fl £ which we also denote by vp. This induced functor is given on objects by "p (m, (n,a)) = (m+n,m+&), which we may also write as m+ (n,a.). Given two morphisms £ :m > m'of fl and 5: (n,a) » (n 1 ,a') of 277 f l k , vp (5,5) is the morphism of Dk given by f+ £ : m+ (n,.a) » m' + (n' ,a.'). The diagrams n x o n : — — — • n - n ; p X 1 n*n; •n; clearly commute. Hence (("")£ , vp) is a commutative monad which we may also denote by ( , v t , v r i , " u , v X ) with the obvious definitions for vt, vTi, vu andvX. Proposition 20 The adjunctions n in Cat enrich to adjunctions f; /nfl-AlgCCat). The diagrams o n -ix t; r>n; (n,vp) n •a (n^.-p) n*n; 1* U . O H ' •n: n commute. For example, the left hand diagram commutes because fkvp<r.5~> = fk(T+?')= r+?+k ="p(T.fk(T)) = vp(i*fk)<r.5). Hence f £ and u k are strict morphisms of Pl-algebras. We have 1 278 o n - i x f i o n ; . Ix U , o n - n o n - n- •n since "p( 1 xT\k) (m,n) ="p (m, (n) ) between morphisms of Oalgebras. Also = m+n+kTi = t\k(m+n) = "p (m, n). Thus T \ k is a 2-cell » o n ; o n ; • n v 1 ' k — n. since for a pair of objects m of n and (n,aj off]^ wehavevp( 1 x e k) (m, (n,&)) = m+€k(n,a.) while € k vp(m(n,a)) = € k (m+n,m+a). These are just different representations of the same morphism of f]^ . • 279 We shall show that for m>k2:l there are adjunctions K k,m n k — i n ; which are the restrictions to the reduced categories of the adjunctions f k , m B k * B l k , m c k , m which we considered previously, for the case (B ,p)= ( f l , p " ( A x 1)), that is, ( B , t , T i , p , X ) = ( n , t v . n v . u v . x v ) . Form>k£l,let f k ( i n : D k * Pl mbe the functor given on objects by f k ( m ( n , a ) = (n+s, <a0, .. . ., a k_ l fn,n+l, . . .. ,n+s-l>) where k+s=m. Thus s new base points are added "on the top of (n,a). Given a morphism g: (n,a) » (n',a') o f D k , f k r m ( £) is the morphism of given by g+s : (n+s, <a0, . . , a ^ ^ n , , . . ,n+s-l>) > (n ' + s , <a ' 0, . . .a'^^.n', . . ,n '+s-l>). Let u k f m : 0 ^ » f l k be the functor which "forgets" the last s base points. 280 (ii) EEQQf: (i) The morphism of D obtained by evaluating the natural transformation given by the second diagram at anobject (n,a.) of D k can Depictured by the following "arrow diagram". Note that X" ( k ' s ) (n,aj = X"<k's>(n) = n+X< k'^sinceA(X< k' s>) = X<s-k>. 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£f m and m are the restrictions to the reduced categories of the 1-cells ^k,m - > B m andu^n, : B m > B^ respectively, which we described previously, for the case (B,t ,Ti .M,X)= ( n , t v , r l v . M v , X v ) . For 0<i<k-l let u { ( J c < i > : P l k * f l v be the functor which "forgets" all the base points except for the base pointa^.^. This functor is given on objects by v/1* (n,aj = ( n j a ^ . j ) andhasthe 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 v u £ ; k = u k. The natural transformation given by the right hand diagram evaluated at object (n, a.) of D 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 £ k < : L > is the restriction to the reduced categories of the 1-cell u < i >l,k : r 3 j c > B,which we defined previously, for the case (B.t .Tl.M ,\)= ( f l , t~ Ti", p", X " ) . L e t - i n " uk,mfk,m = » n ^ - T h e n t ^ is given on objects by t k ,m(n,a.) - (n+s,a.) and is given in the obvious way on morphisms. Let T\£ f m : 1 > ^ k,m be the natural transformation whose valueatanobject (n,a) ofnkisri^m(n,a) = n+sri: (n,a.) > (n+s,a.). For an object (n,aj of Pl^ we have fk,muk,m(n'a) = (n+s, <a0, . . ., a ^ ^ n + l , .. . ,n+s-l>) Let€ k > m:^k,muk,m * 1 be the natural transformation whose value at an object (n,a) of flm isthe unique morphism of Pl m such that the diagram commutes. €^ m(n,a.) can be pictured as follows. 285 Lemma 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 aJc-l a 0 ak a k - l ^ 0 0 This is clearly the same as the morphism given by evaluating the first natural 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 m ^ €k, m: fk, muk, m * 1 respectively, which we defined previously, for the case (B,t,Ti,M,X)= ( n , t v , V . P v . X v ) . It follows from the preceding considerations that for m>k£l we have adjunctions k,m 1 1 m H k U k,m •k,m which are obtained as the restrictions to the reduced categories of the adjunctions f k,m &k "* B m Jk,m :k,m for the case (B .t.Ti.u ,X) = (f l , t v , T\v , u X as suggested earlier. If one was simply interested in showing 1 0 3 1 ( *k, m' uk, m' ^ k, m' ek, ^ a n 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 f v , 4 f k , m ' n - k , n i ( n ' a ) f v v fk,m(n'.a) • fk,m uk,m fk,m( n^) €k,mfk,m <n'3) fk,m( n'3> commutes because it is n+sTi+s (n+s,< a Q , . . . a ^ , n , . . . ,n+s- l » »• (n+2s, <a c , . . . a ^ , n , . . . ,n+2s - l >) n+ u« (n+s,< a 0 , . . . a ^ j , n , . . . ,n+s- l » For an object (n,a) off!^ the diagram " M M ) • U k f m f k ( m u ] t f m ( n , a ) uk,m € k | i n ( n , f l ) commutes from the definition of € k / m (n, a), since mu k f m (n, a) =n+siv Proposition 24 For m>k>l the adjunctions in Cat enrich to adjunctions in D-Alg( Ca t ) . Proof: It is easy to see that the diagrams on; ix f k,m n x n ; 1 k,m k,m "k,m k,m (n-P) k,m :k,m n x n ; ix u k,m on; commute so f £ ( m and u£ r m are strict morphisms of n-algebras. We have 288 Uk,r n; on; ix f 1 1 X Tik,, •* on: on; k,m |x u k,m •n: 289 1 since for a pair of objects m of Pl and (n, a.) of f l k "p(1XT^ m ) (m, (n,a) ) = m+n+sTl: (m+n,m+a.) > (m+n+s,m+a.) = 'H.k,m(m+n,m+a) = T^^'pOn, (n,a))-Hence T\k ( m is a 2-cell between morphisms of fl-algebras. We show that n x n ; JL^L—on; ; ^ — „ n * ^ e. ^ i For a pair of objects m of f l and (n,a.) o f f l m = m+€krItl(n,a.) : (m+n+s, <m+a0, • • • ,m+ak_i» m+n, . . .,m+n+s-l>) > (m+n,m+a.). The "arrow diagram" for this morphism of is shown below. It is clear that m"p (m, (n,a.)) = e i c , m < m + n' m+-a-) *s m e morphism of Dm- This shows that € k ( m is a 2-cell between morphisms of fl-algebras. 290 • 291 VI. The Lifted Quasi-Adjunctions By proposition 11,16 the tensor product operation induces a 2-functor of two variables fl-Alg (Ca t ) 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 Plk for k 21, we obtain 2-functors F£: A > Pl-Alg( A), given on objects by F£(A) = ( n k®A, vp ® 1). The adjunction f v 1 k (n,-p) „ mk,vp) ^ U k 6 k in fl-Alg( Ca t ) of proposition V.20 gives rise to a strictly natural adjunction (cb-,v k,h k , e k):F >Fi whose value at an object A of A is the adjunction in fl-AlgC Ca t ) f k ® l ( n ® A , v p ® D ^ (n k®A , vp®n n k ® i u k ® i e k ® i Similarly, for m >k 21, the adjunction f v 1 k. m ^ k , m €k , m in Pi-Alg( Ca t ) of proposition V.24 gives rise to a strictly natural adjunction (*k,m.^k,m.hk,m.ek,m ):r"k >*m whose value at an object A of A is the adjunction f v m ® 1 K , m (n k®A , v p®o ^ (n;®A,vp®o ^ m ® 1 u ^ ® ' e i u ® 1 We have the following commutative diagram of strictly natural adjunctions. 292 F " r k k, m k, m Let n - A l g(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 » UF is the strictly natural transformation with T)A = a( 0 ): A > 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' -*• B1 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| k,£ k,r k , 8 k ) for each k21. Form >kil, the para-soft adjunction (F m, U,Tl m,£ m,rm ,8m ) can also be obtained from the para-soft adjunction (Fk,U,T)k,ek,rk,8k ) by attaching using the strictly natural adjunction (^k \m> v k\m'^k ,m' e k,m ) : F k * F m • situation is indicated by the following diagram. *;| 1 Fk V k , m 1 l v ; * k V k D-Alg(A) F u We now describe the para-soft adjunction (F k,U,T) k,£ k,r k ,8 k )in detail. The horizontal unit T) k: 1 > UFk. T) £ is a strictly natural transformation and for an object A of A,T]£A is the composition T)A Ucp kA UFA * UF kA A „ p | ^ A k > A * n k ® A The horizontal counit £ k : F k U > 1. For a commutative monad (B,p),££(B,p)isthe composition V kU(B, p) £(B, p) F kU(B, p) > FU(B, p) * (B, p) This is the strict morphism of commutative monads given by u k ® 1 P ( D t ® B,~p® 1) * (fl® B, v p ® 1) : > (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 ® B 1 ® h f)y ® B' n® B B id ® h oc u k ® 1 n® B' P' B' The vertical unit r£ : 1 » U £ k ° T|kU. For a commutative monad ( B ,p), r£( B ,p) is the 2-cell T|U(B,p) UcprU(B,p) U(B, p) • UFU(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 kA is the 2-cell in f]-Alg( A) given by F j -T iA F^UFA V^UFA F^Ucb^A F-UF-A id V^UF FUcp^A EtpJA = id <f FUF^A £F^A F£A This is the 2-cell between strict morphisms of commutative monads given by nk® A H k ® A 296 Now let (B ,p) = (B ,t ,T\.U ,X) be a commutative monad. The natural monad monad structure associated with the soft adjunction (Fk',U,T]k',Ek,rk',sk' ) gives rise to a monad structure on U( B ,p) = B. The "multiplication" is given by the 2-cell TlfcUO.p) UE k(B,p) U(B, p) * UF kU(B, p) — * U(B, p) T|^U(B. p) Tl kT| kU(B, p) = id / T| kUF kU(B, p) Tl kU£ k(B, p) = id T] kU(B, p) UF kU(B, p) *• UF kUF kU(B, p) *• UF kU(B,p) UF k Tl kU(B, p) U F k U £ k ( B , p) U»;U(B. p) U £ k F k U ( B , p) U £ k £ k ( B , p) - id « / UE- (B, p) UFrU(B, p) U E ; (B, p) U(B, p) cr(k,k ) nk® B l^®1 n k®B U k ® 1 rs P ——* n® B — -Cr(2k) B |o-(u-€ k(k,Js )) f|®B •» B CT(k) 297 since U^€k (k, k^ ) = p 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 k,U ,T] k,E k, 8k ) is the k-fold composite monad structure (b ,ik, r^, uk). • From this lemma we see that, for k>l, the 2-functor 0k: H-Alg( A) » A described in chapter V is the lifted 2-functor of chapter IH obtained from the natural monad structure associated with the soft adjunction (F k,U,T] k,£ k,r k , 8 k ) . Recall from chapter V that there is a para-natural adjunction (^k'^k-nk< * 0k, whose vriue at each commutative monad (B,p) is me adjunction B Bv IfQ k:U — -» U is the para-natural transformation Q k = U E k ° T ] k U , there is a modification z k » V k, u w k whose value at a commutative monad (B ,p) is the universal cone 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 k U k F i ^ k Fk^lkU a k : F k ^ k F kU £ k F k u c k c k - id / b k : F k v k For a commutative monad (B ,p), a k( B ,p) is the 2-cell in D-Alg( A) given by n k ® B k 1® u, n k ® B | € k 0 1 n k ® B u : ® i n® B i 299 u ; ® uk n® B while b k( B ,p)is the 2-cell in H-Alg( A) given by 1® t ku,. 1 1® ?! n;®Bk u k ® 1 n® B 1® u. To check the first part of the coequalizer hypothesis we need to find a coqualizer for the two 2-cells a k(B,p) andb k(B,p) in D-Alg( A)( F^0 k( B ,p),(B ,p)) = fl-Alg( A)( flk ® B k / p ® 1),(B,p)).Tc this end we consider the 2-cells obtained by taking the horizontal composition of Ua k( B ,p) and Ub k( B ,p) with cr(n,a.) : B k • D k ® B k for an arbitrary object (n,a.) of D k . Uak(B,p)°cr(n,a.) is 0"(n, a) n k®B k JK®1 n^®By u k « uk n® B cr(n +k) cr(u k € ^ ( n , a ) ) f|®B a(n) 300 where p (n,a) is the image under the monoidal functor f l > A( A,B) determined by (B ,p) of u(n,a.) = u k € k ( n ' A ) : n+k • n. Hence U(n,a) : n + k * n can be pictured as follows. u(n,a) : * n + k * * n is the 2-cell in D-Alg( A) given by the diagram 301 t n - a k - l _ 1 On the other hand, Ub k( B ,p) 0 cr (n,a) is 1 ® t k u t a(n, a) n ^ B K | i ® s f c n;®B > — — • n® B — - — > B ® u. Our first task will be to find a coequalizer for the two 2-cells ^ ( n , f l ) U k t n + k u k t n u „ Let X (n-a) : n > n be the morphism of fl given by X<n,a> = (a 0+X< 1' n- aO- ) c>+k-l)(a 1+X( 1' n- al- k)+k-2) • • . ( a j ^ + X * 1 ' " - 3 ^ - 2 ) +l)(a k_ 1+X< 1' n _ a)c-l- 1)) n-1 a k - l ak-2 n-1 n-2 n-1 We simplify this diagram to 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 n > t n be the corresponding 2-cell in A( A ,B). This 2-cell can be pictured as follows. B t n _ a k - i - l . B X ( 1 ' n " a J c - i - 1 ) t n ~ a k - l _ 1 ^(1, n-a^k+1) n- a 0 - k ) ^ y' t a l - a 0 B • B B t ao tn-ao-k Note that if (n, a) = (k,Jt), where Ji = <0,1, . .., k-l>, wehave \(k,W = x ( k ' n " k ) : t n >tn. In particular, \ ( k ' w = id:t k » t k. Also M ( l t, w = p k. 304 Lemma 2 In f l we have the relation: "X(n.a) JJ ( n > a ) = (n-k+Uv.) ( X <n'*) +k) Proof: X <n»a) y j n a j can be represented pictorially by the diagram n+k-1 a k - l while (n-k+uk) ( X (n'*)+)c) can be represented pictorially by the diagram n+k-1 a k - l • The corresponding relation in A( B ,B) is: X(n»a> « M(n,a) = t n - kMk ° X ( n , a ) t 305 Let S ( n , a : t n u k > tn-*U)c be the 2-cell in A( B k ,B) given by 5 ( n, f l ) = t n ~ k S k B X<n-a> u k, that is, 5 (n, a) is the 2-cell \(n, a) B t n-k B Notethat 5(k,kj = 5k- Our £ u m is to s n o w that the following diagram is a coequalizer diagram in A( Bk,B). U(n,a) Uk * t nu,, t n + V S(n,a) t n ~ V 1% Indeed we shall show that it is a split fork. First we check that it is a fork. Lemma 3 Proof: S(n, a ) ° M ( n, f l )u k - C ( n # a ) • t«C K. 5 (n.a) • u< n,a) uk " ^ n _ k?K • * ( n ' a > u k • M ( n,a) uk = t n ~ k £ K o t n~ ku ku k o \ (n,a) t k u k by the relation following lemma 2. = t"- kS K » X< n-a) U k o t n - k 5 k (See the following diagram.) • (n,a) 306 B • Let f \ ( n a ) :n-k » n be the morphism of fl given by ^<n,a) = a 0 +n+ai-a0-l+n + +rl+n-ak_1-l_ ^ (n, a) ^ fescnted previously in chapter V. As before, let T\ ( n t a ) : t n _ k • t n be the corresponding 2-cell in A( B ,B) determined by the commutative monad (B ,p), so that ^(n,a) = t a 0 T \ t a 0 " a l - 1 r i T\t n _' ak-l _ 1_ Note that n^k.) = T l k -Lemma 4 We have the following relations in f l : CO >>'fl) n{n,a) = n - k + kn, 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* \<n'a> • T i ( n f A ) = tn - * T i k , (»)* M(n , a ) • n ( n , a ) tk = ( X ( ^ ) , - l . Proposition 5 t n + k u k » t \ ^ t n " k u k t n ? k is a spit fork, split by \ n , a ) t k U k « X < n ' a > U k ' " K ^(n, a )Uk Proof: <A) 5(„, a ) °Tl(„, f t)U k = t*-*?k • X ( n ^ ) U k • n (n, a)U k t n" k5 k o t n - k n k by (i) id. t n + V « t n u k « t n _ k u (B) From (ii)* we have u ( n, f l ) 0 n ( n , a ) ^ k • X^-a) = id, h e n c e ^(n,a)Uk ° n ( n , a ) t k u K • X ( n ^ ) U k = i d . = ^ k - T l < n , f l ) t k U k • X ( n ^ > U k , where the last equality follows from the diagram 308 • Note that for the special case (n, a.) = (k,k.) the split fork of proposition 5 reduces to the split fork "k uk t 2 k a t ku„ ^ k split by t 2 k a T l k t k U ) c tKU, which is the split fork associated with the universal tk-algebra for the monad (B ,tk ,ri k ,uk). We now investigate the functorial nature of the split coequalizer of proposition 5. For this purpose we construct a functor $ k: f | k > A( B k ,B), which is given on objects by $ k (n, a.) = t n _ k u k . 309 Since the morphisms of f l k are obtained from those of f l _ it is clear that they are generated under composition by morphisms of certain specific types. For each type of generating morphism F, of f l k we give the value of $ k( F,). Note that in the diagrams drawn to represent these generating morphisms we follow the 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 $ k(f) = t h - i X t e + i - k u k : t n ~ k u k > t n _ k u k -310 Type: S2 f = h+X+e: (n,.a) > (n, <a0, . . ., a j _ l f a ±+l, a i + 1 , ak-l >> w nere h+e+2=n anda^h. n-1 »k-l a i + l h+1 h=a^ a i - l ao aj^ +1 The single cross-over switches the base point a A upwards. We set $ k( J)= id : t n - k u k > * n~ k uk • Type: S3 f = h+X+e: (n,a) > (n, <a0, . .., a ^ , a ^ l , a i + 1 , , ak_1>) where h+e+2=n and a^h+1. n-1 a k - l a i + l h+l=ai-h a i - i a i - l The single cross-over switches the base point a.^ downwards. We set $ k( J) = id: t n _ k u k >t n _ ku k. Type: CI % = h+u+e: (n,a) > (n-1, <a0, . . . , 3 . ^ , 3 . ^ - 1 , a j c_ 1-l>) where 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>k(f) = t h - i u t e + i - k u k : t n - l c u k » t n - k " 1 u k . Type: C2 | = h+p+e: (n,aj » (n-1, <a0, .. . , a i r a i + 1 - l , , a k_ 1-l>) where h+e+2=n and a±=h. 312 The single collapsing brings together the base point a^ ^ = h and the neighbouring point h+1 above In this case we let $ k ( f ) be the 2-cell B k ^ » B B • e+l+i-k ^(l,e+l+i-k) 4e+l+i-k B ,h-i thatis, * k ( g ) - t n - 1 - * ? ^ ! , * o t h" iX< 1'e+i+i-Jc)u k:t n" ku k » t n - k _ 1 u k -Note that if h=l, u < 0 > 1 ( k = 1 :B » B. Type: C3 £ = h+u+e:(n,a • (n-1, <a0, . .., a^-i, a ^ - l , a k_ 1-l>) where h+e+2=n and a^h+1. The single collapsing brings together the base point a i=h+l and the neighbouring point h below a±. We 313 use the same 2-cell as for the previous case and set $k(D = t n - l - k 5 u < i > 1 ^ o t h - i \ ( l - e + l + i - k ) U k . t n - k U k > t n - k " 1 U k . Tvpe:N |" = h+rf+e: ( n , a j > (n+1, <a0, . . ., a i_ 1,a i+l, a k - l + 1 > ) where h+e=n and ai_1<h<ai. A new point is introduced at the level h between the base points a i _ 1 and a±. In this case we set $ ] t ( | ) - th - i n t e + i- ku k : t n- ku k * t n " k + 1 u k . The morphisms of H k are generated under composition by the seven types of special morphisms just 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 $ k extends to a functor on the whole of f l 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 k - l h-l=a. *1~1 ijoceoccMooc n-1 a k - l »i+l » i - l a 0 0 The image of each of these morphisms under $ k is t h ~ 1 _ i X t 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 $k. The case where no base point is affected is also easy to check and depends on the 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) First we consider relations of the type depicted as follows. X (1+M) n-2 n-2 The image of each of these morphisms under $ k is t h - 1 - i u t e + 1 + i - k u k : t 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 $ k is the 2-cell 316 B where h+e+2=n and hSl. 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 $ k are exactly the same as in the previous case. . 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) . The first of 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 $ k is the 2-cell 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 the right hand 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 $ k are exactly the same as in the previous case. 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 $ k is t h ~ 1 - i M t e + 1 + i _ k U j c : t 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 $ k as can be seen by using the relation tp • At • t\ = X • pt in A(B,B). The image of the left hand morphism under $ k is the 2-cell e+l+i-k * l,k X (1,e+l+i-k) 4e+l+i-k where h>l and h+e+2=n, which is J l,k e+l+i-k *e+l+i-k < i > x(l,e+l+i-k) *e+l+i-k ^(1,e+l+i-k) e+l+i-k The image of the right hand morphism under $ k is the 2-cell This is the same as the image of the left hand morphism under <$k. (See lemma V,12.) 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 $ k is B • J l,k t e+l+i-k X' (1,e+l+i-k) •e+l+i-k -,(1, e+l+i-k) 4e+l+i-k •* B •B J B T I T I ^ j h - l - i 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 h-1 h+l=a 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 B ^e+l+i-k j h - l - i 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. The evident relations derived from (fl3): X 2 = 2 and (fl6): p X = p can easily be seen to be preserved under $ k, so we are left with (fl5): x (n+D = i+n and (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 $ k is the 2-cell t h - i n t e + i " k u ) c : t n _ k u k > t n _ k + 1 u k w h e r e h £ 0 andh+e=n. 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>k is given by the 2-cell t' e+2+i-k <i> J l , k t t ^(l,e+2+i-k) 4e+2+i-k , h - i where where h£0 and h+e+2=n. This is the identity 2-cell on t 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 fl are also preserved by $ k. To indicate why this is true we check one of the cases arising from the relation (Pfl 10). 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 l,k •* B . (1,e+l+i-k) ^e'-l+j-k th'-h+i-j t h-i where h 1 >h>0, a^h, a j_x<h', h' +2<a j, i< j-1 and h+e+2=h' +e' +2=n. This is the same as the image of the right hand morphism under namely the 2-cell B Proposition 6 $k : Hk »A(B k,B) is a well-defined functor. Let ¥ k : H k • A( B k ,B) be the functor corresponding to the composite 1-cell u £ ® 1 p ^ k 0 g k * n ® B : *• B Thus ¥ k is the composition f l k • f l •A(B.B) *• A (Bk,B ) where $ is the (monoidal) functor determined by (B,p)andUk* = A(uk,B). A. A> ¥ k is given on objects by ¥ k (n,a.) = t n u k and for a morphism F.: (n, a.) •» (m,bj off] A, ¥ k( |~) is the 2-cell Proposition 7 A* ?k : *k >$k givenby 5 k(n,aj = S<n,a) = t"-*5 k • X<n'*>uk / s a natural transformation. Proof: We show that the diagram ? k(n, a) l k ( n , f l ) \(m,b) : • * k(m,b) Ck(m,b) commutes for each generating morphism |~: (n, A.) »(m, b_) of f l k . Type: SI g = h+X+e: (n,fl) »(n,a) where h+e+2=n , a ^ ^ n and h + l ^ . We have $ k( g~) = t h - i X ^ 1 ^ ^ and * k ( g) = t hXt eu k. Hence 5k(n,a) • ¥ k (D - t n _ k 5 k o X<n-a>uk • t h X t e u k and $k(D °£k(n,fl) = t h - i X t e + i _ k u k o t n _ k 5 k • X<n-a>uk = t n " k 5 k • t ^ X t ^ X • X <n'a> U ] c, which is the 2-cell The following diagram shows that the relation: X ("'a) (n+X+e) = (h-i+X+e+i) X ( n holds in fl. 327 Hence in A(B,B) we have \<n,a> oth\t e - t h - i X t e + i • X <n'*>. This shows that 5k(n,a) • ¥ k(f) = $ k(f) • 5k(n,a) . Type: S2 £ = h+X+e: (n,a.) > (n,b) where h+e+2=n , a ^ h and 12 = < 3 Q ' • • •' a i - l ' a i + l » ai+l» a k - l ^ ' We have * k ( f ) = id and ^ k ( | ) = t hXt eu k. Hence ? k (n,i2) • f k ( | ) - t n _ k $ k • X <n^> u k «»thXteuk and ik(T) •5 k(n,a) = t n " k 5 k €»X< n^>u k. The morphism X <n'a> (h+X+e) of f l of can be pictured as follows. 328 This morphism is the same as X <N'3->. Hence in A( B ,B) we have \(n'k> • t hXt e = X *n'a>, so 5n(n,b) 8 V I ) = $ k(|>5 k(n,.a) . Type: S3 £ = h+X+e: (n,a.) > (n,h) where h+e+2=n, a^=h+l and h = < a c • • •' ai-l' ai~l» ai+l' ^ - l ^ We have ik (n,a) • = t n~ k5k o X <n-k> u k ® t h X t e u k and $ k ( D e?k<n'a-) = t n _ k5k ° X ( n , a ) u k , since i k ( | ) = id. This case is very similar to the previous case. The morphism X ( n < ^ (h+ X+e) of f l of can be pictured as follows. 329 This morphism is the same as X (n»a). Hence in A(B,B) we have X<n'k) « t h X t e = X ( n' a ),so Type: Cl % = h+(i+e: (n,a.) » (n-l,b_) where h+e+2=n, a^-ch, h+l<a ± and k = * a 0 ' • • • ' a i - l ' a i ~ l f a k - l - ^ • We have and 5ic<n-l,b> • * k ( D $ k(5~)°5 k(n,a.) = t ^ u t * 1 * " * ^ ® t n ~ k 5 k • X Uk - t n - k _ 1 5 k o t h - i u t e + i u k • X<n'a>uk, 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 <n>a>) holds in fl. Hence in A(B,B) we have \(n-l,b) o t hMt e = t h _ i ( j t e + i • X <n-a). This shows that £k(n-l,b_) « ¥ k(f) = $ k(f) ® £ k (n,aj . 331 Type: C2 g = h+u+e: (n,aj > (n-l,b_) where h+e+2=n, a ^ h and fc - <^Qr • • • f a^, a i + i - ^ ' ••••>ak-l~^ The following diagram shows that the relation : \(n-l,h) (h+]T+e) = (n-k+i-l+M+k-i-1) (h-i+X< X' e + 1 + 2 i - k>+k-i) X<n-a) holds in fl. Using the corresponding relation in A( B ,B) we obtain 5 k (n-l ,bJ • * k ( D - t"" 1"^ • tn-k+i-lpt^-iun • t h _ i X CWe+l+2i-Jc>tk-iUjc .x< n'A>U k = t " - 1 - ^ otn-k+i-lptk-i-1uk ot n - 1 -kX( 1 ' i >tk-i U k e t h - i X e+l+i-k) xk^ o\(n,&)u^ 333 334 335 by lemma V,12. This shows that £ k (n-l,b_) • ¥ k(f) = $ k(f) ° 5 k <n/2.) . Type:C3 g = h+p+e: (n,.a) > (n-l,b_) where h+e+2=n, a^h+1 and h - <aQ' • • • ' a i - l ' a i - ^ - ' a k - l ~ ^ " h+l=a We have the relation in f l : 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<n'a>, 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 k(n-l,b_) ® ¥k(g~) = $ k ( D • S k (n, a.) . Type: N g = h+Ti+e: (n,a.) > (n+l,b_) where h+e=n, ai_1<h<ai and fc = <a0, .. . .a^.a^l, ak_1+l>. a i - l We have and which is the 2-cell S k(n+l,k) • * k ( f ) = t n + 1 - k 5 ) c •X(n+l,b) U k • th'nt«uk K(T) • 5k (n/a.) = t h _ i T l t e + i - , t U k • t n " k 5 k o X <n'3> u k = t n _ k + 1 5 k • t h _ i u t e + i U k • X<n'a>uk, 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~<n+1'k> (h+T\+e) = (h-i+T\+e+i) X < n 'A> . This relation is demonstrated by the following diagram. 337 Let P k :n k ® B k > B be theunique2-cell corresponding to $ k :n k > A(B K ,B). Since £ k : ¥ k > $ k is a natural transformation, there is a unique 2-cell p k: p( U k ® u k) > p k such that for each object (n,a) of D k <r(n,a) = u £ ® u k p • n® B -* B Pk B K ] l5 k(n,a) $ k(n,a) We now show that ' P ( u ; € k ® U k ) p ( u k ® t k u k ) ^ p ( u k ® u k ) -P ( u k ® 5 k) is a coequalizer diagram in A( f l k ® Bk, B). This is a consequence of the following general result. 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 f g 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> • cOcrCu) = ® |3)o"("u) = fO"("u) • (3aCu), so there is a unique 2-cell ^( 7 j ) : hcr( u) > ka(U) such that the diagram 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 hMo~,k„o":D • 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 f a ( u ) gcr(u) Vcr(lT) ha(u) fa(f) (3a(U) oca( v) gcr(f) ga( v) Ycr(v) h a ( D ha(v) |3a(v) <p cr(7) 4* (V) 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)- kadi) ha(D k a ( 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 O-(U) A- > D®A gcr('u) I Ycr(U) ^ ^ hcr(u) gcr(u) cr(TJ) D®A kcr(u) Hence 6 ° TC= f>, as required. Corollary 9 p ( u k ® t k u k ) P C u j ^ ® u k) P ( u k ® u k ) P(u£® 5 k ) is a coequalizer diagram in A( D k ® B k, B). • • 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| k® B k, "p® 1),(B,p)). We wish to show that the whole diagram is a coequalizer diagram in this hom-set. First we show that p k determines a strict morphism of commutative monads and that p k is a 2-cell between strict morphisms of commutative monads. Lemma 10 p k = n k ® B k Proof: -> B is a strict morphism of commutative monads. First we show that the diagram t® i commutes. For each morphism !•: (n,aj > (m,bj o f f l k 0"(n,a) B k | crCT) n k ® B k and 0-(m,b) 0"( n, a ) B k Jrff) n j e S , t® i n k ® B k -a(m,b) 343 t n - k + 1 u . tm-k+l We need to show that these two 2-cells are equal. It suffices to show this for generating morphisms |^of D k . It is easy to see that they are equal for each type. As an illustration we consider a morphism of type C2. | = h+ p+e: (n,aj > (n-l,bj where h+e+2=n,a—h and £L. = < a 0 ' • • -f a i f ai+l~lf a k - l - 1 > -h+1 h=a. In this case t$ k(lf)and $ k (1+f) are each given by the 2-cell }<x> t ' e+l+i-k X (1,e+l+i-k) X e+l+i-k ,h+l-i Next we show that For each object (n,aj of f l k taking the horizontal composition of the second 2-cell with C"(n,a) : B k > f ] k ® B k gives 0"(n, a) 6 k |o - rn(n)) n k®Bj $i,(n, a) a(i+n, l+a) B k I l k(n+n) $ v(l+n,l+a) according to the description of $ k on generating morphisms of type N. This is the same as the horizontal composition of the first 2-cell with a (n,a). It is easy to see, in a similar way, that n k®B k-r t ) 2 ® i nk®gk J[-ii®i n k®B, and ' t® 1 n k®B k- flx B r t ) 2 ® i n k®& k _ i " x ® i n ^ B , r t ) 2 ® i using the description of $ k on generating morphisms of type CI and S1 respectively. Lemma 11 p k : p( U k ® u k ) > p k is a 2-cell between strict morphisms of commutative monads. Proof: We need to show that n;®BK B ' t® i n ; ® e k U k Q S U 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 <n'a) ,so these 2-cells are the same. • Proposition 12 P ( U k € k ® U k ) P ( u k ® t*u k) p ( u k ® u k) P ( u k ® 5 k) is a coequalizer diagram in D-AlgC A)( ( f ] k ® B k, v p ® 1),(B,p)). Proof: Let (g,oc): ( f l k ® B k, "p ® 1 ) — »(B ,p) be a morphism of commutative monads and let If: p( U k ® u k) • (g ,oc) be a 2-cell between morphisms of commutative monads such that r o p ( u k e k ® u k) = K «p(u k ® 5 k). Let (n,a) be an object of f l k . The image of the above diagram under the functor cr(n,a)*:A( f | k ® B k, B) > A(B k, B) is the split fork ^(n,a) uk t n + ku„ 5(n,a) t n " k u , t n5v which is split by t n + k u. t k u v • X ( n ' a ) U , , t nu„ ^<n,a>Uk t n _ k u . We have 1fcr(n,a) • M (n,a> u k = Ycr (n,a) ° t n 5 k so there is a unique 2-cell \> (n,a) : t n _ k u k > gcr (n,a) such that the diagram 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,A)Uk-Further, by the argument of proposition 8, there is a unique 2-cell 6: p k >g such that 6cr(n,a.) =^( n, f l) =Tra(n,a.) • 7 \ ( N A ) u k for each object (n,aj offl^.thatis, gcr(n, a) We check that 0 defines a 2-cell between morphisms of commutative monads 6: p k > (g ,oc), that is, Pk 348 However, by hypothesis, Y : p( U k ® u k ) monads, so •> (g ,oc) is a 2-cell between morphisms of commutative 349 P ( u k ® u k > 0"(n, a) g that is, Also, the relation t T i ( n a ) = 1^ (1+11, i+a) clearly holds. Hence the 2-cells in the diagrams (i) and (ii) are equal. • We have now demonstrated that the first part of the coequalizer hypothesis is satisfied. It remains to check the naturality condition. 350 Lemma 13 Let be h: A > Bk a 1-cell in A . Then the coequalizer diagram of proposition 12 is preserved under the induced functor F kh* :D-Alg(A)((nk® B k / p ® 1),(B,p)) * D-Alg( A)( (D k ® A, vp ® 1),(B,p)), where F kh= 1 ® h:(fl k® A, v p ® 1) > ( H k ® B k , v p ® 1). That is, P ( U * ^ ® U * h ) , _ p k ( l ® h ) P(u k ® 5kh) is a coequalizer diagram in H-Alg( A)( ( f l k ® B k , v p ® 1),(B,p)). Proof: One can first check that it is a coequalizer diagram in D-Alg( A)( D k ® A ,B). This follows because, for an object (n,a.) of f l k , its image under cr(n,a.) * : A ( f l k ® A,B) > A(A,B) is the split fork ^(n,,a)"kh " t nu kh > t n" ku kh p ( u ^ ® t k u k h ) ~ * p ( u ^ ® u k h ) * p k(1®h) t n5 k h which is split by t n + k u k h * - • t nu kh < t n - k u k h - n ( n , a ) ^ U k h « \ < n ' a > U k h ^ ( n , a ) U k h 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 (Fk\Gk,11k,Ek,rk lSv.). We now describe this soft adjunction in detail by giving explicit formulas for the horizontal and vertical units and counits. The horizontal counjt £ k : F k u k -» 1. -» (B ,p) is the strict morphism of For a commutative monad (B,p), E k( B ,p): F k0 k( B ,p) commutative monads given b y p k : n k ® B k > B. According to the general construction of a lifted soft adjunction given in chapter in, there is a A A A A modification n k : £ k V k ® B k > £ k whose value at a commutative monad ( B ,p) is the 2-cell p k: p( U k ® u k) > pk. Hence the diagram Frvk(B,p) F j & C B . p ) — * > F£U(B,p) • e;(B,p) (B,p) in D-Alg( A) corresponds to the diagram nj;®e k 1 ® u E J B . P ) p ( u j ® 1) in A.Let(h,oc):(B,p) (B,t,TI,U,X) and (B'.p') = (B'.f ,n',P'X).Then -* (B' ,p') be a morphism of commutative monads, where (B ,p) = F ; U ( B , P ) F kU(h, ex) FkU(B',p') £^(B, p) •* (B.p) Z 1 e^B ' .p 1 ) <h, ex) (B'.p1) is the 2-cell between morphisms of commutative monads given by the 2-cell 352 f ) k ® B 1® h ® B' u ^ ® 1 n® B id 1 ® h u k ® 1 n® B' p' B' in A. Let p'(u k® (t') ku' k) P'(u k® u'k) p'k (0 p'(u k® ?'k) be the coequalizer diagram in fl-Alg( A)( ( f ] k ® B'k,vp ® 1), ( B',p')), associated with the commutative monad ( B' ,p'), that is, it is the coequalizer diagram ak(B',p') E f c ( B ' . P ' ) ° F k n k ( B ' . p ' ) o F ^ v ^ B ' . p 1 ) b ; ( B ' , p ' ) n £ ( B ' , p ' ) ^ £ k ( B ' , p ' ) o F k V k ( B ' , p ' ) > e k ( B ' . p ' ) of chapter i n . Denote 0k(h,a):0k(B,p) • Gk(B',p') by h k:B k > B 'k. Then, taking the horizontal composition of the coequalizer diagram (i) with F k0 k( h ,a), we obtain the coequalizer diagram p ' < u * € > ; ° u A > p k d ® f i k ) p'(u k® (t') ku' kh k) _ ^ P'(u;®u' kn k) — - — • P ' k ( 1 ® h k ) P ' ( u k ® S k h k ) (ii) According to the general lifting construction £ k( h ,cc) is obtained from the coequalizer diagram (ii) and then fits into the following commutative square of 2-cells in n_Alg( A). 353 n k(B',p ')°F kO k(h, oO E k (B',p ' ) °F kV k (B',p ' ) °F kO k(h, °° * e k(B',p ')°FkOk(h, oc) £ v ( h , c x ) o F k v k ( B , p ) £k(h, oO (iii) ( h , a ) o E - ( B , p ) o F k v k ( B , p ) (h, oO°n'(B,p) (h, od°E v(B,p) where nk(B',p') ° F kO k(h,a) = p'k( 1®hk)and Ek(h,oc) ° F kv k(B,p) is the 2-celJ between morphisms of commutative monads given by the 2-cell n k®& k " k ^ k „ P n® B B 1® h. id D v ® B1 1® h cx n® B' u k » u k p' B' in A. The square (iii) of 2-cells in fl-Alg( A ) arises from the following commutative square of 2-cells in A. P' K(1®h k) P'(u k®u' kh k) • P ' k ( 1 ® h k ) c x ( u k ® u k ) ock = UEk(h, oO h p ( u k ® u k ) hp. hp, We have introduced the notation t x k: p'k( 1 ® h k) » hp k for the right hand 2-cell in this diagram, that is, 354 1 ® h, ex. nk®S'k B' For each object (n, a.) of H k , the image in A( B K ,B') of the coequalizer diagram (ii) in A(flk® B K , B ' ) under the functor cr(n,a) „ :A(flk® B K , B ' ) > A( B K , B ' ) is a split fork. cx( u k ® uk)cr (n,a) is the 2-cell o-(n, f l) _ _ e u k ® u k 1 ® h n K ® B K n® B n® B' P' cx t n ( t ' ) n while hp k (n, a.) = h 5 ( n ( S ) is the 2-cell B y{n, a) t n-k Using the evident splitting 2-cell, we see that cxkcr (n, a) is given by 355 Lemma 14 For a morphism of commutative monads (h,oc):(B ,p) > (B',p'), Ek(h,cx) isthe 2-cell between morphisms of commutative monads given by the unique 2-cell c x k such that oc k O"(n,a.) = ex < n _ k > u k foreachobject (n ,a . ) of f l k . • The horizontal unit T ) k : 1 -» 0 k F k . To obtain results which we can also use later on, we consider the composite 2-functor 0 k F^ where m>k>l. For each object A of A, O kF^A = Dk( ® A, "p ® 1). We shall relate this object to the Eilenberg Moore object for the k-fold composite monad (H m , " t k , v T i k , v p k ) associated with the commutative monad (Dm,"p) = (nm."t, vri, vp, v\)in Cat. Using the standard description of Eilenberg-Moore objects in Cat, this Eilenberg-Moore object is the category of "tk-algebras for the monad ( , " t k , v T i k . v M k ) . which we 356 denote by 0^ m . The objects of C\kim can be considered to be triples (n, <p ,a.), where (n,a.) isanobjectof C\^andf:k > mis a morphism of 0. A morphism |: (n, a.) > (n1, <p',a.') in f \ ( m i s a morphism ?:(n,a.) > (n1, a.') of such that the diagram commutes. We have the usual adjunctions n k, m n k Uk where "fk and "u k are given on objects by v f ] c ( n , a.) = (k+n, k, k+a.) and v u k (n, f,a.) = (n,a.) respectively, with the obvious extension to morphisms. For an object (n, <p, a.) of n k f m , "€ k (n, <f ,a) : (k+n, Ji, k+a.) >(n, <p,aj is the unique morphism of f)ktm such that the diagram nTi+k n+kT\ n • n+k * k commutes. The universal cone associated with C\k>m is n: n k,m Uv€ k c k 357 For each object A of A , ( D m ® A, v t k ® 1 , v T \ ) c ® i , " p k ® 1 ) is a monad in A , and we have a v t k ® 1 -algebra X ® L n;®A ^ Q k . m A : H k , m ® A * Oj^ F^ A = 0 k ( D m ® A, ~p ® 1) be the unique 2-cell such that n k , m ® A © V m A k,m k m u k F ; A ^ k F m A V k F m A U F ^ A m ' u k ® 1 ni® A nk,m®A ' t k ® i v u k ® i nM®A It is straightforward to check that this defines a strictly natural transformation © k , m :nk,m® - > U K F 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 k t ^ is not an isomorphism. 358 Lemma 15 T | k A : A -» U kF kA is given by the composition o-(k,Js,Js) f ] k ( k ® A : • U kF kA Proof: According to the construction of chapter HI, T|kA is the unique 2-cell such that VkF,:A. TkA UF kA v k F k A njJFJA U F k A UF kA T]-UF kA U£ v F v A UF£UF kA — > UF kA T l v A where the second 2-cell is an QkFkA-algebra. This second 2-cell is 'k"k.® 1 cr(k,Js) n k ® A n k ® A a(2k,k+Js) A 1 a(Mk> f l k ® A ff(k,Js) where the last equality is obtained using the fact that € k(k,Ji) = 7Tk: (2k,k+JO —»(k,kj The lemma now follows since 359 v k F i c A o-(k,k,Js) - e k , k A * < \ k ® A * VJA z kF^A v k F k A ^ k F k A 'uk® 1 0"(k,k,k) - „ „ A • n k i m ® A -uk€k® i n m ® A 'uk® 1 fl;®A tr(2k,k+k) (T(2k,k+Js) A ]lo-ru k€ k(k,Jj,k)) f l k ® A A I A ( M K ) D K ® A 0-(k,k) 0"<k,k) Notethat v € k (k, k., kj «= u k: (2k,k.,k+kj • (k,k.,k.), which gives the last equality. • The vertical unit r k : 1 » 0 k£ k o T|k0k. Lemma 16 r k : 1 "* uk ^ k ° ^ lk uk / s t n e identity modification. Proof: For a commutative monad (B ,p), rk( B ,p) is constructed from the 2-cell Vk(B,p) Uk(B,p) • U(B,p) Tl K O k(B,p) TlfcVk(B,p) = id Y T| kU (B,p) UF^Uk(B,p) • UF^U(B,p) UF^Vk(B,p) ue | UnJ(B.p) ue k(B, P) a(k,js) a(k,k) id n^®B k-V 1® u. f ) k ® B 1 Pk Now pko-(k,k.) = 5k, so this 2-cell is Thus it is the identity 2-cell on u k: B k > B. It follows that 361 TlKO k(B,p) ^ „ Uk(B,p) *> U kF kU k(B,p) r\(B,p) u k e k ( B , P ) Uk(B,p) V k(B,p) U(B,p) is the identity 2-cell on V k( B ,p): 0k( B ,p) » U( B ,p). The lemma follows by the uniqueness part of the universal property associated with 0k( B ,p) = Bk, once we show that TLlUB.p) U kE k(B,p) Uk(B,p) * 0 kF k0 k(B,p) > Ok(B,p) is the identity 1-cell. Taking the horizontal composition of this 1-cell with V k(B,| Ok(B,p) U(B,p) V k(B Q k(B,p) U(B,p) we obtain 'uk® k uk s C-(k,k,k) A a s Bk » nk f k ® B k " U K € K ® 1 v t k ® 1 362 CT(2k,k+Jk) a(k,k) lk(2k,k+Js) K Pk(Mk> B $k(k,Js) -+ B The last step can be checked from the definition of $ k : f l k -+ A(Bk,B). The vertical counit 8 k : £ k F k ° F k T ] k -» 1. The vertical counit, evaluated at an object A of A, namely s k A , is obtained from a certain coequalizer diagram involving two 2-cells whose vertical composition with s^A coincide. Then s k A fits into the commutative triangle E j ^ A o F ^ A E k F k A o F ; T i k A *k* First we identify the 1-cell E^F^A. LetQ k : n k > C a t ( l \ ( k ,D k ) denote the functor $ k:fl k -+ A( B k ,B) of proposition 6 for the particular case A = Cat, (B ,p) = ( f| k, vp). Thus Qk is given on objects by Qk (n, a.) = " t n _ k " u k and, for example, if % = h+p+e: (n, a.) > (n-l,b.) where h = < a 0, . . .a i f a i + 1 - l , ..., a k _ 1 - l > is a generating morphism of type C2, then QK( J) is the 2-cell in Cat (that is, natural transformation) given by the diagram extension to morphisms. 364 Now E KF K A : F £ 0KF £A • F K A is the strict morphism of commutative monads given by the 1 -cell U £ K F K A : n k ® O K F K A > f l k ® A. Take the horizontal composition of this 1-cell with 1 ® 0 k / K A : D k ® ( H k f K ® A) » D k ® U KF KA and consider the corresponding functor f l k > A( D k k ® A,D k ® A ). This functor can be decomposed as the composition QK ~ - ® A n k • c a t ( n k f k , n k ) • A ( n k f k ® A , n k ® A)_ We treat £ kF kA o F kV kF kA: F kU kF kA > F kA in a similar way. It is the strict morphism of commutative monads given by the composition n k ® u k F k A — — • n k ® ( n k ® A ) cn kxn k)® A ( u * x 1 ) 0 1 , (fixnp® A V P ® 1 » n k® A Taking the horizontal composition of this 1-cell with 1® © k, kA gives n k ® ( n k . k ® A ) = ( n k x H k ( k ) ® A — - — - — > ( D x n k ) ® A — -— » > n k ® A The corresponding functor f l k • A( f l k f K ® A,D k ® A ) has a decomposition &K „ - ® A n k > C a t ( n k f k , n k ) * A ( ( \ K ® A , n k ® A ) where Rk is given on objects by Rk(n,a_) = " t n " u k and for a morphism ?:(n,a.) > (m,b_) we have Rk(F) = 1 v u k : ~ t n v u k »"t m vu k. Now we look at the 2-cell n kF kA. Let Z k: Rk » Qk be the natural transformation whose value at an object (n,aj o f f l k is that is, Z k is the natural transformation £ k : ¥ k • 9 k of proposition 7 for the case A = Cat, ( B ,p) = ( H k , vp). Let q k: H k x f l k / k » f l k be the functor corresponding to Q k : n k » Cat( Hjc, jt.Ok ) and let T k: v p ( u k x vu k) :—> q k be the natural transformation corresponding to Zk. Thus T k is the 2-cell p k: p( u k ® u k) • p k for the case A = Cat, (B ,p) = (fl k, vp). Applying the 2-functor U to and then taking the horizontal composition of the resulting 2-cell with ] ® ©k,k A : n ^ ® ( D k , k ® A) > n k ® O kF^A gives the 2-cell q k ® l in A. Finally, we observe that the 1-cell F kT] kA: F kA > F k O kF^A in fl-AlgX A) is given by the 1-cell 366 1® <7(k,k,k) l ® Q k k A nk ® A • nk ® (nk(k ® A) : • nk ® oKF^ A _ in A. Note that the diagram commutes, where X is the isomorphism of categories which switches the two factors. It is now apparent that nk FkA ° FkT| kA is obtained by tensoring the 2-cell in Cat with A. Here XCT (k, ]&, kj is the section r • : — * (r, (k,k,k)). We describe s kA in the special case where A = Cat and A = E, the category with a single object. For the sake of simplicity, we identify D x I with D when D is a small category. Then s kH is a 2-cell in D-Alg( C a t ) ( ( f l k , " p ) , ( f l k , vp)) for which we introduce the alternative notation 0k. The general s kA is given by tensoring skII = 6^ with A. 8 k I = 6 k fits into the commutative triangle of natural transformations (2-cells in Cat) 3 6 7 T kXcr<k,k,]s) "p(u kx vu k)Xo - (k , ] s , ] s ) • q kXa ( k , ] j , J s ) 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 k of the coequalizer diagram involved here is a split fork, we have an explicit description of 6 K . Indeed, for an object (n,aj o f D k , 6k(n,a.) is obtained as the composition of €k(n,a.) with the morphism of H k given by evaluating the natural transformation •tn at the object (k,k.,k.) of D k f k . N o w "n{n,&)"uk(k,k,]s.) = vn(n,a) {k'& :"t n - k(*rJt> >vtn(k,Ji) T\ ( n > a )+k: (n,n-k+Ji) » (n+k,n+jc), thus e k(n f Ja) = €k(n,a_) ° v"n. ( n a ) v u k (k,i, k.) can be pictured as follows. 368 369 Letc k = qkXo-(k,k.,kJ if)* > f l k . Then s k A : E k F k A o F ^ T ^ A > Aisthe2-cell between strict morphisms of commutative monads given by n k ® A | ® 1 Hk ® A 1 The functor c k :Ok > H k is given on objects by c k (n, a.) = (n, n-k+k.) . Thus the base points are all "moved to the top". To complete the description of the vertical counit, we give the action of c k on morphisms. For a generating morphism F, = h+X+e: (n,a) » (n,a) of H k of type SI, where h+e+2=n, ai<h and h+Ka 1 + 1, we have c k(|) = " t h _ i ^ v t e + i - k " u k (k,Js,Ji) = ^ -^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 k( J) is the identity. For a generating morphism F, = h+X+e: (n,a) > (n,a) of type CI, where h+e+2=n, a^h , h+l<a 1 + 1 and h = < a 0, • .., a i f a i + 1 - l , • • •, a k _ 1 - l >, we have ck(T) = ^-^p-t^-^u^k,*,*) = vt h- i vp vt e + i- k(k,li) = 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 > (n-1, bj of type C2, where h+e+2=n, a^h and h = < a 0, .. ., a i f a i + 1 - l , .. ., a ^ j - l >, c k(T) is given by the value of the natural transformation 370 at the object (k, k., k) of f \ ( k . ™s i s ^ morphism of given by the diagram For a generating morphism T=h+7T+e: (n,aj * (n-l,bj of type C3, where h+e+2=n, a.j=h+land h = < a 0, . . . . • r a j ^ - l >< ck(T) is the same morphism of Pl^ as for the previous case. For a generating morphism |"=h+T\+e: (n,aj » (n-l,b.) of type N, where h+e=n, ai_1<h<ai andb. = < a 0, .. . .a^ta^+l, . . . .a^.j+l >, we have C k ( | ) = vt h-i vn vt« + i- k vu k(k,Js,Js) = " t h - i ^ v t e + i - k ( k f J s ) = h-i+T\+e+i-k:(n,n-k+k) > (n+1,n-k+l+k). 371 c k has the following simpler description. For any morphism j- : (n, a.) is the unique morphism of fl £ such that the diagram ^(n, a) -» (m,b) of Dv ,Cv(f) (n, a) (m, h) (n,n-k+Js) cr(f) (m,m-k+]s) \ t m , 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 * n ' a* isomorphism which causes the 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 (nk,vp) in fl-AlgC Cat) of proposition V,5 gives rise to a strictly natural adjunction ( * k \ m . v k \ m . h k , m . e k , m ) : F k whose value at an object A of A is the adjunction F; f k . m ® ' ( f i t ® A , v p ® 1) (n ~ ® A , v p ® 1) ^ k . m ® 1 k , m inD -Alg (A) . Starting with the quasi- adjunction (F £, 0 K , T) K , £ K , fk, sk) of chapter VI, we can apply the attaching procedure using this strictly natural adjunction to obtain a para-soft adjunction ( F - O f c . - r k F m'^k- l l k , m ' t k , m ' , k , m ' ° k , m • •k. J-k, m k, m n -A lg(A) We now describe this soft adjunction in detail. 373 The horizontal unit T ) k , m : 1 * U k F m . This is the strictly natural transformation given by the composition 1 U k F k k + ' k . m U v F „ K m Lemma 1 For each object A of A, T ) k „fK: A > ^ F ^ /s p/Ven by the composition o-(m,k,m) A „ ® k , m A A • ^ k , m A U . F ^ A _ Proof: T| k (mA is given by the composition o-(k,Js,Js) < \ , k ® A 0 k , k A U k F k A U k < P k \ mA k m Taking the horizontal composition of this 1-cell with the universal cone v k F ; A ^ k F m A ^ k F m A V k F m A U F I A m gives the 2-cell o"(k,k,k) f \ ,k® A X^k® 1 "t k® 1 ( 1 ; ® A id ' t k ® l fk m ® 1 k, m • * n m ® A 374 0~(k+m, k+m) 0"(m,m) where k+s=m. The morphism y k+s : (k+m, k+m) > (m,m) of f ) m can be pictured by the following diagram. This is the same as "u k v€ k (m, k,m) : (k+m,k+m) > (m, m) . The lemma follows since 375 cr(m,Js,m) - v v A • f l k r m ® A X € k ® 1 ' u k ® 1 n ; ® A ' t k ® 1 n m ® A 0~(k+m, k + m ) A J[c3-(VUk€k(m,Js,m) ) O m ® A 0"(m,m) • The horizontal counit £ k^ m: F m 0 k > 1. This is the para-natural transformation given by the composition m K V k . m U k F k U k For a commutative monad ( B , p ) , £ k m ( B , p ) : F m O k ( B ,p) » ( B ,p) is the strict morphism of commutative monads given by ~ . "k.m® 1 ~ . P k n ; ® e k * n k ® B k » B mA To complete the description of £ k f m as a para-natural transformation, we need to specify the 2-cell £ k , m ( B , p ) F m U k ( B , p ) ( B , p ) F ; u k(h,oO (h, oO WB'.p') (B'.p') 376 where ( h,oc): (B ,p) > ( B ' ,p') is a morphism of commutative monads. Ej^niCh.oc) is the 2-cell in D-Alg(A) given the 2-cell n;® B K > n;® B K • B 1® h, i d n ; ® B ' K I® h. nk® P'v in A, where ex k is the 2-cell of lemma VI, 14. The vertical u n i t r k > m : 1 » 0 k e k f m ° T| k f m0 k = ftk/m . This is the modification given by kvk Uk*k , u k u k F ; u k Uk^k.mUk UkFk^k Uk £k Lemma 2 For a commutative monad (b ,p), fkm(b ,p) is given by the 2-cell JK,. t k,m (See lemma V,16.) Proof: First consider the composite 1-cell ftkf m ( B ,p): U k ( B ,p) > U k ( B ,p) which gives the codomain of r k ( m ( B ,p). Taking the horizontal composition of this 1-cell with the universal tk-algebra B O k (B , p ) = B gives 0"(k,k,Js) C\Z ® B\ 'u k®1 ^ k k n k k ® B k x v€k®i K n , ® 1 n k ®s k id ' t k ® 1 id f l v ® B $k(m+k,k+Js) $k(m, Is) 378 The morphism (Jk+s : (m+k, k+£) > (m, Js.) of H k can be pictured by the following diagram. m+k-1 Thus we see that $ k( Mk+s) is This shows that Q k f m ( B ,p): 0 k( B ,p) * O k(B,p)is t k , m : B k > Bk. The horizontal composition of the 2-cell fkf m ( B ,p) with u k: B k > B is cr(k,Js,Js) ^ n k,K® gk' n k ® B k t ^ m ® i n k ® B } Lk.m" 379 The vertical counit s k r m : 6 k > m F k ° F k T ] k j m » 1. This is the modification given by 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 = f k , m c k u k ( m : n m • D m and = Foranobject (n,aj of f l m , e k m(n,a.) : (n+s,n-k+m) > (n,a.) is the morphism of f l m depicted as follows. It is perhaps instructive to check directly that (F ~,0k, T) k ? m, E k ( m , r k f m , 8 k f m) is a para-soft adjunction. For a commutative monad (B ,p), the composite 2-cell F;Ok(B,P) (B, p) is the 2-cell in f~)-Alg( A) given by the 2-cell 382 in A. Taking the horizontal composition of the left hand 2-cell P k( uj^ m ® ^ ( 1 ®^k,m^ v /^ n o"(n,a.) :Bk > H^® Bk, where (n,a) is an object of f l ^ . gives the 2-cell P k0"(n,fl)Ti k ( m = tn-*u k n k r m = \"-Hsuk in A(B k,B). This 2-cell can be expressed as 4>k(n+sTi) for the morphism n+sT\: (n,n-k+k.) > (n+s, n-k+Jj.) of Dk . Taking the horizontal composition of the right hand 2-cell P k ( u k ( i n ® D(ek(m® 1) withe (n,a) gives the 2-cell £ k(u k ( me k f m (n,a> ) in A( Bk,B). 383 Consider the composite morphism n+srl uk,m ek,m ( n' a ) (n,n-k+Js) • (n+s,n-k+Js) : »• (n,<a 0, a J c_ 1 >) of P l k . This morphism can be depicted as follows. The image of this morphism under $ k is the identity 2-cell on u k: B k > B. This establishes one of the modification equations for the soft adjunction. For the other modification equation, consider the 2-cell 384 A 385 0"(m,n>) while the right hand 2-cell is A • n k f m® A n;®'A H ; ® A ' t s ® 1 0"(m,ro) 0~(m+s, s+ m) 'U K® 1 rc® A I ©j: m ® i rc® A 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 ek,m (m'ID) ° (sTl+m) : (m,m) > (m,m) of Plm is the identity, as can be seen from the following diagram. 386 V A t sTi+m 6 k m(m/lD) Proposition 1 The natural monad structure determined by the soft adjunction (Fm'Uk''Hk,m'£k(m>nc,m'8k,m) o n B ,p) •= B k , where ( B ,p) is a commutative monad, is the induced monad structure ( B k , t k , m , n k , m , u k / m ) . Proof: We need to show that the "multiplication" is u k ( m . Taking the horizontal composition of T) k f mO k(B,p) U*F;f|k,mC)k(B,p) uk(B, P ) • u k F;u k (B, p) * u k F m u k F;O k (B, p) with V k(B,p):O k(B,p) >( B ,p) we obtain 0"(m,Js,m) nk,m® B k u k®1 U ^ m W B . p ) i c F ; u k ( B , P ) UkGk,m(B.P) 3^L n m ® B k | e j f B « i n m ® B , k, m nk® $v(m+s,s+Jj) Bk Pk(uk,mekfm(m,m)) B uk,mek,m <m'in) : (m+s, s+Ji) > (m,]0 can be pictured as follows. 388 B l k , m • It follows from proposition that the lifted 2-functor associated with the para-soft adjunction (Fm.Uk.;nk,m.£k,m.rk,m.8k,in)isthe 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 0m. We already know that there is a quasi-adjunction between these two 2-functors, namely (F m, 0m, T|m, £ m , r^,, s m ) . One would perhaps expect that we would arrive at exactly the same quasi-adjunction by the new route of lifting from the soft adjunction (Fm>l"lk''nk:fm,£]C,m,r]Cfm,sk(m). 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. 389 F VU • m m "k,m F m U k ^ k , m m k K, m m K ^ k , m ^ k , m = id » / "k,m F m U k • * 1 "k,m F m V k m ' k , m F ; u m r r a " k , r a F m V k . m F m U k "k,m Thenotation Q k > m = 0 k£ k / i n °T) k r m0 k, z k f i n = V k f I t l ° e k ( m has been introduced here, so that for a commutative monad (B, p) 0k(B, p) v k „ ( B . P l U m ( B ' P ) Z k , m < B . P ) V k m ^ . P ) ftk,m(B-P) UJB, p) is the universal t k r m-algebra l k , m For a commutative monad ( B ,p) , a k m ( B ,p) is the 2-cell in fl-Alg( A) given by the 2-cell 1 ® u nm®v k,m nm®sk I v n;«s, nj® B k g k , m ® 1 nm ® B m K m ® i n m®B r k,m k,m n k ®B k in A and b k m ( B ,p) is the 2-cell in D-Alg( A) given by the 2-cell 1 ® *v m u t „ k,m K , m n m ®e m l i ® ? k , n nm®B, n k ®e k -1® u k, m in A. Consider the two 2-cells obtained by taking the horizontal composition of Ua k ( m( B ,p) and U b k m ( B , p ) with cr(n,a) :B m > f l m ® B m where (n,a) is an object of H m . U a k m ( B , P ) ocj(n,a) is 9k.m®1 0"(n,a) nm ® * m l e k > m ® i n;®B „ k,n\ K , n \ H v ® B k ^ uk 'k,m $ v (n+s,n-k+k) *k ]UkK , m e i U < n ^ > ) B $ k ( n ' < a 0 ak-l» 391 B ta k-k B jn-k+s using the notation of chapter VI, where h = <ak-k, . . . ., am_1-k>. u bk,m( B.P) °o-(n,a) is where b_ = <ak-k, ,am_1-k>. By arguments similar to those used to establish proposition VI,5 we have 393 Proposition 2 u(n, fe) um t n + m u V " V - t ^ U . m ^ m in k,m t n _ k Yt t n 4 mu « tn_kum-« t n" mu m /s a sp//f forfc, spit by ^(n,fe) 1 u m " A um where b_ = <ak-k, .. . ., am_1-k>. • Let m :n„ > A( Bm,B) be the functor corresponding to U k,m® U k,m „ Pk n m ® B m ^ n k ® B k * B Thus ¥ k m is the composition _ k,m _ T k „ k,m n m • D ; *• A(B k,B) *• A (B m, B ) _ We define a functor $ k > m : Dm • A( Bm,B) by a slight modification of the definition of <$m given in chapter VI. $ K rm has the same value as $ m on objects and on all generating morphisms of fl m except those of type C2 and C3. For a generating morphism | = h+u+e: (n,aj > (n-1,a.') of flm,where h+e+2=n and either h=a^ and a.' = < a 0, . . . , a ifai+i~lf • • • > a m - l - 1 > o r h+l^ai and a! = < a 0, ... j a i - ^ a j - l , . . .,a m _ x - l >, we let$ k ( m(?)be the 2-cell 394 i<3> l , m e + l + i - m t1 ( 1 , e + l + i - m ) X where j = X (k, s) ( i ) e + l + i - m i+s if i<k, i-k ifi>k. t h - i m is a functor by essentially the same argument as the one given in chapter VI to show that $ k is a functor. Proposition 3 V k , n r V m >*k,m 9'venby Y k , m ( n , a ) « Y k , ( n , a ) = t«-"lfkfni • X("-^b>u n where b_ = <ak-k, .. . ., am_1-k>, is a natural transformation. Proof: It suffices to show that the diagram %,m(n,a) ^ k , m ( n ' 3 ) * k . m ( ^ i , m ( n ' , a ' ) ; > K*W'*') commutes for every generating morphism of D m . We do this only for generating morphisms of types SI and 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 and t h - i X t e + i _ k u m if i<k, t h " k X t e u m ifi>k Km(D = t ^ X t ^ i - X Hence *v.,m<n,a.) • *k.m<D = " k , / ^ " - ^ 1 ^ • *k,m(T>. whereb = <a J c-k, . .. ., a ^ - k ^ and i , J ' ^ , r a ( n ( s ) = • t ^ x , ™ • X (""k^> u„ 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 (n-k<22>, 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 rk,m(n,a.) •ikim(J) = * k, m(|;«Y k f m(n,fl). Type:C2 £ = h+p+e: (n,a) > (n-1,a') where h+e+2=n,ai=h and A' = < a c • • •' a i ' a i + l ~ l ' a k - l ~ ^ * ^e+l+i-k B 4e+l+i-k ( N o t e t h a t u ^ > 1 ( k o U k m = u<^> l f m.) Ifi>k, i k f m (D - th-kptetv On the other hand, $ k m ( f ) is ^e+l+i-m B • B +e+l+i-m where j = X< k' s>(i) = \ i+s ifi<k, [ i-k ifiSk. Suppose 12*. Then V k f m(n-l fa') o ¥ k f i n(f) is j n - m - 1 where ti = <ak-k, . . . ., a-^ -k, a i + 1 - l - k , . . . .,a m_ 1-l-k>. The relation: X<n-k-l,b') (h-k+TT+e) = (n-k-m+i-l+M+m-i-1) (h-i+X < 1' e + 1 + 2 i _ m _ k>+m-i)'X <n~*>h) holds in f l , and is demonstrated pictorially as follows. 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 - l c - l , b ' ) U m . t h - l c M t e u ] ^e+l+i-m ^h-i The left hand portion of this diagram is 402 by lemma V.12. This shows that Y k f m ( n - l , a ' ) • ¥k,m(T) - $k,m(D • * k, m(n,a.) for the case i > k . Now suppose that i<k. In this case Y k / m(n-l,a.') o m ( 5) is ^e+l+i-k while $ K F I N<S)«Y k, m<n ,a) is •e+l+i-k B *• B ^(1,e+l+i-k) 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. •h-i •* B (Xtn-k-l.b'J+i) ( h - i + X ( 1 ' e + 1 + i -405 n - k - 1 Note that the condition a i + 1-a iS2 is implicit in the description of 5. This implies that afc-a^k-i+l for i<k, so h-i<a k-k. • Let p k > m : f l m ® Bm > B be the 1-cell corresponding to the functor $ k r m : n m » A( Bm,B) and let P k , m : P k ( u k f m ® u k , m ) * Pk, m be the 2-cell corresponding to the natural transformation A. A. *k,nr V m * $ k, m . Thus for each object (n,a) o f f l m , B. ( T ( n , a ) n „ u k , m ® u k , m _ £ Pk n ; ® B m n k ® B k > B J k , m ¥ k , m ( n , a ) $ k , n > ' a > 406 ^n-m , where h = <ak-k, .... ,am_i-k>. Pk,m :(rim® B m . V P ® 1 ) * (B ,p) is a strict morphism of commutative monads and p k m i s a 2-cell between strict morphisms of commutative monads. This follows using arguments similar to those used to establish the analogous results for p k and p k in chapter VI. Indeed K V k,m k,m k,m ' £ » » ^ k , m P k ( U k . m ® t k , m U k , m ) „ P k <U k ,m® U k , m > » Pk,m P k ( u k , m ® 5 k , m ) is a coequalizer diagram in f ) -A lg ( A)( (D m ® B m , v p ® 1 ) , (B , p ) ) and, furthermore, Uie appropriate naturalil condition can be checked to see that the adjunction ( F m , O k , T | k ( m , E k f m,'k,mi*k,m^ where m>k>l, satisfies the coequalizer hypothesis for the construction of a lifted soft adjunction. We denote the resulting lifted soft adjunction by ( F m,O m , T | 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 m , T l m , E m , r ^ , 8 m ) between the same two 2-functors. The horizontal counit E k m : F m 0 m » 1. For a commutative monad ( B , p ) , E k m ( B , p ) : F m0 m( B ,p) » ( B ,p) is the strict morphism of commutative monads given by p k f m : (Pl m ® B m , v p ® 1 ) > ( B ,p) . We have a modification n k > m : E k m © F m V k m > E k m such that for a commutative monad ( B , p ) , the 2-cell 407 F ; V . (B,p) £ v m ( B , p ) - ^ - ^ F mO k(B,p) ±2 > (B.p) 1 fik,m(B,P) WB,P) in D-Alg( A) corresponds to the 2-cell in A. Let (h ,oc): (B ,p) • (B1 ,p') be a morphism of commutative monads. Then it can be verified that £ k m( h ,cx) is the 2-cell between strict morphisms of commutative monads given by the unique 2-cell t xk,m :P'k,m( 1 ® hm) * h P k , m such that oc k ( mcr (n,a.) = o c ( n - m > u m for each object (n,a.) of f l m ; that is, cr(n,a) „ P k , m B m • H i ® B m • *> B 1® h. oc k,m p' B' k,m ( t l ) n -408 The horizontal unit ^ l k , m : ' * UMFM. For an object A of A, T|K(MA:A > 0MF is the unique 1 -cell such that X m m UV Fm A V V mFmA K m m mF ™ A k,m m k m u k F m A 'Kjin k m U k^U K F ;A MF^A K k, m m UVF:A K m Th A 'k,m 'Hk,m'Tlk,mA - id k m where the second 2-cell is an QK> MF^ A-algebra. Taking the horizontal composition of Uus 2-cell with VKF^:OKF^ MJF^ gives "uk®1 cr(m,Js,iD) -A » * \ , m * * CJ(s+m, s+ ID) A l ^ n ( n w i D ) ) nM®A (T(mf m) From the proof of proposition V.18 we see that T)K( ^ •. A > UMF^A CAN *As° ^ obtained by 409 using the universal cone m m UmF m A m m Zm Fm A m m m m UF;A=n ;®A Q m F m A = v t m ® 1 U F m A = f l ; ® A and the v t m ® 1-algebra obtained from the vertical composition of the 2-cell tT(e k m(m,m) ):a(s+m, s+m) > a(m,m) with the 2-cell ^k Fm A K m UF;A = f 1 m ® A Q k F m A = ~ tk ® 1 * t s ® 1 U F IA m f l ; ® A u fm A • H;®A 'uk® n m ® A o"(m,k,m) v t k ® i x® 1 n m ® A . - t s ® i -» Dm® A 0"(2m,m+m) A J[ 0-rt s vU k€ k(m,Js,m) ) f l m ® A 0"(s+m, s+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]m • A( A ,Hm ® A ) of the morphism of f) m depicted as follows. This morphism can be given more simply as u m ( X ( s ' k > +m): (2m, m+m) > (m,m). Proposition 4 For an object A of A, T | k ( m A : A -a ( m , X ( 8 ' l t ) , m ) -> UmFj^A is given by the composition m, m m m host Taking the horizontal composition of this 1-cell with VmF m A m m UF^A m U m F ; A m m m m VmF m A m m ^ m F m A U F I A g i v e s "u m® rj-(m,X(8'lc>,II!) A A • n ® A m, m Dr® A ' t m ® i 0 ; ® A a(2m,m+rri) 0" (m, m) Since vu m v€ m(m, X <S'K> ,m) = p m( X <s'*>+m), the result foUows. 412 The vertical unit r ^ : ! » ^J-},,m0\,n^ Proposition 5 f k r m is the identity modification. Pioof: For a commutative monad (B ,p), rj^m( B ,p) is constructed from the 2-cell (0 From the proof of lemma 1, we see that the horizontal composition of the 1 -cell Um£)c,m(B,p)°Tlk(mOm(B,p)with is 0~(k+m,k+m) Thus O mE k, m(B,p)°Tl k f mO m(B,p)= u k ( [ n:B m > Bk. Taking the horizontal composition of the 2-cell 0 m n k , m ( B ,p) °T] k f mU m( B ,p) with V k f i n(B,p):O k(B,p) * (B,p) gives P k K , m ® u : Bm > n k , m ® B m • H m ® B m | P k, m Pk,r PkK,m®"k,m> 0"(m,m) n m ® B m | p k > m B Pk,r Lk,m Thus we see that the 2-cell (i) is k,m 1 1 id. 415 This now gives Um(B,p)- U m(B , p V 0V(B,p) IKnAp) & \ / u m e k f m ( B , P ) To prove the proposition it suffices to show that . , ^kfn0N(B. P) „ „ D m e k r m ( B , P) u m ( B , P ) • UBF;UB(B.P) = id Um(B,p) is the identity 1-cell. Taking the horizontal composition of this 1-cell with B we obtain $ktm(2m,m+m) B m t^m(M m a ( 8 ' k ) +™>) B 4 1 7 The vertical counit 8 k ) i n: £ k , m F m ° F m T) k f, -> 1. Lemma 6 For each object A of A , the composite 1-cell *A m A m £)c,mFmA FIUTrA • F" A isgivenby cm®1:Hm®A >nm®A. Proof: Using the methods given in chapter VI, it is straightforward to verify that this 1-cell is obtained by tensoring the 1-cell f l ; X 0 - ( m , X ( s ' k ) , m ) n m *n m , m n: with A, where q k , m i s the functor given by p k m for the case (B ,p) = ( , v p ) . It is easy to see that this functor has the same values as those of c m on all generating morphisms of Dm except possibly those of type C2andC3. The value of the above functor at a morphism g = h+u+e: (n,aj » (n-1, a.') ofPl mof type C2, where h+e+2=n and h=ai and a' = < a 0, . . . / a i f a i + 1 - l , . . . ,3,^-1 > (or of type C3 with h+l=ai and a.' = < a 0, . . ., a i _ i , a.^-1, . . . , a ^ - l >)is the value at (m, X <s>k) ,m) ,of the natural transformation 1 'm ^e+l+i-m n: n m , m vu<^> n: '•^ (^ e+l+i-m) -^ e+l+i-m n: ,h-i n: where j = X <k's> (i ) . Since vu < :' > 1 ( m (m, X * s ' k> ,m) = (m, i,m), we obtain the same value as that given by • 418 Proposition 7 EEQQI: S k , m ~ S r r r For an object A of A, S k ( i s obtained from a coequalizer diagram involving two 2-cells whose vertical composition with s k r „A coincide. Then S k ^ fits into the commutative triangle n. mF;A°F;f|k mA k,m m m 'K,m Jc, m 1 By similar considerations to those made for the construction of S k in chapter VI, it suffices to describe S k r mE for the case A = Cat, A - E, and then obtain the general description of S k r „A by tensoring with A. For an object (n,aj of Plm, the natural transformation n nv TH where h - <a k-k, . am_1-k>, evaluated at (m, X<s'K*,m) is the morphism ^(n,b) + r n : (n,n-m+m) • (n+s,n-k+m) of flm. Then we have sk(JI(n,a.) = S k i Jl (n,a) (Ti ( n f b )+m) = ek,m<n'a) Cl^fe) 4™) = 6m(n,a), as can be seen from the following diagram. 419 420 Summary of the constructions in chapters VI and VII. Form>l,the quasi-adjunction (F m,0 m,'T) m >£ m,r m > 8 i n ) is obtained from the original quasi-adjunction (T) ,£,id,id) by attaching and lifting according to the following scheme. m m m m (T) , e, id, id) m m m m 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 h v ) v^k,m' k,m'nk,m'Bk,m ' y t ( 5 ) _ I. r V*k> C^nV £ X 8 ) m' k,m> k,m' k,m ' (<P k,V k ,h k ,e k ) ^k,m' k^,m> 'k,m'*k,m ^ (6) ^k,m'Vk,m'hk,m'ek,m ^ •> u. 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"). The right hand quasi-adjunctions in the last two diagrams, namely (F m, 0m, T|m, £ m , r m,8 m) and ( F m , O m , T | k ^ , £ ^ , ^ , 8 ^ J , C ^ \ , m ^ k , m differ from T] m and£ m in that they each contain a "twisting" which depends on k. However, in forming the compositions 0 ^ , Q F ; f j » i » „ 0 m m m m m and FVT1 E F v pv »" ' * . m , p v Q p v k > m "> t p . m m m m m these twistings "cancel out" so that these composite para-natural transformations coincide with "Om 0 £ » ' m m « m m u m • u m F ; u m • u m m m m m m a n d F'Tl £ F v F v 5L> F^0 — * F v m m m m m respectively. Then, for each k, the vertical unit m and counit s K > m coincide with and s m, and hence are independent of k. 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 |
AggregatedSourceRepository | 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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080429/manifest