Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

May 14, 2012

Postulated Colimits and Absolute Colimits

Posted by Mike Shulman

So there’s this thing invented by Anders Kock called a postulated colimit. It seems like I’ve read his note about them numerous times without really understanding it. I felt like there ought to be some relationship with my theory of exact completions, but I didn’t nail it down precisely in time for the posting of that preprint.

Now, however, I think I finally have a grasp on postulated colimits. They do turn out to be nicely related to exact completions, but to find out how, you’ll have to wait for me to update the exact completions paper (or figure it out yourself). Today, I just want to tell you what postulated colimits are, and talk about how they’re related to something else I like: absolute colimits.

An absolute colimit is a colimit that’s preserved by any functor whatsoever. The term is used in two slightly different ways, which can be confusing if you don’t watch out for it.

On the one hand, a particular colimit in a particular category CC is absolute if it is preserved by any functor with domain CC. On the other hand, if VV is a nice category to enrich over, and WW is a weight for colimits in VV-categories, then WW is absolute if all WW-weighted colimits in all VV-categories are preserved by all VV-functors.

There is obviously a close relationship between the two meanings; the subtlest part is probably that an ordinary colimit can be preserved by all VV-functors without being preserved by all unenriched functors. For instance, initial objects are never absolute in the first, unenriched, sense — but the weight for initial objects is an absolute weight when V=V= pointed sets or abelian groups.

In this post I’m interested in the first meaning of absolute colimit; no enrichments today.

I would guess that I’m fairly typical in that my first exposure to absolute colimits was through Beck’s monadicity theorem, in which one uses split coequalizers, and remarks that they are a special sort of absolute coequalizer. An obvious question to ask after you first meet these notions is “are there absolute coequalizers that aren’t split?” If you’ve never thought about this question, then I encourage you to go away and work on it for a little while. Go on, I’ll wait.

Back? So you might have realized that there is a very trivial sort of absolute coequalizer that is not split: if f:ABf\colon A\to B is a morphism that is not a split epi, then 1 B1_B is a coequalizer of ff and ff, which is not split. But there can also be other more interesting absolute coequalizers that are not split.

If you’re a seasoned category theorist who automatically reaches for the Yoneda lemma, then you might also have realized that there’s a very clever way to characterize all absolute coequalizers, and which is a generalization of the notion of split coequalizer. I believe this is originally a result of Bob Paré from 1969. The key is this: suppose we have an absolute coequalizer diagram Xf 1f 0YeZ. X\; \underoverset{f_1}{f_0}{\rightrightarrows}\; Y \overset{e}{\to} Z. Then this coequalizer must, in particular, be preserved by the representable functor hom(Z,)hom(Z,-). Therefore, we have another coequalizer diagram hom(Z,X)f 1f 0hom(Z,Y)ehom(Z,Z) hom(Z,X)\; \underoverset{f_1\circ -}{f_0\circ -}{\rightrightarrows}\; hom(Z,Y) \overset{e\circ -}{\to} hom(Z,Z) But this is a coequalizer in SetSet, and we know what coequalizers in SetSet look like. In particular, coequalizers in SetSet are surjective, and so (e):hom(Z,Y)hom(Z,Z)(e\circ -)\colon hom(Z,Y) \to hom(Z,Z) must be surjective. Thus, in even more particular, there must be something in hom(Z,Y)hom(Z,Y) which maps onto 1 Zhom(Z,Z)1_Z \in hom(Z,Z). That just says that ee is split epic (just as it must be in a split coequalizer).

Now our coequalizer diagram must also be preserved by hom(Y,)hom(Y,-), and from that and our knowledge of coequalizers in SetSet, we can extract a generalization of the rest of the split coequalizer condition. See absolute coequalizer for details.

It turns out that this technique works in arbitrary generality. In fact, by abstract nonsense, a colimit is absolute if and only if it is preserved by the Yoneda embedding C[C op,Set]C\to [C^{op},Set]. And by looking at presenvation by particular hom-functors, we can extract a characterization of general absolute colimits. Bob Paré did this in 1971.

Specifically, let μ:FΔA\mu \colon F \to \Delta A be a cocone under a functor F:ICF\colon I\to C. Then the following are equivalent:

  • μ\mu is an absolute colimiting cocone.

  • μ\mu is a colimiting cocone and is preserved by the Yoneda embedding C[C op,Set]C\to [C^{op},Set].

  • There exists i 0Ii_0\in I and d 0:AF(i 0)d_0\colon A\to F(i_0) such that

    1. For every iIi\in I, d 0μ id_0 \circ \mu_i and 1 F(i)1_{F(i)} are in the same connected component of the comma category (F(i)/F)(F(i) / F).
    2. μ i 0d 0=1 A\mu_{i_0} \circ d_0 = 1_{A}.

In particular, there exists an i 0i_0 such that μ i 0\mu_{i_0} is split epic, generalizing our above observation that absolute coequalizers are split epis. The rest of the characterization is likewise a generalization of the part of the characterization of absolute coequalizers that I didn’t mention.

So far, so good. Now what is a postulated colimit? Anders Kock introduces the notion as follows:

To say that a diagram

RbaXqQ R \underoverset{b}{a}{\rightrightarrows} X \xrightarrow{q} Q

in the category of sets is a coequalizer may be expressed in elementary terms by saying that qa=qbq \circ a = q \circ b, and that the following two assertions hold

(1.1) qq is surjective

(1.2) for any xx and yy in XX with q(x)=q(y)q(x) = q(y), there exists a finite chain z 1,,z mz_1, \dots, z_m of elements of RR with x=a(z 1)x = a(z_1), b(z 1)=a(z 2)b(z_1) = a(z_2), … ,b(z m)=yb(z_m) = y.

These assertions can be interpreted in any category where sheaf semantics is available; this means in any site…. If they hold for a given diagram in the site, we shall say that the diagram is a postulated coequalizer.

This already looks a bit familiar; those two characterizing facts about coequalizers in SetSet are exactly the same properties that we used, after applying some representable functors, in order to characterize absolute coequalizers. But then Kock goes in a seemingly different direction: he takes these two statements and interprets them in the internal logic of a category.

Recall (if you knew it) that the internal logic of a category CC is a way of “interpreting” or “compiling” mathematical statements which look like they are talking about sets into statements which talk about objects of CC instead. For instance, given a function q:XQq\colon X\to Q between two sets, the statement “for all yQy\in Q, there exists an xXx\in X with q(x)=yq(x)=y” expresses the surjectivity of qq. In the internal logic of a topos, however, our function would be replaced by a morphism q:XQq\colon X\to Q between objects, and the same statement “for all yQy\in Q, there exists an xXx\in X with q(x)=yq(x)=y” would get compiled into one which turns out to express that qq is an epimorphism.

So Kock is saying that in a topos, we can take his conditions (1.1) and (1.2) and interpret them “internally”. As I said above, condition (1.1) will just become the assertion that qq is an epimorphism. Condition (1.2) will become something somewhat more mysterious. Regardless, a fork with these properties is called a postulated coequalizer — “postulated” I guess because the internal logic “postulates” that it is a colimit.

More generally, we can do something analogous for a cocone under any diagram and obtain a notion of postulated colimit. In that case the analogue of condition (1.1) will assert that the coprojections in the cocone are jointly epic.

Finally, generalizing in another direction, we have an “internal logic” in any site, which is basically just the restriction of the internal logic of its topos of sheaves. So we can define postulated colimits in any site. In that case, the analogue of condition (1.1) will assert that the coprojections of the cocone form a covering family.

Now a priori, it may not be obvious that a postulated colimit even is a colimit! We have these odd conditions about epimorphisms, but why should that imply a universal mapping property? However, Kock proves that if the site is subcanonical, then a postulated colimit is indeed a colimit.

You could say that this works because in a subcanonical site, the covering families themselves are already colimits (namely, they are universally effective-epimorphic), so that that colimit-ness can be extended to the postulated colimits which are defined in terms of the covering families. Alternatively, you could say that it works because a subcanonical site embeds fully-faithfully in its topos of sheaves, and a topos is sufficiently set-like that the “internal” characterization of colimits works there for the same reason that it does in SetSet.

This leads us to another of Kock’s characterizations of postulated colimits: a cocone in a site CC is a postulated colimit if and only if it becomes a colimit in the topos of sheaves Sh(C)Sh(C). In particular, a colimit in CC is a postulated colimit if and only if it is preserved by the sheafified Yoneda embedding CSh(C)C\to Sh(C).

Now we can draw the loop closed. Recall that a colimit in CC is absolute if and only if it is preserved by the ordinary Yoneda embedding C[C op,Set]C\to [C^{op},Set]. But every category CC can be made into a site with a “trivial topology”, for which Sh(C)[C op,Set]Sh(C) \simeq [C^{op},Set]. Therefore, a colimit is absolute if and only if it is postulated by the trivial topology. (Note that since the trivial topology is subcanonical, every postulated colimit in a trivial site is in fact a colimit.)

The especially nice thing is that when we take the definition of postulated colimit and “β\beta-reduce it” in the case of the trivial topology, we recover (as we must) Paré’s characterization of absolute colimits. The simple half of this is easy to see: in the trivial topology, the covering families are precisely those which contain a split epimorphism, so Kock’s condition (1.1) for the trivial topology reduces exactly to the part of Paré’s condition which says that some coprojection is split epi. The correspondence of the other two conditions is more tedious, but basically the same.

Let me end with the following suggestive remark. Since the notion of postulated colimit is defined entirely in terms of the topology of a site, it’s immediate that postulated colimits are preserved by any morphism of sites. And since the sheafified Yoneda embedding CSh(C)C\to Sh(C) is a morphism of sites, this property also characterizes postulated colimits.

However, this is reminiscent of the second type of absolute colimit I mentioned back at the beginning: the weights whose colimits are preserved by every enriched functor. Perhaps a topology on a category is something akin to an enrichment of it, and postulated colimits are the “absolute weights” for such an “enrichment”. Moreover, then the topos of sheaves, which is essentially a cocompletion under postulated colimits, would be the “Cauchy completion” relative to this “enrichment”. If you’ve read sections 6–8 of my exact completions paper, you may be able to guess what’s going on.

Posted at May 14, 2012 5:40 AM UTC

TrackBack URL for this Entry:

7 Comments & 2 Trackbacks

Re: Postulated colimits and absolute colimits

Jolly good! In fact I read your post last night and tried to send the following comment, but was foiled by the fact that my computer is literally falling apart — from the ethernet socket forward.

You wrote (my emphasis):

If you’re a seasoned category theorist who automatically reaches for the Yoneda lemma, then you might also have realized that there’s a very clever way to characterize all absolute coequalizers, and which is a generalization of the notion of split coequalizer.

I think of it very slightly differently, although this might be partly just a difference in how we use words.

We have this coequalizer diagram

XYZ X\; \rightrightarrows\; Y \to Z

(in a category called CC, say), which we know to be absolute. This means that the coequalizer is preserved by all functors out of CC. As a lightly seasoned category theorist, I’d immediately ask myself the following question:

What functors out of CC is it possible to even mention?

Really, the only ones I can think of are the representables C(X,)C(X, -), C(Y,)C(Y, -) and C(Z,)C(Z, -). There’s also the Yoneda embedding y:C[C op,Set]y: C \to [C^{op}, Set], but that doesn’t add anything: colimits are computed pointwise, so yy preserves our coequalizer iff the representable C(W,)C(W, -) does for each object WW of CC, and the only mentionable objects of CC are XX, YY and ZZ. (There are also functors such as the diagonal CC×CC \to C \times C, but they won’t help.)

And, as you explain, it’s only these three functors that you need to test against in order to guarantee absoluteness.

There’s a strong feeling of inevitability that pervades general category theory (as opposed to, say, topos theory). I first began to understand this when I learned the proof of — yes — the Yoneda lemma. There, you have to prove that a whole bunch of squares commute; and while those are checks that you really are obliged to do as part of the proof, there’s a sense of inevitability in doing them.

But also in the Yoneda lemma, there is inevitability in the proof strategy itself. For example, given a natural transformation α:C(X,)F\alpha: C(X, -) \to F, we have to construct an element of FXF X. How could we possibly do that? Well, α\alpha assigns to each map XYX \to Y out of XX an element of FYF Y. But the only map out of XX we can even mention is the identity 1 X1_X; and the resulting element of FXF X is indeed the one we want.

This principle of “what can we even mention?” seems to go a long way.

From this point of view, it’s unsurprising that a colimit in a category CC is absolute if and only if it is preserved by the Yoneda embedding out of CC. For the Yoneda embedding is, essentially, the only functor out of CC that it’s possible even to mention.

(There are also the representables on CC, but as mentioned above, for them to all preserve the colimit is equivalent to the Yoneda embedding preserving it. I guess I’m also neglecting the contravariant representables C(,X):CSet opC(-, X): C \to Set^{op}, but they automatically preserve colimits anyway.)

Posted by: Tom Leinster on May 15, 2012 8:44 PM | Permalink | Reply to this

Re: Postulated colimits and absolute colimits

That is also a nice way to think about it! Perhaps it’s not that different in essence, but it definitely emphasizes a nice point of view.

Posted by: Mike Shulman on May 15, 2012 9:32 PM | Permalink | Reply to this

Re: Postulated colimits and absolute colimits

Still on the theme of my previous comment, here’s a little theorem that Paré must have known ever since he proved his 1971 theorem that you quote. We talked about this in Glasgow, but I think neither of us saw the proof at the time.

Theorem   Let D:IAD\colon I \to A be a functor that has a colimit. Then the colimit is absolute if and only if it is preserved by (i) the functor A(D(i),):ASetA(D(i), -)\colon A \to Set, for each iIi \in I, and (ii) the functor A(colimD,):ASetA(colim D, -)\colon A \to Set.

“Only if” is trivial; it’s “if” we’re after.

You can derive a proof almost immediately from the proof of Paré’s theorem, but there’s also the following easy direct proof. Let BB be the full subcategory of AA consisting of the objects D(i)D(i) (iIi \in I) together with colimDcolim D. Then DD defines a functor IBI \to B; call it DD'. Note that colimDcolim D (the colimit of DD in AA) is also the colimit of DD' in BB. It is an absolute colimit of DD', since by hypothesis it is preserved by all representable functors out of BB. But now DD is the composite

IDBA I \stackrel{D'}{\to} B \hookrightarrow A

with the colimit of DD' being absolute. It follows that the colimit of DD is absolute.

Posted by: Tom Leinster on May 16, 2012 8:36 PM | Permalink | Reply to this

Re: Postulated colimits and absolute colimits

Ah, beautiful! I’ve added this to the nlab page.

Posted by: Mike Shulman on May 17, 2012 1:16 AM | Permalink | Reply to this
Read the post Superextensive sites
Weblog: The n-Category Café
Excerpt: "Superextensive sites" allow us to replace covering families by singleton covers... sometimes.
Tracked: May 21, 2012 6:19 AM

Re: Postulated colimits and absolute colimits

As I recall, one of the questions left open on the exact completions preprint was how to relate this work to Garner and Lack’s Lex Colimits paper, which is the only place I’ve seen Kock’s postulated colimits mentioned before. Not having digested the papers enough to gauge for myself, I have to ask: should we expect to see a unification of your approach with Garner/Lack?

Posted by: Tim Campion on May 28, 2012 1:56 AM | Permalink | Reply to this

Re: Postulated colimits and absolute colimits

A good question! The answer is yes, and it will appear in the new version of the exact completions paper.

For those not familiar with “lex colimits”, the idea is as follows. We let 𝒥\mathcal{J} be some class of “weights” for colimits in categories with finite limits. Intuitively, this means we consider a collection of types of colimits, whose specification may involve finite limits. For instance, “quotients of internal equivalence relations” is a valid choice, where the definition of “internal equivalence relation” requires finite limits. Now we can define a category to be “𝒥\mathcal{J}-exact” if it has finite limits, 𝒥\mathcal{J}-colimits, and these commute with each other in exactly the same ways that they do in a Grothendieck topos (or, equivalently, in the category of sets). For different values of 𝒥\mathcal{J}, we recover regular categories, exact categories, lextensive categories, pretoposes, categories with filtered colimits that commute with finite limits, etc. Among other things, Garner and Lack proved that every small category with finite limits has a free 𝒥\mathcal{J}-exact completion.

The relationship to my exact completions paper is not too surprising in outline. If 𝒥\mathcal{J} is a class of lex-weights in the sense of Garner and Lack, all of which are “κ\kappa-ary” in a suitable sense, then you can construct the “𝒥\mathcal{J}-exact completion” of a κ\kappa-ary site, as the closure of its image in its κ\kappa-ary exact completion under finite limits and 𝒥\mathcal{J}-lex-colimits. If the site CC is small with a trivial topology, then this recovers its Garner-Lack 𝒥\mathcal{J}-exact completion.

More generally, if 𝒥 1𝒥 2\mathcal{J}_1 \le \mathcal{J}_2 in the sense of Garner-Lack (that is, every 𝒥 2\mathcal{J}_2-exact category or functor is also 𝒥 1\mathcal{J}_1-exact), then any 𝒥 1\mathcal{J}_1-exact category has a 𝒥 1\mathcal{J}_1-exact topology (e.g. the extensive topology on an extensive category, or the regular topology on a regular category), and the 𝒥 2\mathcal{J}_2-exact completion of this topology is the relative 𝒥 2\mathcal{J}_2-exact completion of Garner-Lack.

One thing which one has to be careful about (and which I was insufficiently careful about in the preprint) is that “κ\kappa-arity” of 𝒥\mathcal{J} doesn’t just mean that the input data of 𝒥\mathcal{J} is κ\kappa-small, but that the “congruence it generates” is so. Thus κ\kappa-ary exactness, κ\kappa-ary regularity, and κ\kappa-ary extensivity are all κ\kappa-ary exactness notions, but (for instance) the exactness notion for reflexive coequalizers discussed in Garner-Lack, though it may appear to {1}\{1\}-ary, is actually only ω 1\omega_1-ary.

And one thing which is slightly odd is the universal property of the 𝒥\mathcal{J}-exact completion of a general κ\kappa-ary site. The universal property of the κ\kappa-ary exact completion is that it is a reflection into κ\kappa-ary exact categories, regarded as κ\kappa-ary sites with their κ\kappa-canonical topologies. So one might naively guess that the 𝒥\mathcal{J}-exact completion would be a reflection into 𝒥\mathcal{J}-exact categories with their 𝒥\mathcal{J}-exact topologies. However, this is not right; instead what we reflect into is 𝒥\mathcal{J}-exact categories with subcanonical and 𝒥\mathcal{J}-superexact topologies (i.e. containing the 𝒥\mathcal{J}-exact topology). When 𝒥\mathcal{J}-exactness is κ\kappa-ary exactness, then the 𝒥\mathcal{J}-exact topology is the κ\kappa-canonical one, so there is only one subcanonical and 𝒥\mathcal{J}-superexact topology, but in general there can be many.

(Thinking about this general notion of 𝒥\mathcal{J}-superexact topologies led me back to the old notion of “superextensive site”, hence my most recent post.)

Posted by: Mike Shulman on May 29, 2012 4:57 PM | Permalink | Reply to this

Re: Postulated colimits and absolute colimits

The final version of my exact completions paper, which discusses the relationship with postulated and lex colimits, has now appeared in the CT2011 proceedings volume of TAC.

Posted by: Mike Shulman on September 5, 2012 8:03 PM | Permalink | Reply to this
Read the post Scones, Logical Relations, and Parametricity
Weblog: The n-Category Café
Excerpt: The category-theoretic scone or "gluing construction" packages the type-theorist's method of "logical relations" to prove canonicity and parametricity properties of type theory.
Tracked: April 18, 2013 4:56 AM

Post a New Comment