Yoneda reduction



The term Yoneda reduction is was coined by Todd Trimble in his (unpublished) thesis. It refers to a technique based on the Yoneda lemma for performing a number of end and coend calculations which arise in coherence theory and enriched category theory.

The module perspective on the Yoneda lemma

There are various formulations of the Yoneda lemma. One says that given a presheaf F:C opSetF: C^{op} \to Set, there is a canonical isomorphism

F(c)Nat(hom C(,c),F)F(c) \cong Nat(\hom_C(-, c), F)

where “Nat” refers to the set of natural transformations between presheaves C opSetC^{op} \to Set; in other words, the hom

Set C op(hom C(,c),F)Set^{C^{op}}(\hom_C(-, c), F)

appropriate to the presheaf category.

There is an VV-enriched category version, whenever CC is a category enriched in a complete, cocomplete, symmetric monoidal closed category VV. Here “Nat” is constructed as an enriched end (an example of a weighted limit):

V C op(C(,c),F)= dF(d) C(d,c)V^{C^{op}}(C(-, c), F) = \int_d F(d)^{C(d, c)}

and therefore the enriched Yoneda lemma gives an isomorphism

F(c) dF(d) C(d,c)(1)F(c) \cong \int_d F(d)^{C(d, c)} \qquad (1)

which is (VV-)natural in cc; we may therefore write

F() dF(d) C(d,)(2)F(-) \cong \int_d F(d)^{C(d, -)} \qquad (2)

and this isomorphism is VV-natural in FF.

We pause to give an instance of the Yoneda lemma which is both familiar and which serves to inform much of the module-theoretic terminology in the discussion below. Let V=AbV = Ab; let RR be a ring (conceived as an AbAb-enriched category with exactly one object \bullet). Then Ab R opAb^{R^{op}} is the (AbAb-enriched) category of right RR-modules, or equivalently, left R opR^{op}-modules). The presheaf hom R(,)\hom_R(-, \bullet) is just the underlying abelian group of RR seen as a right module over the ring RR, also known as the regular representation.

The first formulation (1) of the Yoneda lemma would simply say that at the level of abelian groups, we have for any right RR-module MM

M()RightMod R(R,M)M(\bullet) \cong RightMod_R(R, M)

Further taking into account the “naturality” in the argument bullet, the formulation (2) says that actually we have an isomorphism at the level of right RR-modules

MRightMod R(R,M)M \cong RightMod_R(R, M)

where the module structure on the right side arises by considering the argument RR now as a bimodule over the (ring) RR.

The (enriched) Yoneda lemma is nothing but a far-reaching extrapolation of this basic isomorphism: it says

FRightMod C(hom C,F)F \cong RightMod_C(\hom_C, F)

where the CC-presheaf or right CC-module hom on the right is appropriately constructed as an enriched end, and hom C:C opCV\hom_C: C^{op} \otimes C \to V is a treated as a VV-enriched “bimodule” over CC, and plays the role of the “regular representation” of CC.

Calculus of bimodules

The analogy between presheaves and modules can be pursued considerably further. Again, we start with the perhaps more familiar context of rings and modules.

In the first place, given a ring RR, there is a familiar monoidal category of RR-bimodules (and bimodule morphisms). If M,NM, N are bimodules over RR, with left RR-actions denoted by λ\lambda‘s and the right actions by ρ\rho’s, their tensor product M RNM \otimes_R N, defined by the coequalizer

MRNMNM RNM \otimes R \otimes N \stackrel{\to}{\to} M \otimes N \to M \otimes_R N

(where the two parallel arrows are MλM \otimes \lambda, ρ×N\rho \times N) carries an evident RR-bimodule structure. Each of the functors M RM \otimes_R - and RN- \otimes_R N admits a right adjoint expressed by natural isomorphisms of abelian groups

Bimod(N,Left R(M,Q))Bimod(M RN,Q)Bimod(M,Right R(N,Q))Bimod(N, Left_R(M, Q)) \cong Bimod(M \otimes_R N, Q) \cong Bimod(M, Right_R(N, Q))

where Left R(M,Q)Left_R(M, Q) denotes the abelian group of left RR-module maps MQM \to Q, equipped with its natural RR-bimodule structure; Right(N,Q)Right(N, Q) is similar. Thus the monoidal category of RR-bimodules is biclosed.

More generally, there is a bicategory whose objects or 0-cells are rings R,S,R, S, \ldots, and whose morphisms or 1-cells RSR \to S are left RR-, right SS-bimodules. 2-cells are homomorphisms of bimodules. If M:RSM: R \to S and N:STN: S \to T are bimodules, then their bimodule composite is M SN:RTM \otimes_S N: R \to T. This too is a biclosed bicategory, meaning that

This generalized module theory can be pursued much further.

(Lost a bunch of work, due to vagaries of computers. Sigh. Will return later.)


Relative coherence theorem for symmetric monoidal categories

If VV is symmetric monoidal, then the monoid of endomorphisms on the nn-fold tensor functor

n:V nV\bigotimes^n: V^{\otimes n} \to V

is in bijection with the monoid of endomorphisms on the unit object II.


By fully and faithfully embedding VV (as a symmetric monoidal category) into Set V opSet^{V^{op}}, we may without loss of generality suppose VV is complete, cocomplete, symmetric monoidal closed.

The result is by induction on nn: observe that a map

x 1x 2x nx 1x 2x nx_1 \otimes \x_2 \otimes \ldots \otimes x_n \to x_1 \otimes x_2 \otimes \ldots \otimes x_n

natural in all the arguments x ix_i, in particular in x nx_n, corresponds to a map dinatural in x nx_n:

x 1x n1x 1x n1x n) x nx_1 \otimes \ldots \otimes x_{n-1} \to x_1 \otimes \ldots \otimes x_{n-1} \otimes x_n)^{x_n}

and hence to a map to the end

x 1x n1 x n(x 1x n1x n) x n Ix_1 \otimes \ldots \otimes x_{n-1} \to \int_{x_n} (x_1 \otimes \ldots \otimes x_{n-1} \otimes x_n)^{x_{n}^{I}}

where the end exists and is isomorphic to

x 1x n1Ix 1x n1x_1 \otimes \ldots \otimes x_{n-1} \otimes I \cong x_1 \otimes \ldots \otimes x_{n-1}

by Yoneda reduction. This completes the induction.

(It’s been ages since I’ve thought about this. I need to think through the argument carefully again.)

Blog resources

Todd Trimble talks about Yoneda reduction on the nnCafé here.

Revised on March 30, 2011 07:32:44 by Urs Schreiber (