Is there a good reference for the construction of colimits of categories? Here, by 'categories', I mean 1-categories; and I'm considering 1Cat as a weak 2-category. I've been playing around with this for the last week; I can construct limits without much trouble (at least if the index category is a 1-category; I assume that changing the index category to a 2-category wouldn't cause any substantial problems), but constructing colimits seems noticeably messier. It's not too bad if your index category is filtered, but in general it seems like a pain. I frequently see statements like 'nCat is expected to have all limits and colimits', so I assume that this has been verified in the case of n=1 somewhere. Also, while I'm asking, does the decategorification operation (from nCat into (n-1)Cat) commute with colimits? I was somewhat surprised to see that decategorification from 1Cat into 0Cat does commute with filtered colimits; so I'm wondering to what extent that statement generalizes. I.e. can I replace 1Cat by nCat, can I remove the word 'filtered', and for that matter can I replace colimits by limits? (I know decategorification doesn't commute with arbitrary limits of 1Cats - indeed, that's arguably where much of the fun of higher category theory comes into play - though I haven't thought too much about whether or not it commutes with filtered limits.) I have reason to hope that decategorification doesn't commute with filtered colimits of 2-categories, but no hard evidence; trying to check that seems like enough of a pain that I'm hoping somebody else has done it first. I haven't thought much about non-filtered colimits since I can't even construct them; I'd be surprised offhand if decategorification commuted with arbitrary colimits. Then again, I was surprised to see that it commuted with filtered colimits, so clearly my intuition isn't the most reliable guide in this case. David Carlton carlton@math.stanford.edu 29-Jan-2002 20:56:41 -0400,2784;000000000000-00000000
Is there a good reference for the construction of colimits of categories? Here, by 'categories', I mean 1-categories; and I'm considering 1Cat as a weak 2-category. I've been playing around with this for the last week; I can construct limits without much trouble (at least if the index category is a 1-category; I assume that changing the index category to a 2-category wouldn't cause any substantial problems), but constructing colimits seems noticeably messier. It's not too bad if your index category is filtered, but in general it seems like a pain.
The construction of quotients of 1-categories (which, together with coproducts, make up arbitrary colimits) is indeed somewhat messy: the naive quotient (equivalence classes of objects and morphisms) forms a graph with a partial composition operation that obeys the identity law but no further axioms. Over this structure, one can construct a free category (the category of paths, modulo the smallest congruence that makes the quotient map a functor), which is, then, the actual quotient category; which equivalence classes of arrows are or are not identified in the quotient category is, in the general case, hard to predict. References include M. Bednarczyk, M. Borzyszkowski, and W. Pawlowski: Generalized congruences --- epimorphisms in Cat. Theory and Applications of Categories 5 (1999), 266-280 L. Schroeder and H. Herrlich: Free adjunction of morphisms. Applied Categorical Structures 8 (2000), 595-606. Greetings, Lutz -- ----------------------------------------------------------------------------- Lutz Schroeder Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen lschrode@informatik.uni-bremen.de P.O.Box 330440, D-28334 Bremen http://www.informatik.uni-bremen.de/~lschrode ----------------------------------------------------------------------------- 29-Jan-2002 20:56:44 -0400,3194;000000000000-00000000
David Carlton asks -
Is there a good reference for the construction of colimits of categories?
If I remember correctly, Philip Higgins's little book "Notes on categories and groupoids" (Van Nostrand Reinhold 1971) is good on that kind of thing. You're right that the non-filtered colimits are distinctly messier than the limits. There are two reasons. The first is that that is the way of algebra anyway - think of colimits of monoids or groups, for instance. Universal algebra says that colimits exist for every algebraic theory, but the construction is intricate. You first make an algebra of all possible terms (expressions) and then factor out a congruence to enforce the equational laws and the cocone commutativities. The second reason is that categories are models not of an algebraic theory, but of an essentially algebraic theory (some operations - specifically here composition - are only partial, with domain of definition stipulated equationally). The techniques of universal algebra still work, by and large, but the proof is even more intricate than the 2-step process in algebra. This is because imposing equations can cause new terms to spring into existence. Steve Vickers. 30-Jan-2002 08:58:25 -0400,2955;000000000001-00000000
Steve is right about the messiness. The very first paper I am aware of on the subject used 25 pages of detailed computations to show that the amalgamated sum of two categories gotten by identifying a single object of one category with an object of the other exists. That must have been sometime in the 60s. What a mess! A good mathematician, whom I won't embarrass by identifying. Michael On Tue, 29 Jan 2002 S.J.Vickers@open.ac.uk wrote:
David Carlton asks -
Is there a good reference for the construction of colimits of categories?
If I remember correctly, Philip Higgins's little book "Notes on categories and groupoids" (Van Nostrand Reinhold 1971) is good on that kind of thing.
You're right that the non-filtered colimits are distinctly messier than the limits. There are two reasons.
The first is that that is the way of algebra anyway - think of colimits of monoids or groups, for instance. Universal algebra says that colimits exist for every algebraic theory, but the construction is intricate. You first make an algebra of all possible terms (expressions) and then factor out a congruence to enforce the equational laws and the cocone commutativities.
The second reason is that categories are models not of an algebraic theory, but of an essentially algebraic theory (some operations - specifically here composition - are only partial, with domain of definition stipulated equationally). The techniques of universal algebra still work, by and large, but the proof is even more intricate than the 2-step process in algebra. This is because imposing equations can cause new terms to spring into existence.
Steve Vickers.
30-Jan-2002 09:03:32 -0400,3062;000000000001-00000000
David Carlton asks -
Is there a good reference for the construction of colimits of categories?
If I remember correctly, Philip Higgins's little book "Notes on categories and groupoids" (Van Nostrand Reinhold 1971) is good on that kind of thing.
You're right that the non-filtered colimits are distinctly messier than
limits. There are two reasons.
The first is that that is the way of algebra anyway - think of colimits of monoids or groups, for instance. Universal algebra says that colimits exist for every algebraic theory, but the construction is intricate. You first make an algebra of all possible terms (expressions) and then factor out a congruence to enforce the equational laws and the cocone commutativities.
The second reason is that categories are models not of an algebraic
reply to r.brown@bangor.ac.uk Another paper to look up is by Philip Higgins in Mathematische Nachrichten 27 (1963) 115-132 which generalised his earlier work on algebras with a scheme of operators to partially defined operators. One way of looking at this is that a morphism f: C \to D of categories (or groupoids) may identify objects. So one thing to do is factorize it through through a universal morphism which does just that identification (compare Steve Vickers' comments). Philip's book (in fact his 1964 paper on presentations of groups) shows how you thereby get free groupoids on graphs and free products of groups from one construction. An advantage of this is you need only one normal form theorem, whereas the group theory books give two proofs. There is a paper by M.Zisman looking at the effect of this particular construction on classifying spaces of categories and groupoids. This is seen as a `change of base' construction (a favourite notion of Grothendieck) in my paper ``Homotopy theory, and change of base for groupoids and multiple groupoids'', {\em Applied categorical structures}, 4 (1996) 175-193. This also relates change of base to results in algebraic topology such as n-adic excision and Hurewicz theorems. The n-adic theorems were found via this route (n=2 is the well known relative case). In homotopy theory one would like to know what happens to a homotopy type if you change its lower dimensional part. An algebraic solution to this would also give the homotopy types of spheres, since S^n is obtained from a disc E^n by shrinking the boundary S^{n-1} to a point. So we can't expect a calculable solution overnight! In the strict multiple groupoid case some explicit calculations have been done (using crossed n-cubes of groups, Ellis-Steiner) , but all this suggests the interesting difficulty of calculating with multiple categories. On the other hand, calculating with groups is not a walk-over either, and the expectation is that some group theory results are best understood from a higher dimensional viewpoint. For colimits of topological categories and groupoids see also (with J.P.L. HARDY), ``Topological groupoids I: universal constructions'', {\em Math. Nachr.} 71 (1976) 273-286. which gets it from an adjoint functor type construction: this probably overlaps work of C. Ehresmann. Ronnie Brown ----- Original Message ----- From: <S.J.Vickers@open.ac.uk> To: <categories@mta.ca> Sent: Tuesday, January 29, 2002 2:08 PM Subject: categories: Re: colimits of categories the theory,
but of an essentially algebraic theory (some operations - specifically here composition - are only partial, with domain of definition stipulated equationally). The techniques of universal algebra still work, by and large, but the proof is even more intricate than the 2-step process in algebra. This is because imposing equations can cause new terms to spring into existence.
Steve Vickers.
30-Jan-2002 09:06:16 -0400,3084;000000000000-00000000
In a paper by M.Kelly `A unified treatment of transfinite construction for free algebras, free monoids, colimits, associated sheaves, and so on', Bull. of the Australian Math. Soc., 22 (1980), 1-85. there is a general construction of colimits in the category of algebras of a finitary monad. The category of 1-Cat is an algebra of a free category on graph monad, which is finatary so the colimits exist in 1-Cat. Informally what we have to do to construct a coequalizer in 1-Cat is the following. First we have to construct a corresponding coequalizer in graphs. Then apply free category functor to it and form another coequaliser in graphs. This process continuing. Finally we have a sequence of graphs and its colimit is our coequalizer in 1-Cat. The same argument show the existence of colimits in n-Cat (strict n-categories and strict n-functor) or weak n-Cat with strict n-functors (if you accept my definition of weak n-catgory introduced in 'Monoidal globular categories as a natural environment for the theory of weak $n$-categories', Adv. Math. 136 (1998), pp. 39-103.). If we think of n-Cat as a category of algebras over an appropriate n-operad then it contains a full subcategory of algebras such that their underlying n-graphs (n-globular sets in other terminology) are discretes in dimension n (i.e. Hom(a,b) = 0 if a /ne b and Hom(a,a)=1). This subcategory is closed under limits and so we have a left adjoint from n-Cat to this subcategory which can be considered as a decategorification functor. Therefore, it commutes with colimits. Michael Batanin. 29-Jan-2002 20:56:51 -0400,1875;000000000000-00000000
David Carlton writes about colimits of categories. Other people have answered many of his questions, but not yet:
Also, while I'm asking, does the decategorification operation (from nCat into (n-1)Cat) commute with colimits? I was somewhat surprised to see that decategorification from 1Cat into 0Cat does commute with filtered colimits; so I'm wondering to what extent that statement generalizes. I.e. can I replace 1Cat by nCat, can I remove the word 'filtered', and for that matter can I replace colimits by limits? (I know decategorification doesn't commute with arbitrary limits of 1Cats - indeed, that's arguably where much of the fun of higher category theory comes into play - though I haven't thought too much about whether or not it commutes with filtered limits.)
If by n-Cat you mean strict n-categories and strict n-functors, then here is a response to the ``colimit'' part of the question. First of all, you can't generalize from filtered colimits to arbitrary colimits, even in the case 1Cat-->0Cat. Write Cat for 1Cat and Set for 0Cat, and P:Cat-->Set for the decategorification functor, which sends a category to its set of isomorphism classes of objects. This functor P preserves filtered colimits, as you said (or see below), and clearly also preserves coproducts, but doesn't preserve the coequalizer f q A ----> B ----> C ----> g where C is the free-living isomorphism, with objects 0 and 1, and two mutually inverse non-identity arrows 0-->1 and 1-->0; where B has objects 0 and 1, and arrows freely generated by 0-->1 and 1-->0, and where q is the evident quotient; where A has two objects 0 and 1 and arrows freely generated by 0-->0 and 1-->1, and where f and g are the evident functors. Alternatively, observe that Cat is locally finitely presentable (lfp), so that if it preserved all colimits it would have a right adjoint, and prove that it does not have one. On the other hand, decategorification P:n-Cat-->(n-1)-Cat does preserve filtered colimits for any n. To see this, write n-Catg for the full subcategory of n-Cat consisting of those n-categories in which all n-cells are invertible. The inclusion I:n-Catg --> n-Cat has a right adjoint R which forgets all non-invertible n-cells. (It also has a left adjoint.) Now RI=1 and PIR=P, so that P will preserve filtered colimits if PI and R do so. But PI:n-Catg ---> (n-1)-Cat has a right adjoint D, which regards an (n-1)-category as an n-category with no non-identity n-cells. Thus PI preserves all colimits, and P will preserve filtered colimits provided R does so. If V is locally finitely presentable, then so is V-Cat [G.M.Kelly and Stephen Lack, V-Cat is locally presentable or locally bounded if V is so, Theory Appl. Cat. 8:555-575, 2001]. From the equation (n+1)-Cat=(n-Cat)-Cat and the fact that 0-Cat(=Set) is lfp, it follows by induction that n-Cat is lfp for every n. Similarly from the equation (n+1)-Catg=(n-Catg)-Cat and that fact that 1-Catg(= the category Gpd of groupoids) is lfp, it follows that n-Catg is lfp for every n. Now R:n-Cat-->n-Catg is a right adjoint functor between lfp categories, so will preserve filtered colimits if and only if its left adjoint I:n-Catg-->n-Cat preserves finitely presentable objects. For an object G of V, write 2_G for the V-category with objects 0 and 1, and homs 2_G(0,0)=2_G(1,1)=I, 2_G(1,0)=0, and 2_G(0,1)=G. By the Kelly-Lack paper, the finitely presentable objects of V-Cat are the closure under finite colimits of the V-categories of the form 2_G for G a finitely presentable object of V. It follows that I:(n+1)-Catg --> (n+1)-Cat will preserve finitely presentable objects if I:n-Catg ---> n-Cat does so. Thus it remains only to show that I:Gpd-->Cat preserves finitely presentable objects, or equivalently that R:Cat-->Gpd preserves filtered colimits. There are various ways to do this. One could use the description of filtered colimits in Cat given in the Kelly-Lack paper to show that IR preserves filtered colimits, and deduce that R does so. Alternatively one could show that the ``free-living isomorphism'' (called C above) is finitely presentable in both Gpd and Cat, and constitutes a strong generator of Gpd, and deduce that I preserves finitely presentable objects. Similarly, P:n-Cat-->(n-1)-Cat will preserve whatever limits PI preserves, and once again an inductive argument shows that PI will preserve whatever limits PI:Gpd-->Set preserves (products, for instance). Steve Lack. 30-Jan-2002 09:02:37 -0400,2558;000000000001-00000000
Thanks for all the responses to my colimits question; I greatly appreciate them, and it will take me a while to digest them. I think I should be a bit more precise as to what I'm asking for, so let me try again: First, here's what I mean by a colimit of categories: let I be a 1-category, trivially extended to a weak 2-category with only identity 2-morphisms. (Or we could even have I be an arbitrary weak 2-category; I'm not too worried about that right now, but eventually I'd like an answer.) And let F be a weak functor from I to the 2-category 1Cat (which happens to be strict, but we think of it as a weak 2-cat.) Then: I want a 1-cat colim(F) such that, for all 1-cats C, the categories Hom_1Cat(colim(F),C) and Hom_(1Cat^I)(F,diag^I(C)) are equivalent, where by diag^I(C) I mean the constant functor from I to 1Cat^I sending all objects of I to C and all morphisms to identity morphisms. So I'm not looking at the set of functors from colim(F) to C: I don't really care whether or not that's equivalent to the set of functors from F to diag^I(C). I want an equivalence of categories. I'm fairly sure that some of the responses that I got answer this question; I'll look up the references and come back if I have more questions, but I'm provisionally happy with that for now. Here's the second question: Once we've constructed this, we can ask under what conditions the sets Decat(colim(F)) and colim(Decat(F)) are naturally bijective. (I guess there's a natural map from colim(Decat) to Decat(colim).) It's true for filtered index sets; is it true for general index categories? Also, we can generalize these questions to the setting of F be a functor from I to nCat, by which I mean the weak (n+1)-category of all n-categories; then we have a functor of n-categories that we want to represent. Since the notion of "weak n-category" is a matter of some debate, I'm willing to take it for granted that such a colimit does exist. Then: In what context (e.g. for what index categories) do we expect the (n-1)-categories Decat(colim(F)) and colim(Decat(F)) to be equivalent? Or the sets Decat^n(colim(F)) and colim(Decat^n(F))? Again, a definitive answer to that last question is unlikely since it would depend on having a firm grasp of weak n-categories (and of nCat), but I'm curious what people's instincts are. For what it's worth, I can show that Decat can't be a left adjoint (in the relevant sense). If it were, its right adjoint would be a functor F from Set (a 1-category trivially extended to a 2-category) to 1Cat such that, for all categories C and sets S, the category Hom_1Cat(C, FS) is equivalent to the set Hom_Set(Decat(C),S) (thought of as a discrete category). In fact, we can't even have Hom_Set(Decat(C),S) equal Decat(Hom_1Cat(C, FS)). One way to see this is to first let C be the discrete category with two objects, which shows that the cardinality of Decat(FS) is just the cardinality of S. So we might as well assume that the objects of FS are just S and that no two objects are isomorphic. But then set C to be the category 0 -> 1; use this to select a morphism f:s->t for any s,t in S, and then to show that the composite of f:s->t and g:s->t is an isomorphism, so all objects are isomorphic after all. David Carlton carlton@math.stanford.edu 31-Jan-2002 23:01:36 -0400,969;000000000001-00000000
on 31/1/02 6:27 AM, david carlton at carlton@math.stanford.edu wrote:
For what it's worth, I can show that Decat can't be a left adjoint (in the relevant sense). If it were, its right adjoint would be a functor F from Set (a 1-category trivially extended to a 2-category) to 1Cat such that, for all categories C and sets S, the category Hom_1Cat(C, FS) is equivalent to the set Hom_Set(Decat(C),S) (thought of as a discrete category).
Sorry, when I wrote about Decat as a left adjoint I thought about n-groupoids rather than n-categories. Steve Lack has already clarified the situation. But now I understand you are asking about weak (or pseudo) colimits. They exist in 1-Cat and 2-Cat and can be expressed in terms of appropriate weighted colimits. I never saw a paper about pseudocolimits in 3-Cat (here we can use Gray-categories instead of general tricatgories). They must be expressed as weighted colimits as well, or a codescent object of a simplicial Gray-category. I'd like to have a reference if such a paper already exists. Michael Batanin.
participants (7)
-
david carlton -
Lutz Schroeder -
Michael Barr -
Michael Batanin -
Ronald Brown -
S.J.Vickers@open.ac.uk -
Steve Lack