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\}$.

Is there a useful generalization of this correspondence between limits and push-forward for the case of indexed limits? I am concerned with push-forward of ($n$-)functors along projections onto a factor of a cartesian product $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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1647

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 = (\omega Cat, \otimes_{Gray})$. Then

target space is a $V$-category $X$

parameter space is a $V$-category $\Sigma$

the background field is a $V$-functor $\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^* \nabla : hom(\Sigma,X)\times\Sigma \stackrel{ev}{\to} X \stackrel{\nabla}{\to} phas$

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

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

This yields (if it exists) another $V$-functor $\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:

$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 $F$ is the left Kan extension of F along the functor $p: A\to\{pt\}$.

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

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

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

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

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

(3)$(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 = Cat$ so that a $V$-category is a strict 2-category.

Let $X$ be the 2-category

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

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

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

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

I am after the pushforward of $ev^* F$ down to $\Sigma$ along the canonical projection $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 $X$; it’s the functor that takes $s\in\Sigma$ to the colimit, over $f\in[\Sigma,X]$, of $F(fs)$. We might write it as

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

For your choices of $X$ and $\Sigma$, the category of functors $\Sigma\to X$ has a terminal object (the constant functor at $y$), so the whole thing is just the constant functor at $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 $X$ instead something like $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 = Set-Mod$ and took $F$ to assign the Set-module Set to each object and right multiplication by a set to each morphism. Setting $phas = 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 $X$ 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 $X$ has a terminal object.

Right, actually I gave the wrong $X$, I should be looking at

$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 $FinVect$? 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 $FinVect$ 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 $A$ and $B$ are objects in a category with finite products and finite coproducts, then a map

$A + B \to A \times B$

determines (and is determined by) four maps (from $A$ to $A$, $A$ to $B$, etc.) which can be thought of as entries in a $(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 + 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 $CMon$-enriched, not $Ab$-enriched). The sum $f + g$ of two maps $f, g: A \to B$ is given by the evident composite

$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)$ is of course the zero map. Conversely, a $CMon$-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

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 $CMon$-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

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: \Sigma\to phas$ is given by the coend

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

By the Fubini theorem, this is isomorphic to

(2)$\int^{f\in X^\Sigma}\int^{s\in\Sigma}\Sigma(s,-)\times F(f s),$

which is isomorphic to

(3)$\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 $f$ appears only once, and covariantly, this coend is just an ordinary colimit.

With your revised $X$, 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 $\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

$\array{ X^\Sigma \times \Sigma &\stackrel{ev^* F}{\to}& phas \\ \downarrow \\ \Sigma }$ then using the hom-transform to think of this as $\array{ X^\Sigma &\to& phas^\Sigma \\ \downarrow \\ pt }$ and then do the push-forward to the point, hence the colimit over $X^\Sigma$ with values in $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 : K \to B$

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

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

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

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

$[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

$\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 $Set$ to be replaced by any other enriching category $V$ (I won’t try to list all the properties we need on $V$ to make each an all of the following constructions possible) and generalize $[K,Set](\Delta 1, B(b,G(-)))$ first to $[K,V](\Delta I, B(b,G(-)))$ and then to $[K,V](F, B(b,G(-))) \,,$ where now $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 $K$, we say that it is indexed by $F$ (which includes the information about $F$’s domain $K$, of course).

Now, a limit of a functor $G$ is something that represents the universal cone over $G$, 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 $G$ indexed by $F$, what you might denote $lim_F G$, by the property

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

naturally for all $b\in B$.

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

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

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

The $F$-indexed colimit $colim_F G$ over $G$ also receives its own notation: $F \star G$:

$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 $V$-category $B$ being tensored over $V$ is much like a “$V$-module”: $V$ behaves like a monoid which acts on $B$. Or more suggestively, $B$ behaves like a vector space over $V$.

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

If $B$ is tensored over $V$ one writes (this time the notation is natural)

$v \otimes b$

for the result of acting with $v \in V$ on $b \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 $B$ is tensored over $V$, the $(F : K \to V)$-indexed colimit over a functor $G : K \to B$ can be expressed by a coend over the tensor product:

$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 $K$ to functors on $K^{op} \times K$.

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

given two ordinary functor:

$T,S : A \to B$

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

$\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 $T$ is trivial this reduces precisely to a cone over the functor $B(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 $\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} \times A \to V$ a (extraordinary) natural family of morphisms from some object $k \in V$ $\lambda_a : k \to T(a,a)$ for all $a \in A$ is one for which for all $f : a \to b$ in $A$ we have: $\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 $A$, as when $V = 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

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

over a functor $T : 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 $V$-object of natural transformations in any enriched context (2.2, p. 29): the $V$-object of natural transformations of $V$-functors $T,S : A \to B$ is defined by the end over the functor $B(T(-),S(-))$

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

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

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

To get an intuition for what is going on with our formula for the $F$-indexed colimit over $G$

$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= FinSet$ such that isomorphism classes in $V$ are given by natural numbers and such that coproduct induced addition of these natural numbers.

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

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

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

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

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

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 $G$ with values in a $V$-tensored category $B$ with weight $F$ as

$\int_X G \; d\mu_F \,.$

Moreover, if products and coproducts coincide, such as in $FinVect$, I’d write (along the lines of John Baez, of course) $\langle a,b\rangle := B(a,b)$ for $a,b \in B$, which would turn formulas such as 3.67 into pleasant familiar formulas such as $\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 $X$ we might have a “vector bundle” $F : X \to B$ in that there is an object of $B$ over each point of $X$ as the fiber. Then given a projection $\array{ X \\ \downarrow^{p} \\ W }$ we may want to “push down” the vector bundle to $W$ such that $\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_p F$

of $F$ along $p$.

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 $\tilde p : W \to [X^{op},V]$ be given by (3.39) $\tilde p(w) := W(p(-),w) \,,$ then $(Lan_p F)(-) := \tilde p(-) \star F \,.$

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

$(Lan_p F)(-) = \int^{x \in X} \tilde p(-)(x) \otimes F(x) \,,$ which in turn is $(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 $X$ and $W$ 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_p F)(w) = \int_X F \; d\mu_{\tilde p(w)}$

The “measure” $d\mu_{\tilde p(w)}$ on $X$ in this formula, for each $w \in W$ is unity on all $x$ which do live in the fiber over $w$ with respect to $p$, 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 $W$.

(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.

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: C \to C'$ and $F: C \to D$ and asks for a functor $F': C' \to D$ that makes this equation hold: $F = 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 $n$Lab. 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 $n$Café 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

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

and

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:

But you forgot something, too: to deposit the link you found at the $n$Lab, 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