$\to$
Guest post by Fosco Loregian and Bryce Clarke.
Pastro, Craig, and Ross Street. Doubles for monoidal categories. Theory and applications of categories 21.4 (2008): 61-75.
Coend calculus rules the behaviour of certain universal objects associated to functors of two variables $T : C^{op}\times C \to D$; intuitively, $end(T)$ stands to $T$ as the limit $\lim\, F$ of $F : A \to B$ stands to $F$; the major difference is that $end(T)$ takes into account the fact that $T$ eats at the same time two “terms” of the same “type” $C$, once covariantly in the second component, and once contravariantly in the first: on arrows $f : c\to c'$ the functor $T$ acts in fact as follows:
Now, a distinguising feature of the objects that depend contra-covariantly on the same variable is that they can be integrated: given a sufficiently regular function $f(x)$, its dependence from $x$ can be thought as “covariant” (and defined, say, on a topological vector space $V\cong \mathbf{R}^n$), whereas the “$d x$” in the symbol
is contravariant (it belongs to a certain dual space of covectors on $V$); altogether, the integral can be thought as exhibiting a contra-covariant dependence from $x$.
Ends and coends are associated to functors $T : C^{op}\times C \to D$ in a similar fashion that resembles integration: they are certain objects $\int_c T(c,c)$ (the end) and $\int^c T(c,c)$ (the coend), canonically associated to $T$, treating $c$ as a mute variable (meaning that $\int_c T(c,c)$ and $\int_{c'} T(c',c')$ are the same object), and satisfying a “commutative rule of integrals” analogous to
The end of $T$ is endowed with projections on the “symmetrized components” $\int_c T(c,c) \to T(c',c')$, one for each object $c'$; dually, the coend $\int^c T(c,c)$ is endowed with injections $T(c',c') \to \int^c T(c,c)$.
All in all, this happens also for colimits, so the two constructions are -at least intuitively- tightly related: this intuition can of course be made more precise. Every universal object built in category theory can be thought either as a subobject of a product (a limit), or as a quotient of a coproduct (a colimit), and co/ends make no exception:
More on this will be explained later on in the discussion.
What is more important now, and quite astounding, is that such contra-covariant actions arise at every corner of category theory: using co/ends it is possible to re-state the Yoneda lemma and the theory of Kan extensions, and to find plenty of applications to algebra, topology, geometry… and functional programming. :-)
As already said, a functor $T : C^{op}\times C \to D$ acts on morphisms as
given two such functors, say $P,Q : C^{op}\times C \to D$, we can consider the two diagrams
and
Given two functors $F,G : A \to B$ a natural transformation can be seen as a family of maps that “fill the gap” between $F(f)$ and $G(f)$ in a commutative square; in a similar fashion, a dinatural transformation between the above $P,Q$ can be seen as a way to close a certain diagram that testifies a transformation from the arrow action of $P$ to the arrow action of $Q$:
Just as co/limits are defined via suitable transformation to/from a constant, so are co/ends:
There exists a category $Wd(Q)$ of wedges, defined with an obvious choice of morphisms between bases; similarly, there is a category of cowedges $Cwd(P)$.
The end $\int_c Q(c,c)$ of $Q$ is now defined as a terminal object in the category of its wedges; dually, the coend $\int^c P(c,c)$ of $P$ is the initial object of the category of its cowedges. Of course, we say “the” end because such an initial object is unique up to unique isomorphism when it exists.
So far, so good. In fact, we didn’t stray much far from plain old category theory, as it is possible to show the following:
Lemma (co/ends are colimits): Given $Q : C^{op}\times C \to D$ there exist a category $\text{tw}\, C$ and a functor $Q^\tau : \text{tw}\, C \to D$ such that
For those who know: the end of $Q$ is the weighted colimit of $Q : C^{op}\times C \to D$ with the $\hom_C$ functor $C^{op}\times C \to Set$, and thus the category $\text{tw}\, C$ is nothing more, nothing less than the category of elements of $\hom_C$; this allows for a very explicit presentation of $\text{tw}\, C$:
Corollary (hom commutes with all ends): As a consequence of the fact that $\int_c Q$ is a limit, there is an isomorphism
natural in $y$. Dually,
natural in $y$.
(of course, a coend is just an end in the opposite category!)
But why are co/ends denoted as integrals? The notation dates back to Yoneda,
Yoneda, Nobuo. “On Ext and exact sequences.” J. Fac. Sci. Univ. Tokyo Sect. I 8.507-576 (1960): 1960.
(in particular, see §4 but beware that the notation is reversed; a coend is denoted $\int_a$ and an end $\int_a^\ast$!) and it is essentially motivated by the fact that an end behaves like an integral:
Theorem (Fubini rule): Let $P : C^{op}\times C \times D^{op}\times D \to E$ be a functor; then
in the sense that if one of the three objects exists, so do the other two, and they are all canonically isomorphic (the category $C^{op}\times C \times D^\text{op}\times D$ is of course equal to $(C\times D)^\text{op}\times( C \times D)$). Similarly, there is such a rule for ends.
Thus, in category theory integration with respect to a variable is a process that can happen in whatever order we desire: given a permutation $\sigma$ of the set $\{1,\dots,n\}$, whenever the integral
exists, then so does
Proof. The slickest proof I know for this goes as follows: assume all coends exist; then, sending a functor $P : C^{op}\times C \to D$ to its coend is a functor $\int^C : [C^{op}\times C, D] \to D$, and it is easy to see that it is a left adjoint (for those who know, $\int^C$ is a particular kind of weighted colimit, and every such weighted colimit admits a right adjoint expressed in terms of the weight: but now it’s easy to prove that these right adjoints commute, thus yielding the Fubini rule by uniqueness of adjoints).
Here we explore how co/ends allow to rediscover category theory from scratch.
Theorem (Natural transformations as an end) Let $F,G : C \to D$ be two functors; then, there is an isomorphism
Proof. There is a natural choice for a wedge $\omega : Nat(F,G) \to \hom(F c,G c)$, that sends a natural transformation to its $c$-component; it remains to show that this is indeed a terminal wedge. Given another wedge $\alpha : A \to \hom(F c, G c)$, the wedge condition translates into the equation
valid for every $a\in A$; but this is only a convoluted way to say that for every $a\in A$ the family
is a natural transformation.
Two important remarks:
In an additive setting, the wedge condition for $\alpha$ can be easily translated into the fact that natural transformations appear form the kernel of a certain map; the intuition that naturality is a cocycle condition is more or less what led Yoneda to study ends and coends in homological algebra.
Even in a non-additive setting, one can easily see that a natural transformation $\alpha : F \Rightarrow G$ is a map that equalizes the action of $F,G$ on arrows; this means that the following diagram
is an equalizer; there is nothing special here, as for every functor $T : C^{op}\times C \to D$ there is a similar equalizer diagram
Here‘s a discussion on what is the coend of the hom functor; I claim that the following object represents the coend of $\hom(F-,G-)$, perhaps you know where the same object appears under a different name, and where it is used for some purpose? I find this particularly intriguing in the case of a monoid $M$ regarded as single-object category:
I didn’t expect these construction to be dual, and yet they are!
Claim (but also: exercise for the reader). Let $C$ be a small category. The coend
is the set of connected components of the “endo-comma” category whose objects are endomorphisms of $C$, and whose morphisms $(u : x \to x) \to (v : y \to y)$ are the $f : x \to y$ such that $f u = v f$. More generally, if $F,G: C \to D$ are functors there is an isomorphism
where the endomorphism comma is defined similarly.
On the first day He created the Yoneda lemma, and He saw that it was good:
Theorem (The ninja Yoneda lemma) Let $F : C^{op} \to Set$; then for every object $a\in C$,
Proof. The set $\int_c \Set(\hom_C(c,a), F c)$ is the set of natural transformations from $\hom(-,c)$ to $F$, and thus the non-ninja Yoneda lemma yields an isomorphism between this set and $F a$. Dually, call $F\otimes y$ the functor
Then, we have
Each of these steps can be easily justified in light of what we already proved:
This natural deduction-style kind of proof is half-jokingly called “coend-fu” ((端楔術 : literally “the art [of handling] terminal wedges”) in my note, soon-ish a book, on coends.
Incidentally, the isomorphism $F a\cong \int^c F c \times \hom_C(a,c)$ is precisely the sense in which “every presheaf is a colimit of representable functors”; the colimiting diagram has domain the category of elements of $F$, and the natural functor $\Sigma : El(F) \to C \to [C^{op},Set]$ has colimit $F$.
On the second day, He created Kan extensions, and category theory was complete.
Theorem (Kan extensions are co/ends) Let $A \xleftarrow{G} B\xrightarrow{F} C$ be a span of functors; if the coend
exists, then it is the value at $a$ of the left Kan extension of $F$ along $G$; dually, is the end
exists, then it is the value at $a$ of the right Kan extension of $F$ along $G$.
Proof. The proof is another lengthy, but completely straightforward, kata using the coend-fu we already know:
This Pastro and Street paper makes heavy use of the theory of bimodules. Let’s dig deeper into their structure. First of all, let us define a bicategory as follows:
The composition of 1-cells is the tensor product of modules: ${}_R M \otimes_S N_T$ is a $R$-$T$-bimodule for every $R$-$S$bimodule $M$ and every $S$-$T$-bimodule $N$ (so in particular this is not a strict 2-category); 2-cells are composed horizontally and vertically, using the obvious function composition, and bifunctoriality of the $\otimes$ operation.
Good! There is a 2-categorical characterization of modules. What is good for? Well: rings are monoids in the category of abelian groups. We could have done the very same thing taking (plain) monoids, i.e. monoids in the category of sets, and defining a category of “bimodules” as sets with a left action of some monoid, and a right action of some other monoid.
What is interesting now is that we can generalize the same construction, with no additional cognitive loading, and take $X,Y,Z\dots$ to be multi-object monoids: we define a bicategory $Mod$ as follows:
A functor $P : D^{op}\times C \to Set$ is a multiobject module on which the multiobject monoids $C,D$ act.
So categories really are monoids, and are also eager to act on sets.
A bimodule is also called a profunctor, a distributor, a correspondence, a span,… and possibly with many other names; each of these names comes from a certain intuition behind their nature that leads to the definition of the same bicategory:
they are called profunctors because they generalize functors: some profunctors are called representable, and they are the ones of the form $\hom(b, F a)$ for some functor $F : A \to B$ between categories. A pro-functor thus works “on behalf of a functor”, as well as a relation generalizes a function.
…which is why some people prefer to call them relators: just as a func-tion is a special kind of rela-tion, a func-tor is a special kind of rela-tor.
they are called distributors: as the nLab says,
> Jean Bénabou, who invented the term and originally used “profunctor,” now prefers “distributor,” which is supposed to carry the intuition that a distributor generalizes a functor in a similar way to how a distribution generalizes a function.
There’s in fact a beautiful story about this: Lawvere defined a notion of distribution between toposes, such that the points of a topos $p : Set \to \mathcal{E}$ behave like Dirac delta functions, and such that distributions between presheaf toposes are exactly profunctors.
they are called correspondences or spans because of the Grothendieck construction: every presheaf $P : D^{op}\times C \to Set$ has a category of elements $El(P)$ that in this case is a discrete fibration over $D^{op}\times C$
Well… until now we cheated a bit. In order to get a bicategory we need to define a composition law for 1-cells and show that it is bifunctorial, and I didn’t tell you how to do it: but it turns out it is really easy, if you know coend-fu! Indeed, the intuition of a bimodule as a “matrix indexed by its domain” and the rule to compose two relations guide us to find an expression to meaningfully compose $Q : A \mathrel{⇸} B, P : B \mathrel{⇸} C$. We can define
boils down, on discrete domains $A,B\in\Set$ to a “matrix product of sets” like
There is also a connection between the ways in which profunctors compose, and the way in which relations do. Indeed, look how the two concepts closely resemble each other:
Finally: yes, you can make this precise by saying that sets are discrete categories, or even more precisely categories enriched over truth values, and that relations are precisely the $\{0,1\}$-enriched version of profunctors, as they are functions $A\times B \to \{0,1\}$!
One of the key results of the paper Doubles for Monoidal Categories is the canonical equivalence of categories:
This theorem has since been labelled by some as the “fundamental theorem of optics”, as it provides the link between the category of Tambara modules $\mathbf{Tamb}(\mathcal{C})$ and the double $\mathbf{Doub}(\mathcal{C})$ of the monoidal category $\mathcal{C}$, now also known as the category of optics. To unpack this theorem, we first begin with the definition of a Tambara module.
The category of (bi)modules $\mathbf{Mod}$ forms a bicategory, however when we choose a particular category $\mathcal{C}$ we may instead consider the monoidal category $\mathbf{Mod}(\mathcal{C})$ whose:
One may ask the question: what happens when $\mathcal{C}$ has the structure of a monoidal category?
Definition: Let $\mathcal{C}$ be a monoidal category. A (left) Tambara module on $\mathcal{C}$ consists of:
Last revised on August 19, 2019 at 08:45:31. See the history of this page for a list of all contributions to it.