Death is only the co-end

José Goudet Alvim

2022-01-14

High priest Imohtep, cursed and buried alive, once said that “death is only the beginning”. That was a mistranslation, the original text actually said that “co-ends are only death” but the categorical nuances were missed by Evelyn Carnahan. This post is an effort to correct those mistakes and shed some light on this millennia old tradition of profunctors and necromancy.

Profunctors

Profunctors are an a priori strange little idea, they – in a way – embody the shape of the \(\hom\) functor in that they are functors of type \(\newcommand\dual[1]{{#1}^{\mathrm{op}}} \newcommand{\cat}{\mathcal} \newcommand{\nat}{\mathbf{Nat}} \newcommand{\proto}{\nrightarrow} \newcommand{\Set}{\mathbf{Set}} \newcommand{\To}{\Rightarrow} \newcommand{\dinat}{\mathrel{\dot\To}} \newcommand{\iso}{\cong} \renewcommand{\phi}{\varphi} \newcommand{\id}{\mathrm{id}}\) \[ \dual{\cat A}\times\cat B \to \cat V \] Where \(\cat A\) , \(\cat B\) , and \(\cat V\) are small categories. We write – when \(\cat V\) is known from context – \[ \cat B\proto\cat A \] as a shorthand for \(\dual{\cat A}\times\cat B \to \cat V\) ; and that’s profunctors for you!

Endo profunctors (those where both \(\cat A=\cat B\) ) are specially special because of how they resemble the \(\hom\) of a category – and the internal \(\hom\) functor \([\_,\_]\) of a monoidal closed category is the special among the specially special, since \(\cat V\) is also equal to the others and it has nice properties etc.

Dinatural Transformations

Profunctors obviously have at least one class of morphism between them, the natural transformations. But a different and and more general definition can be given when the profunctor is endo: dinatural transformations; which assigns arrows “on the diagonal”: given parallel (endo) profunctors \[ F, G: \cat A\proto \cat A \] a dinatural transformation between them, written as follows, is given \[ \alpha: F\dinat G \] by an assignment of arrows: \[ \alpha_a:F(a,a)\to G(a,a) \] such that for every arrow \(f:b\to a\) \[ \begin{array}{ccccc} & {\scriptsize F(a, f) } & F(a,b) & {\scriptsize F(f, b) } & \\ % & \swarrow & & \searrow & \\ % F(a,a) & & & & F(b,b) \\ % \downarrow & {\scriptsize \alpha_a} & & {\scriptsize \alpha_b} & \downarrow \\ % G(a,a) & & & & G(b,b) \\ & \searrow & & \swarrow & \\ % & {\scriptsize G(f, a) } & G(b,a) & {\scriptsize G(b, f) } & \\ \end{array} \]

Dinaturality is an extremely clunky looking definition, it is. They don’t form a category and don’t generally compose; profunctors only form a paracategory which really isn’t that impressive in my humble opinion.

Ends and Coends

Much like one takes the (co)-limit of a functor in terms of terminal/initial objects in some (co)cone category – namely we take limits over diagrams which are just special cones with the base we chose – we can take ends and coends of profunctors. And miraculously this isn’t only useful but also somewhat not-uncommon.

Wedges and co-Wedges

A wedge is like a cone: more precisely, a wedge is made of three parts: an apex, the base and the sides connecting them. The apex is an object \(\mathfrak a\) of \(\cat V\) ; the base are the objects at the diagonal of the profunctor ( \(F(c,c)\) for \(c\in\cat C\) ) and the sides are projections-like: an indexed family \[ \pi_c: \mathfrak a \to F(c,c) \] such that for any arrow \(f:b\to a\) in \(\cat V\) ,
\[ \begin{array}{ccccc} & {\scriptsize \pi_{c} } & \mathfrak a & {\scriptsize \pi_{c'}} & \\ % & \swarrow & & \searrow & \\ % F(a,a) & & & & F(b,b) \\ % & \searrow & & \swarrow & \\ % & {\scriptsize F(f, a) } & F(b,a) & {\scriptsize F(b, f) } & \\ \end{array} \]

Which can be condensed into saying that \[ \pi : \mathfrak a \dinat F \] where we understand \(\mathfrak a\) as the constant profuntor taking everything to \(\mathfrak a\) and all arrows to the identity. Co-wedges are, therefore, dual to wedges in that we have as sides an indexed family \(i_c\) such that: \[ i: F \dinat \mathfrak a \]

Universal Wedges and co-Wedges

Wedges can be composed with arrows, that is, a wedge \(w\) with apex \(\mathfrak a\) can be turned into a wedge \(wf\) – given an arrow \(f:\mathfrak b\to\mathfrak a\) (in \(\cat V\) ) by composing \(\pi\) with \(f\) coordinate-wise and dually, one may precompose a co-wedge \(m\) with apex \(\mathfrak b\) resulting in a co-wedge \(fm\) .

It’s useful to identify the wedges and co-wedges with just their sides, as it gives you all the information you require: the base comes from the codomain, the apex from the domain and the sides are already given. Thus, we’d write \(\pi\circ f\) for a wedge composed with \(f\) and \(f\circ i\) for a co-wedge precomposed with \(f\) .

We can now define universality for (co)-wedges. A universal wedge for \(F\) is some \(\pi:\mathfrak a\to F\) such that any other wedge \(\tau:\mathfrak b\to F\) factors through \(\pi\) through a unique morphism \(\mathfrak b\to\mathfrak a\) . Dually, a universal co-wedge is a co-wedge through which every other co-wedge factors via a co-wedge-unique morphism in \(\cat V\) between their apices.

A universal co-wedge of a functor, if it exists, is often written as \[ \int^{c\in\cat C} F(c,c) \] and the wedge, if any are extant, is written \[ \int_{c\in\cat C} F(c,c) \] and when convenient we drop the category or the variable, whichever makes notation less cumbersome and more likely to pass as analysis to the uninitiated.

(Co) Ends are (Co) Limits

Take a ( \(\Set\) -valued) profunctor \(F:\cat C\proto\cat C\) , it is true that \[ \int_x F(x,x) \iso \mathrm{eq}\left( \prod_{w} F(w,w) \rightrightarrows \prod_{\phi:y\to z} F(y,z) \right) \] first, notice that the second product has a more complicated (but naturally isomorphic) form: \[ \prod_{\phi:y\to z} F(y,z) \iso \prod_{y,z}\prod_{\phi\in\hom(x,y)} F(y,z) \] The two parallel arrows are defined thus, call them \(\lambda\) and \(\rho\) , then given \(y,z\) , \(\phi:y\to z\) and \(\vec x = (x_w\in F(w,w) : w\in\cat C)\) : \[ \lambda_{y,z,\phi}(\vec x) = F(\phi,z)(x_z) \] \[ \rho_{y,z,\phi}(\vec x) = F(y,\phi)(x_y) \] these have associated universal arrows \(\lambda\) and \(\rho\) ; and as such we may ask what is their equalizer.

Proof

We start by realizing that any wedge for \(F\) can be converted into an arrow that equates \(\lambda\) and \(\rho\) – although not necessarily universal among equating arrows –, and every such equating arrow can then be turned into a wedge and this process is an isomorphism.

Start by taking any wedge over \(F\) , thus, a dinatural transformation \(\gamma:a\dinat F\) . It has components \(\gamma_w\) for \(w\in\cat C\) and thus we can get the unique arrow \(\bar\gamma:a\to\prod_wF(w,w)\) such that \(\pi_w\circ\bar\gamma = \gamma_w\) .

To equate \(\lambda\) and \(\rho\) , it suffices and is necessary to equate their projections \(\lambda_{y,z,\phi}\) and \(\rho_{y,z,\phi}\) – thus: \[ \lambda_{y,z,\phi}\circ\bar\gamma = F(\phi,z)\circ\gamma_z \] \[ \rho_{y,z,\phi}\circ\bar\gamma = F(y,\phi)\circ\gamma_y \] which must hold by \(\gamma\) ’s dinaturality – implied by the wedg-y-ness of it. And so any wedge becomes an equating arrow for \(\lambda\) and \(\rho\) .

Conversely, any arrow \(\bar\gamma:a\to\prod_wF(w,w)\) that equates \(\lambda\) and \(\rho\) can then be composed with each projection \(\pi_w\) yielding a dinatural transformation which almost by definition must be a wedge for \(F\) with apex \(a\) . And this process is an isomorphism due to the universality of the product, essentially.

It suffices, then, to show that being the equalizer also makes you the end and vice versa. Take then, the end \(\gamma:a\dinat F\) ; any other equating arrow \(\bar\alpha:b\to\prod_w F(w,w)\) must have an arrow \(f:b\to a\) such that \[ \pi_z\circ\bar\alpha = \gamma_z\circ f \] which is to say \[ \pi_z\circ\bar\alpha = \pi_z\circ\bar\gamma\circ f \] which then implies – by universality of the product – \[ \bar\alpha = \bar\gamma\circ f \] \(f\) being unique among the functions between them by being the only one making that equation hold. Which is the universal property of the equalizer as desired. For any other doing this would be equal to it by the end’s universality.

Conversely, now suppose there is an equalizer \(\bar\gamma:a\to\prod_wF(w,w)\)
– and take any wedge \(\alpha:b\dinat F\) ; by universality of that equalizer, there is only one arrow \(f:b\to a\) such that \[ \bar\alpha = \bar\gamma\circ f \] and then obviously \[ \pi_z\circ\bar\alpha = \pi_z\circ\bar\gamma\circ f \] \[ \alpha = \gamma\circ f \] which is saying that that \(f\) is the unique arrow which factors \(\alpha\) through \(\gamma\) , this time uniqueness comes from the equalizer’s universality.

Corollary 1

Any continuous functor preserves ends – dually, since co-wedges are wedges in the dual category, they will be co-equalizers and thus every co-continuous functor preserves them.

Corollary 2

Recall that \(\Set(\_, y)\) takes limits on \(\dual{\cat C}\) (ie. colimits) to limits. By the previous corollary, it takes co-wedges to wedges, and thus we obtain: \[ \Set\left( \int^x F(x,x), y \right) \iso \int_x \Set(F(x,x), y) \]

Relation to Natural Transformations

Given functors \(F,G:\cat C\to\Set\) , \[ \int_x\Set(F(x),G(x)) \iso \nat(F,G) \]

Proof

Exhibit the above end as an equalizer: its projections, \(\gamma_y\) for \(y\in\cat C\) bundled into an arrow \(\bar\gamma\) targeting the product of \(\Set(F(x),G(x))\) taken over \(x\) . The fact that it equalizes \(\lambda\) with \(\rho\) means that the following are equal: \[ \lambda_{y,z,\phi}\circ\bar\gamma = \Set(F(\phi),\id_z)\circ\gamma_z \] \[ \rho_{y,z,\phi}\circ\bar\gamma = \Set(\id_y,G(\phi))\circ\gamma_y \] let \(\alpha\in\int_x\Set(F(x),G(x))\) and name \(\alpha_w :=\gamma_w(\alpha)\) for the sake of foreshadowing. We thus know that, for each \(\phi:y\to z\) , \[ \alpha_z \circ F(\phi) = \Set(F(\phi),\id_z)(\alpha_z) = \Set(\id_y,G(\phi))(\alpha_y) = G(\phi) \circ \alpha_y \]
which makes \(\alpha_\bullet\) a bona fide natural transformation.

Conversely, any natural transformation yields an element in \(\int_x\Set(F(x),G(x))\) : by definition they equalize \(\lambda\) and \(\rho\) and thus they must be isomorphic, since they both satisfy the same universal property.

We’ll continue this discussion in the Yoneda Electric Boogaloo