# Coend computation

Let

$F:A^{\mbox{op}} \to \mbox{Set}$

and define

$G_a:A\times A^{\mbox{op}} \to \mbox{Set}$

$G_a(b,c) = \mbox{hom}(a,b) \times F(c)$.

I think the coend of $G_a$,

$\int^AG_a$,

ought to be $F(a)$--it's certainly true when A is discrete, since then hom is a delta function. But my colimit-fu isn't good enough to actually compute the thing and verify it's true. Can someone walk me through the computation, please?

-
is this a category-theoretic analogue of the main theorem of the fundamental theorem of calculus? – Martin Brandenburg Apr 6 '10 at 0:13
@Martin: an FToC analogue would require a 'boundary' computation of some sort. This seems more like a distribution computation, where the hom works like $\delta(a-b)$, so the integral over the whole space is just evaluation. – Jacques Carette Apr 6 '10 at 3:20

But you asked to be walked through it. First: yes, it is $F(a)$. Another way of writing your coend $$\int^A G_a$$ is as $$\int^{b \in A} G_a(b, b) = \int^b \mathrm{hom}(a,b) \times F(b).$$ I claim this is canonically isomorphic to $F(a)$. I'll prove this by showing that for an arbitrary set $S$, the homset $\mathrm{hom}(\mathrm{this}, S)$ is canonically isomorphic to $\mathrm{hom}(F(a), S)$. The claim will then follow from the ordinary Yoneda Lemma.
So, let $S$ be a set. Then \begin{align} \mathrm{Set}(\int^b \mathrm{hom}(a, b) \times F(b), S) & \cong \int_b \mathrm{Set}(\mathrm{hom}(a, b) \times F(b), S) \\ &\cong \int_b \mathrm{Set}(\mathrm{hom}(a, b), \mathrm{Set}(F(b), S)) \\ &\cong \mathrm{Nat}(\hom(a, -), \mathrm{Set}(F(-), S)) \\ &\cong \mathrm{Set}(F(a), S) \end{align} I don't know how much of this you'll want explaining, so I'll just say it briefly for now. If you want further explanation, just ask. The first isomorphism is kinda the definition of colimit. The second is the usual exponential transpose/currying operation. The third is maybe the most important: it's a fundamental fact about ends that if $F, G: C \to D$ are functors then $$\mathrm{Nat}(F, G) = \int_c D(F(c), G(c)).$$ The fourth and final isomorphism is the ordinary Yoneda Lemma applied to the functor $\mathrm{Set}(F(-), S)$.
I'm a little confused by your notation: specifically, what is the category $\mathrm{Nat}$? From the types its objects are functors $A^{op} \to \mathrm{Set}$, so it's the functor category whose objects are the natural transformations between those functors? – Neel Krishnaswami Apr 6 '10 at 14:14
FWIW You can formalise the steps in the construction of this isomorphism as a Haskell program. Here's one direction, with f being the relevant morphism: hpaste.org/fastcgi/hpaste.fcgi/view?id=24722 I suspect that by interpreting Haskell code as the internal language of some family of categories then this becomes a perfectly good definition of the isomorphisms for mathematical purposes too, and not just a statement about some Haskell functions. – Dan Piponi Apr 6 '10 at 16:53
Neel, I guess Nat is a slightly unspecific notation, like hom. The first occurrence of Nat meant "hom in $[A^{op}, \mathrm{Set}]$". Here $[A^{op}, \mathrm{Set}]$ is the category whose objects are functors $A^{op} \to \mathrm{Set}$. So: Nat is not a category; it means "hom" in that functor category. I might equally well have written "$[A^{op}, \mathrm{Set}]$" in place of "Nat". (In fact I prefer to; I was making a perhaps misguided effort to be more widely comprehensible.) Similarly, the second occurrence of "Nat" could be replaced by "$[C, D]$". – Tom Leinster Apr 6 '10 at 20:08
Ah, thanks -- I've just never seen Nat used like that before. Amusingly, the $[A^{op}, \mathrm{Set}]$ notation is the one I've seen before. :) – Neel Krishnaswami Apr 6 '10 at 22:43