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.

March 31, 2008

Limits and Push-Forward

Posted by Urs Schreiber

The limit and colimit of a functor can be understood as the “push-forward of the functor to a point”: the image of the functor under the right or left adjoint functor of the pullback of functors from the terminal category {pt}\{pt\}.

Is there a useful generalization of this correspondence between limits and push-forward for the case of indexed limits?

Here is supposed to be a diagram illustrating the relation between limits and push-forward to a point.

I am concerned with push-forward of (nn-)functors along projections onto a factor of a cartesian product p:hom(Σ,X)×ΣΣ. p : hom(\Sigma, X) \times \Sigma \to \Sigma \,. In a cartesian closed context, I should be able to use the hom-adjunction to reduce this to a push-forward to the point, i.e. just to a limit.

But I keep wondering if and how indexed limits, ends and coends should make an appearance here.

Posted at March 31, 2008 8:43 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1647

36 Comments & 0 Trackbacks

Re: Limits and Push-Forward

Isn’t that similar to zeta function regularization method? Every push forwared would be equivalent to a term of a Dirichlet series.

Posted by: Daniel de Franša MTd2 on April 1, 2008 12:51 AM | Permalink | Reply to this

Re: Limits and Push-Forward

`Push forward of functors’ being Kan extension…

Posted by: David Roberts on April 1, 2008 1:29 AM | Permalink | Reply to this

Re: Limits and Push-Forward

Yes, sure. But when I saw Figure 1 above,I thought of using the Rosetta stone idea, and then I asked myself what kind of Physics Process and System is that related to?

I saw limits, something ordered and infinite, aestheticaly appealing to me like a sum, weight integrals. All of this with a an ordered converging sum, related to 2 extreme terms in different places(q and Lim_a F) . I don’t know if that makes sense at all.

Could someone give us a Rosetta equivalence in physics, using figure 1? Sorry, but I was just curious… :(

Posted by: Daniel de Franša MTd2 on April 1, 2008 1:27 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Daniel wrote:

Isn’t that similar to zeta function regularization method?

[…]

I saw limits, something ordered and infinite, aestheticaly appealing to me like a sum, weight integrals.

It’ll be a long way (if any at all) from here to QFT path integral regulization – but, indeed, when nobody listens, I admit that this is the long-term aim:

a proposal for a formalization of Freed’s observation that the “path integral” in quantum physics should be just the top-dimension version of a general procedure of taking sections aka pushing forward to a point is this:

Set V=(ωCat, Gray)V = (\omega Cat, \otimes_{Gray}). Then

target space is a VV-category XX

parameter space is a VV-category Σ\Sigma

the background field is a VV-functor :Xphas. \nabla : X \to phas \,.

Quantization of that (Freed’s extended path integral interpretation, which unifies and extends the concepts of “forming the space of states by taking sections” and “forming the propagation operator by means of the path sum”) is supposed to be the result of

- first forming the transgression

ev *:hom(Σ,X)×ΣevXphas ev^* \nabla : hom(\Sigma,X)\times\Sigma \stackrel{ev}{\to} X \stackrel{\nabla}{\to} phas

of the background field to configuration space hom(Σ,X)hom(\Sigma,X)

- and then integrating over all “paths”, i.e. all objects in hom(Σ,X)hom(\Sigma,X) by pushing forward along the projection hom(Σ,X)×ΣΣ hom(\Sigma,X)\times \Sigma \to \Sigma.

This yields (if it exists) another VV-functor hom(Σ,X)ev *:Σphas \int_{hom(\Sigma,X)} ev^* \nabla : \Sigma \to phas and this is suppose to:

- assign to objects in Σ\Sigma the space of states of the theory

- assign to 1-morphisms the “propagator” along that 1-morphism between these spaces of states

and so on. Think of Σ\Sigma as points and paths on the real line to get the quantum mechanical intuition.

There are various toy example consistency checks showing that this formalization does reproduce what one wants to see:

the ordinary space of states of a quantum particle is easily reproduced this way #.

More remarkably, the path integrals for finite group Chern-Simons theory # (known as Dijkgraaf-Witten theory) as well as # for finite 2-group Chern-Simons theory (known as the Yetter model) are reproduced this way.

This is the evidence that convinced me that the categorical push-forwad should indeed be the right abstract way to think about the path integral: if Chern-Simons comes out right, then we are bound to obtain its boundary CFT, too, and that’s all one can ask for.

I looked at more consistency checks of simple kind ## which seem to further support this, though at times the arguments are less than waterproof, in part due to some fuzziness on the technical details of the setup one should look at.

Therefore currently I am trying to approach the problem from two sides:

abstractnonsenseformalizeproblemproblemworkoutexamplesconcreteapplications abstract nonsense \stackrel{formalize problem}{\to} problem \stackrel{work out examples}{\leftarrow} concrete applications

hoping to converge in the middle.

As you will have noticed, most of the toy examples I looked at involve finite categories. That’s how toy examples go. Ultiumately we dream about being able to handle real-world setups as they appear in cutting-edge physics. While I have close to no real results on this at the moment, I do have one curious observation:

the problems and their possible solutions that one faces when computing colimits (or “category cardinality”) for non-finite categories are exactly (see also this) of the same kind of flavor as those of renormalization in QFT #.

While that does not prove anything at this point, it is somewhat suggestive.

Posted by: Urs Schreiber on April 1, 2008 3:19 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Sorry, I mean, Figure 1, the triangle at the low left side.

Posted by: Daniel de Franša MTd2 on April 1, 2008 1:30 PM | Permalink | Reply to this

Re: Limits and Push-Forward

There is certainly a neat little story connecting this construction with (co)ends and indexed/weighted (co)limits.

I’ll talk about colimits; of course you can dualise everything if you care about limits instead. As David Roberts just mentioned, what you’re saying is that the colimit of your FF is the left Kan extension of F along the functor p:A{pt}p: A\to\{pt\}.

If we take BB to be (sufficiently) cocomplete, we can use the coend formula for left Kan extension: in general, the left Kan extension of F:ABF:\mathbf{A}\to\mathbf{B} along K:AXK:\mathbf{A}\to\mathbf{X} is

(1)(Lan KF)(X)= AAX(KA,X)FA (Lan_{K}F)(X) = \int^{A\in\mathbf{A}} \mathbf{X}(KA,X)\otimes FA

Now, the weighted colimit of F:ABF:\mathbf{A}\to\mathbf{B} with weight W:A opSetW: \mathbf{A}^{op}\to Set is

(2)WF= AAWAFA. W\star F = \int^{A\in\mathbf{A}}WA\otimes FA.

So for each object XXX\in\mathbf{X}, the object (Lan KF)(X)B(Lan_{K}F)(X)\in\mathbf{B} is the weighted colimit

(3)(Lan KF)(X)=X(K,X)F. (Lan_{K}F)(X) = \mathbf{X}(K-,X)\star F.

Thus in some sense the left Kan extension is a special case of the general notion of weighted colimit (and dually the right Kan extension is a special case of weighted limit).

Posted by: Robin Houston on April 1, 2008 12:18 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Thanks David and Robin!

I am feeling somewhat stupid for not having realized this relation to coends (and not remembered it from the standard textbooks) – but better late than never.

I was reading Kelly’s book yesterday (without making it to page 64 – obviously :-/ – but still need to acquaint myself better with coends.

Here is a toy example that I should sit down and apply the coend formulation of the push-forward to:

Take the enrichment category to be the 1-category of categories, V=CatV = Cat so that a VV-category is a strict 2-category.

Let XX be the 2-category

X={xyx} X = \{ x \to y \leftarrow x' \} (so that happens to be just a 1-category).

Let phasphas be the 2-category phas:=BFinSet phas := B FinSet i.e the one-object 2-category whose Hom-category is FinSetFinSet and where composition is the cartesian product on sets.

Let Σ\Sigma be just the interval Σ:={ab}. \Sigma := \{a \to b\} \,.

Let F:Xphas F : X \to phas be a VV-functor (i.e. strict 2-functor) and write ev *F:hom(Σ,X)×ΣevXFphas. ev^* F : hom(\Sigma,X)\times \Sigma \stackrel{ev}{\to} X \stackrel{F}{\to} phas \,.

I am after the pushforward of ev *Fev^* F down to Σ\Sigma along the canonical projection hom(Σ,X)×ΣΣ hom(\Sigma,X)\times \Sigma \to \Sigma and its expression in terms of (co)ends.

Such will be the kind of exercise for my train ride tonight.

Posted by: Urs Schreiber on April 1, 2008 1:43 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Quick question: when you say “push-forward”, does that mean the same as “right Kan extension”?

Posted by: Robin on April 1, 2008 1:51 PM | Permalink | Reply to this

Re: Limits and Push-Forward

when you say “push-forward”, does that mean the same as “right Kan extension”?

Right, I should have been more precise. I was being vague about this since I used to be looking at a context where limits and colimits coincided.

But what I really need is colimits.

Posted by: Urs Schreiber on April 1, 2008 2:00 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Okay, left Kan extension then?

The general answer doesn’t depend on the precise choices for Σ\Sigma and XX; it’s the functor that takes sΣs\in\Sigma to the colimit, over f[Σ,X]f\in[\Sigma,X], of F(fs)F(fs). We might write it as

(1) f:ΣXF(f). \int^{f:\Sigma\to X} F(f-).

For your choices of XX and Σ\Sigma, the category of functors ΣX\Sigma\to X has a terminal object (the constant functor at yy), so the whole thing is just the constant functor at F(y)F(y).

Posted by: Robin on April 1, 2008 2:27 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Robin,

thanks a whole lot! I have to run now, but will think about what you just said.

I need to play around with some variations of that simple example. Notably what happens when we use for XX instead something like X={xyx}X = \{x \stackrel{\rightarrow}{\leftarrow} y \stackrel{\rightarrow}{\leftarrow} x'\} (is that as easy to see??).

I tried to strip down the example to make it more tractable, but in a more elaborate version I had something like phas=SetModphas = Set-Mod and took FF to assign the Set-module Set to each object and right multiplication by a set to each morphism. Setting phas=BSetphas = B Set above was supposed to capture that restriction, but maybe that trivialized the example too much.

Thanks again for all your feedback! I’ll have to jump on a train now, but with Kelly’s book in my pocket. Hope to get back to you in a state of less naïvety afterwards…

Posted by: Urs Schreiber on April 1, 2008 3:38 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Nothing I said depends on what you take phas to be: it turns out trivial just because XX has a terminal object.

Posted by: Robin on April 1, 2008 3:58 PM | Permalink | Reply to this

Re: Limits and Push-Forward

just because XX has a terminal object.

Right, actually I gave the wrong XX, I should be looking at

X={xyx} X = \{ x \leftarrow y \rightarrow x'\}

as in the discussion here.

The Leinster measures of categories of this and its iterated forms

.

reproduces the weighting appearing in the exponentiated lattice Laplace operator. But in those previous discussions I did not properly compute the Kan extension we are atalking about now, but instead looked at the pul-push of certain sections through certain diagrams

.

I am thinking it should amount to the same thing, though, but am getting a bit confused about this. Therefore my questions here.

I still need to unconfuse myself further…

Posted by: Urs Schreiber on April 2, 2008 6:19 AM | Permalink | Reply to this

Re: Limits and Push-Forward

By the way, what is the minimal condition on a category such that limits and colimits, if both exist, coincide, as for FinVectFinVect? Is there a nice simple characterization?

Is it existence of a 0-object?

Posted by: Urs Schreiber on April 5, 2008 11:56 AM | Permalink | Reply to this

Re: Limits and Push-Forward

Urs, could you clarify what you mean by limits and colimits coinciding? For example, in FinVectFinVect the limit of a diagram consisting of two parallel arrows (equalizer) does not coincide with the colimit of that diagram (coequalizer).

There is (as I’m sure you realize) a notion of category with zero object and biproducts, where the initial and terminal coincide and finite products and finite coproducts “coincide”. I think one has to exercise some care in saying what this last condition means. If AA and BB are objects in a category with finite products and finite coproducts, then a map

A+BA×BA + B \to A \times B

determines (and is determined by) four maps (from AA to AA, AA to BB, etc.) which can be thought of as entries in a (2×2)(2 \times 2)-matrix. If the category has a zero object as well, then there are canonical candidates for such maps (identity maps on-diagonal, zero maps off-diagonal), so that the matrix is the “identity matrix”. Then the relevant condition for biproducts is that the identity matrix map A+BA×BA + B \to A \times B is an isomorphism. Just having a zero object is not enough for that to happen; the category of pointed sets (where the zero object consists of just a basepoint) is an example where the condition fails.

When the condition holds, then there is a canonical way to enrich the category in the category of commutative monoids (reminiscent of additive categories, except they’re CMonCMon-enriched, not AbAb-enriched). The sum f+gf + g of two maps f,g:ABf, g: A \to B is given by the evident composite

AdiagA×Af×gB×BB+BcodiagB,A \stackrel{diag}{\to} A \times A \stackrel{f \times g}{\to} B \times B \simeq B + B \stackrel{codiag}{\to} B,

and the additive identity in hom(A,B)hom(A, B) is of course the zero map. Conversely, a CMonCMon-enriched category with finite products (or with finite coproducts) is a category with zero object and biproducts in the sense above.

By the way – sorry I haven’t been more active around here recently; there are lots of interesting threads going on. In part my excuse is that I’ve been added as a co-author to another mathematical blog, Vishal Lama’s blog, where I’ve begun talking about topics related to Boolean algebras, more or less at an undegraduate level.

Posted by: Todd Trimble on April 5, 2008 2:17 PM | Permalink | Reply to this

Re: Limits and Push-Forward

I mean (co)products not (co)limits. Sorry.

Posted by: Urs Schreiber on April 5, 2008 2:28 PM | Permalink | Reply to this

Re: Limits and Push-Forward

Thanks, Todd, that’s exactly what I wanted to know (even though I had a typo in the question :-/).

So it’s precisely the CMonCMon-enriched categories with finite products which have 0-objects and biproducts.

What if the requirement of having a 0-object is dropped?

Posted by: Urs Schreiber on April 5, 2008 2:42 PM | Permalink | Reply to this

Re: Limits and Push-Forward

There is little I can add to Todd’s comprehensive answer.

It’s possible for products and coproducts to coincide “accidentally”; for example, take the full subcategory of Set on a single countably infinite set! (If you want an example that has all finite (co)products, use sets-and-partial-functions, and take the empty set as well.) But the notion of biproduct nicely expresses the situation where they coincide coherently.

As Todd says, if a category is CMon-enriched then products or coproducts are automatically biproducts. (Nice exercise, if you haven’t seen it before.) Also, if a category is compact closed then products or coproducts are again automatically biproducts.

In both cases, this is true even in the purely nullary case, i.e. any initial or terminal object is a zero object. (In fact, CMon-enrichment is overkill here: it suffices for the category to be enriched in pointed sets.)

Posted by: Robin on April 5, 2008 4:47 PM | Permalink | Reply to this

Re: Limits and Push-Forward

I should have made it clearer that I’ve been assuming that phas is (enriched) cocomplete.

Then the Kan extension L:ΣphasL: \Sigma\to phas is given by the coend

(1) (f,s)X Σ×ΣΣ(s,)×F(fs). \int^{(f,s)\in X^\Sigma\times\Sigma} \Sigma(s,-)\times F(f s).

By the Fubini theorem, this is isomorphic to

(2) fX Σ sΣΣ(s,)×F(fs), \int^{f\in X^\Sigma}\int^{s\in\Sigma}\Sigma(s,-)\times F(f s),

which is isomorphic to

(3) fX ΣF(f) \int^{f\in X^\Sigma} F(f-)

by the density formula (aka the coend form of the Yoneda lemma). That’s the derivation of the claim I made yesterday. Since ff appears only once, and covariantly, this coend is just an ordinary colimit.

With your revised XX, this colimit is a pushout.

(I can’t pretend that I’ve followed the back-story very clearly, so this observation may or may not be helpful.)

Posted by: Robin on April 2, 2008 12:49 PM | Permalink | Reply to this

Re: Limits and Push-Forward

That’s the derivation of the claim I made yesterday.

Thanks, that was helpful. Good that you mentioned Fubini (it’s amazing how close the similarities to ordinary integration theory are!!) and the density formula. I spent more time reading Kelly and think that I am following now.

So the result fX ΣF(f)=colim X ΣF(f) \int^{f \in X^\Sigma} F(f -) = colim_{X^\Sigma} F(f-) is, unless I am still mixed up, the same fomula which I get by starting with

X Σ×Σ ev *F phas Σ \array{ X^\Sigma \times \Sigma &\stackrel{ev^* F}{\to}& phas \\ \downarrow \\ \Sigma } then using the hom-transform to think of this as X Σ phas Σ pt \array{ X^\Sigma &\to& phas^\Sigma \\ \downarrow \\ pt } and then do the push-forward to the point, hence the colimit over X ΣX^\Sigma with values in phas Σphas^\Sigma.

That colimit then boils down to the one you derived.

I was hoping doing it not this way but using direct push-forward to Σ\Sigma would be more enlightning. And indeed, I learned a lot here. Thanks for all your feedback.

(My replies have been slow. That’s because I am now on leave of absence from Hamburg, lost my office there now, am living “on the road” for a month now, until I’ll settle down again office-wise in May. That makes me spend more time in trains than online…)

Posted by: Urs Schreiber on April 2, 2008 9:18 PM | Permalink | Reply to this

index (co)limits and (co)ends

For the record and for my own benefit, I’ll review and summarize some of the enriched category theory aspects appearing in the above discussion (many thanks to Robin Houston for the help he provided!!), and pointing out where it says what in Kelly’s book:

G. M. Kelly, Basic concepts of enriched category theory

There are several directions from which to approach the generalization of ordinary (co)limits known as indexed (co)limits and as (co)ends. I’ll do it in a fashion somewhat reverse to how Kelly presents it:

For me the starting point is the observation (section 3.4) that a cone over a functor

G:KB G : K \to B

with tip bBb \in B usually thought of as a a transformation from the constant functor Δb\Delta b with value the tip bb into the functor G

Cone(b,F)[K,B](Δb,G), Cone(b,F) \in [K,B](\Delta b, G) \,,

where Δb:K{pt}ptbB, \Delta b : K \to \{pt\} \stackrel{pt \mapsto b}{\to} B \,,

can equivalently be thought of as a cone in “copresheaves” on KK, with tip the constant functor Δ1\Delta 1 at the singleton set:

[K,B](ΔB,G)[K,Set](Δ1,B(b,G())). [K,B](\Delta B, G) \simeq [K,Set](\Delta 1, B(b,G(-))) \,.

I suppose one way to motivate indexed limits is to observe that in the formulation on the right hand, as opposed to the one on the left hand, there is a singled out functor appearing, namely

Δ1:K{pt}pt{}Set. \Delta 1 : K \to \{pt\} \stackrel{pt \mapsto \{\bullet\}}{\to} Set \,.

Therefore it is natural to generalize the notion as it appears on the right, by replacing this constant functor with something else.

And indeed, that’s what one does:

we allow SetSet to be replaced by any other enriching category VV (I won’t try to list all the properties we need on VV to make each an all of the following constructions possible) and generalize [K,Set](Δ1,B(b,G())) [K,Set](\Delta 1, B(b,G(-))) first to [K,V](ΔI,B(b,G())) [K,V](\Delta I, B(b,G(-))) and then to [K,V](F,B(b,G())), [K,V](F, B(b,G(-))) \,, where now F:KV F : K \to V can by any functor, not necessarily one constant at the tensor unit object.

(Now I am on p. 37, equation (3.1).)

Instead of saying then that the cone is indexed by KK, we say that it is indexed by FF (which includes the information about FF’s domain KK, of course).

Now, a limit of a functor GG is something that represents the universal cone over GG, in that morphisms into the limit are in bijection with cones over the functor.

So we do the same here and define the limit of GG indexed by FF, what you might denote lim FGlim_F G, by the property

B(b,lim FG):[K,V](F,B(b,G())) B(b,lim_F G) :\simeq [K,V](F, B(b,G(-)))

naturally for all bBb\in B.

Only that, for some reason, one invents completely unsuggestive new notation and writes {F,G}\{F,G\} for what I called lim FGlim_F G above. So this should really read:

B(b,{F,G}):[K,V](F,B(b,G())). B(b,\{F,G\}) :\simeq [K,V](F, B(b,G(-))) \,.

For indexed colimits the discussion is the same with both (!) KK and BB replaced by their opposite categories. (equation 3.5, p. 38).

The FF-indexed colimit colim FGcolim_F G over GG also receives its own notation: FGF \star G:

B(FG,b):[K op,V](F,B(G(),b)). B(F \star G , b) :\simeq [K^{op},V](F, B(G(-),b)) \,.

A most important special case of such indexed (co)limits is that where we can think of them as weighted (co)limits, a situation which is the basis for a striking similarity between indexed colimits and the theory of ordinary integration (as in functional analysis).

That special case is that where the codomain of our functor is (co)tensored over the enriching category. (section 3.7, p. 48)

A VV-category BB being tensored over VV is much like a “VV-module”: VV behaves like a monoid which acts on BB. Or more suggestively, BB behaves like a vector space over VV.

(Here is a question: is there a difference between saying that BB is tensored over VV and looking at VV as a monoid in VV-Cat and at BB as a module for that monoid in VV-Cat?)

If BB is tensored over VV one writes (this time the notation is natural)

vb v \otimes b

for the result of acting with vVv \in V on bBb \in B.

(The notation for the cotensor product, on the other hand, I can’t even typeset here without looking up special character tables…)

The punchline now is that if BB is tensored over VV, the (F:KV)(F : K \to V)-indexed colimit over a functor G:KBG : K \to B can be expressed by a coend over the tensor product:

colim FG:=FG kKF(k)G(k). colim_F G := F \star G \simeq \int^{k \in K} F(k) \otimes G(k) \,.

(equation 3.70, p. 53)

So now I say what what a coend is, the thing appearing on the right hand here:

Where indexed (co)limits generalized ordinary (co)limits by generalizing what we may regard as the tip of a cone, (co)ends generalize ordinary (co)limits by generalizing what the functor we take the limit over may be: namely from the case of functors on KK to functors on K op×KK^{op} \times K.

One way to motivate this is by thinking about what natural transformations really are:

given two ordinary functor:

T,S:AB T,S : A \to B

a natural transformation η:TS\eta : T \Rightarrow S is, for each aAa \in A a map η a:IB(T(a),S(a)) \eta_a : I \to B(T(a),S(a)) namely a morphism in BB, such that all naturality squares commute, which in terms of this map means that for all f:abf : a \to b in AA we have

I η a B(T(a),S(a)) η b B(T(a),S(f)) B(T(b),S(b)) B(T(f),S(b)) B(T(a),S(b)). \array{ I &\stackrel{\eta_a}{\to}& B(T(a),S(a)) \\ \downarrow^{\eta_b} && \downarrow^{B(T(a),S(f))} \\ B(T(b),S(b)) &\stackrel{B(T(f),S(b))}{\to}& B(T(a),S(b)) } \,.

The point to notice is that in the special case that the functor TT is trivial this reduces precisely to a cone over the functor B(T,S()):ABB(T,S(-)) : A \to B. So the naturality of natural transformations is a generalization of the notion of cone to functors with a covariant and a contravariant dependence on their domain category.

As the vertical morphisms of a cone form a natural family of morphisms with respect to the functor that the cone lives over, the morphisms η a:IB(T(a),S(a))\eta_a : I \to B(T(a),S(a)) of a natural transformation form what is called an extraordinary natural family (1.7, p. 17).

Generally, then, this is the definition of an end: not just a universal natural family of morphisms (that would be a limit), but a universal extraordinary natural family.

More precisely for a functor T:A op×AV T : A^{op} \times A \to V a (extraordinary) natural family of morphisms from some object kVk \in V λ a:kT(a,a) \lambda_a : k \to T(a,a) for all aAa \in A is one for which for all f:abf : a \to b in AA we have: K λ a T(a,a) λ b T(a,f) T(b,b) T(f,b) T(a,b). \array{ K &\stackrel{\lambda_a}{\to}& T(a,a) \\ \downarrow^{\lambda_b} && \downarrow^{T(a,f)} \\ T(b,b) &\stackrel{T(f,b)}{\to}& T(a,b) } \,. Or rather, this is the condition when it makes sense to speak of morphism in AA, as when V=SetV = Set. More generally one reformulates this into a more robust (but less enlightning on first sight) way which works for all enrichment categories. See equation 1.40 on p. 18.

Then (p. 27) the end

AT:= aAT(a,a) \int_A T := \int_{a \in A} T(a,a)

over a functor T:A op×AVT : A^{op} \times A \to V is the (domain object of the) universal such natural family, in that every other one factors through it.

We get from this back to the motivating example of natural transformations by now noticing that this gives a way to speak of the VV-object of natural transformations in any enriched context (2.2, p. 29): the VV-object of natural transformations of VV-functors T,S:ABT,S : A \to B is defined by the end over the functor B(T(),S())B(T(-),S(-))

[A,B](T,S):= aAB(T(a),S(a)). [A,B](T,S) := \int_{a \in A} B(T(a),S(a)) \,.

Finally, now, we get to coends, by dualizing ends: the coend aAG(A,A)\int^{a \in A} G(A,A) is defined by (3.67, p. 53) B( aAG(a,a),b) aB(G(a,a),b) B(\int^{a \in A} G(a,a),b) \simeq \int_a B(G(a,a),b) naturally for all bBb \in B.

Just as ends over T:A op×AVT: A^{op} \times A \to V reduce to limits when there is no dependency of TT on the first (contravariant) variable of TT, coends reduce to colimits in the same case.

To get an intuition for what is going on with our formula for the FF-indexed colimit over GG

FG kKF(k)G(k) F \star G \simeq \int^{k \in K} F(k)\otimes G(k)

it is helpful to consider the special simple case that John described here:

suppose that V=FinSetV= FinSet such that isomorphism classes in VV are given by natural numbers and such that coproduct induced addition of these natural numbers.

Let A=Disc(X)A = Disc(X) be the discrete VV-category over a set XX: all Hom-objects are trivial.

Moreover, let B=SetModB = SetMod, the category whose objects are categories with a SetSet-action on them and whose morphisms are SetSet-linear functors between these.

(I am hoping that I am right that this BB is SetSet-tensored. If not, just take B=SetB = Set instead in the following.)

Then a functor G:AB G : A \to B i.e G:XSetMod G : X \to SetMod is like a vector-valued function on the set XX, and a functor F:XSet F : X \to Set is like a number-valued function on XX. And F()G() F(-)\otimes G(-) is like a vector valued function on XX obained by multiplying GG pointwise by FF.

Moreover, the coend xXF(x)G(x) \int^{x \in X} F(x)\otimes G(x) reduces to just to coproduct xXF(x)G(x). \oplus_{x \in X} F(x) \otimes G(x) \,. This is just like the integral of GG over XX weighted by FF.

It is amazing how close the notion of coends, and also the notation used, is to ordinary integration theory. But the notation is not perfect. First of all it is a pity that the coend has the integration bounds on top instead of at the bottom of the integral sign. It should be the other way around.

If I had to make up notation from scratch, I’d opt for writing the coend of a functor GG with values in a VV-tensored category BB with weight FF as

XGdμ F. \int_X G \; d\mu_F \,.

Moreover, if products and coproducts coincide, such as in FinVectFinVect, I’d write (along the lines of John Baez, of course) a,b:=B(a,b) \langle a,b\rangle := B(a,b) for a,bBa,b \in B, which would turn formulas such as 3.67 into pleasant familiar formulas such as XGdμ F,b= XG,bdμ F. \langle \int_X G \; d\mu_F , b \rangle = \int_X \langle G , b \rangle \; d\mu_F \,.

Posted by: Urs Schreiber on April 3, 2008 9:25 AM | Permalink | Reply to this

Re: index (co)limits and (co)ends

Now for Kan extensions.

Continuing with motivational remarks along the lines I ended the previous comment with, the problem is this:

on XX we might have a “vector bundle” F:XB F : X \to B in that there is an object of BB over each point of XX as the fiber. Then given a projection X p W \array{ X \\ \downarrow^{p} \\ W } we may want to “push down” the vector bundle to WW such that X F B p 1F W. \array{ X &\stackrel{F}{\to}& B \\ \downarrow &\Downarrow& \nearrow_{\int_{p^{-1}} F} \\ W } \,.

The universal way to do this is the (left) Kan extension

Lan pF Lan_p F

of FF along pp.

Well, Kelly argues on p. 65 that this way of thinking of the Kan extension is subobtimal, and rather defines it in terms of an indexed colimit (p. 61):

Let p˜:W[X op,V] \tilde p : W \to [X^{op},V] be given by (3.39) p˜(w):=W(p(),w), \tilde p(w) := W(p(-),w) \,, then (Lan pF)():=p˜()F. (Lan_p F)(-) := \tilde p(-) \star F \,.

This begins to look more suggestive when we assume again that BB is tensored and use the reformulation of indexed colimits in terms of coends over tensor products in this case:

(Lan pF)()= xXp˜()(x)F(x), (Lan_p F)(-) = \int^{x \in X} \tilde p(-)(x) \otimes F(x) \,, which in turn is (Lan pF)()= xXW(p(x),)F(x). (Lan_p F)(-) = \int^{x \in X} W(p(x),-) \otimes F(x) \,.

I find it useful to think of this again in our simple example where XX and WW are just sets, namely discrete categories (no nontrivial morphisms). Let me use the alternative notation which I suggested, to make that point more clearly:

(Lan pF)(w)= XFdμ p˜(w) (Lan_p F)(w) = \int_X F \; d\mu_{\tilde p(w)}

The “measure” dμ p˜(w) d\mu_{\tilde p(w)} on XX in this formula, for each wWw \in W is unity on all xx which do live in the fiber over ww with respect to pp, and vanishes otherwise.

Therefore in this case the left Kan extension of our “vector bundle” indeed sums up all fibers of the bundle that project down to the same point over WW.

(I should admit that I made a quick google search trying to see if there is any literature on the relation between push-forward of bundles and Kan extensions. But couldn’t really find anything. Of course one might need arXiv:0705.0452 to get started here ;-)

Next i wanted to say something about the Fubini theorem for coends and about the “density formula”. But I realize that I need a little more thinking about that before talking about it here.

Posted by: Urs Schreiber on April 3, 2008 10:57 AM | Permalink | Reply to this

Re: index (co)limits and (co)ends

Sorry for the trivial comment after your very detailed post, but there is one thing I can say without having to think about it first:

\pitchfork = \pitchfork

Posted by: Robin on April 3, 2008 4:56 PM | Permalink | Reply to this

Back to Basics

My inability to understand limits has been a barrier to me being able to appreciate 99% (or more) of the cool things going on around here. Could someone help me understand limits? The wikipedia page doesn’t help me much. I need a physicist-type definition/presentation.

Links are more than welcome.

Thanks

Posted by: Eric on May 27, 2009 6:34 AM | Permalink | Reply to this

Re: Back to Basics

Maybe more specifically, I’m trying to inch my way toward understanding Kan extension, so whatever is the most direct route, either via limits, colimits, coends, or whatever, is the path I hope to take.

Here’s some useful stuff I’ve found so far:

Posted by: Eric on May 27, 2009 7:00 AM | Permalink | Reply to this

Re: Back to Basics

Personally to understand Kan extensions I just needed to get good at understanding adjoint functors, because Kan extensions are a special case of adjoint functors.

You can compute Kan extensions using limits and colimits, but the idea of a Kan extension is much simpler. It’s just a best attempt to solve an impossible problem. Someone hands you functors p:CCp: C \to C' and F:CDF: C \to D and asks for a functor F:CDF': C' \to D that makes this equation hold: F=FpF = F' p. You can’t usually do it. But the left and right Kan extensions are your best attempts.

You’ll understand this once you really understand that the left and right adjoints of a functor are your best attempts at solving another impossible problem: finding its inverse.

The point is that in category theory, even when some functors don’t satisfy an equation, they can still “do their best”, thanks to the presence of natural transformations.

I know what I’m saying is cryptic, but it’s just one possible roadmap to get to what you want to understand. It’s the simplest roadmap I know.

Furthermore, until you understand adjoint functors you are doomed when it comes to category theory.

Posted by: John Baez on May 27, 2009 7:26 AM | Permalink | Reply to this

Re: Back to Basics

Thank you! Thank you again!

This reminds me a LOT of (weighted) least squares. In fact, I would not be at all surprised if Kan extension was related to some kind of categorified (weighted) least squares. Or something…

Posted by: Eric on May 27, 2009 7:49 AM | Permalink | Reply to this

Re: Back to Basics

Unless possessed of godlike intellect, to understand limits you have to start by understanding examples of limits.

Do you understand products? Do you understand equalizers? Do you understand pullbacks?

Do you understand products, equalizers, and pullbacks in the category of sets? Do you understand them in the category of vector spaces? Do you understand them in the category of groups?

These are basic examples of limits. Limits are a very general concept, because limits apply to diagrams of any shape, in any category. You have to start with limits of a simple shape in a category you know well.

I tried to write a quick expository intro to pullbacks at the nnLab. But I think the best way to learn this stuff is to read Goldblatt’s book, which is pretty cheap and free online.

Examples, examples, examples! You’ve got to work through a bunch of examples.

Posted by: John Baez on May 27, 2009 7:13 AM | Permalink | Reply to this

Re: Back to Basics

Thank you! Thank you!

I REALLY enjoy Goldblatt’s writing style so far. I feel a sudden sense of hope :)

Posted by: Eric on May 27, 2009 7:42 AM | Permalink | Reply to this

Re: Back to Basics

My copy of Goldblatt arrived today. A nice birthday present to myself :)

Thanks again for the recommendation.

Posted by: Eric on June 27, 2009 4:48 AM | Permalink | Reply to this

Re: Back to Basics

Happy birthday! This book comes with a team of experts who will answer questions about it — the nnCafé regulars.

Posted by: John Baez on June 27, 2009 8:04 AM | Permalink | Reply to this

Re: Back to Basics

Could someone help me understand limits?

Well, we started trying to do that a while ago. The entry

[[limits and colimits by example]]

was motivated mainly from your questions about limits and colimits.

I have to admit that at the moment the entry at the beginning does not so much explain how to come up with limits, as more listing basic examples.

But then in the second part Jocelyn Paine gives a very small-step-by-small step description of simple colimits in Set.

Well, at the moment Jocelyn Paine describes how to teach a computer to understand colimits in Set.

In any case, this entry is waiting for your questions. You should insert them there in green query boxes, and we’ll try to reply to them. And eventually you’ll be able to answer these questions yourself.

I am also planning on entries

[[examples for Kan extensions]]

and

[[examples of adjoint functors]]

but there is not much there yet.

But drop a question there, and chances increase that eventually more material accumulates as if by magic.

Posted by: Urs Schreiber on May 27, 2009 9:29 AM | Permalink | Reply to this

Re: Back to Basics

Could someone help me understand limits?

By the way, with respect to understanding Johan Alm’s work:

A detailed description of how the Kan extension that describes quantization works over points is at

The First Part of the Story of Quantizing by Pushing to a Point…

Johan tells the second part of this story, which I never got around to telling :-)

Posted by: Urs Schreiber on May 27, 2009 10:27 AM | Permalink | Reply to this

Re: Back to Basics

A nice video explanation from Catsters:

General limits and colimits 1

Posted by: Eric on May 27, 2009 4:42 PM | Permalink | Reply to this

Re: Back to Basics

A nice video explanation from Catsters:

A, right. I had forgotten to link to their stuff.

But you forgot something, too: to deposit the link you found at the nnLab, for the benefit of those to come after you.

I now did it for you ;-)

Posted by: Urs Schreiber on May 27, 2009 5:50 PM | Permalink | Reply to this

Re: Back to Basics

I was also going to suggest the Catsters videos. In fact, you shouldn’t start with that one, you should start with Terminal and Initial Objects 1, and watch everything forward from there. That will get the examples in first.

Posted by: Tim Silverman on May 27, 2009 7:07 PM | Permalink | Reply to this

Post a New Comment