nLab
Yoneda lemma

Idea

The Yoneda lemma is an elementary but deep and central result in category theory and in particular in sheaf and topos theory. It is essential background behind the central concepts of representable functor and universal construction.

Preliminaries

Recall that for $C$ a locally small category and $[C^{\mathrm{op}},\mathrm{Set}](={\mathrm{Set}}^{C^{\mathrm{op}}}=\mathrm{Hom}(C^{\mathrm{op}},\mathrm{Set}))$ the category of presheaves on $C$, there naturally is a functor

$$Y:C\to [C^{\mathrm{op}},\mathrm{Set}]$$Y : C \to [C^op,Set]

– called the Yoneda embedding for reasons explained below – which sends $C$ to the category of presheaves over it: this is just the image of the Hom-functor

$$C(-,-):C^{\mathrm{op}}\times C\to \mathrm{Set}$$C(-,-) : C^op \times C \to Set

under the Hom-adjunction

$$\mathrm{Hom}(C^{\mathrm{op}}\times C,\mathrm{Set})\stackrel{\simeq }{\to }\mathrm{Hom}(C,[C^{\mathrm{op}},\mathrm{Set}])$$Hom(C^{op} \times C, Set) \stackrel{\simeq}{\to} Hom(C, [C^{op}, Set])

in the closed symmetric monoidal category of categories.

Hence $Y$ sends any object $c\in C$ to the presheaf which assigns to any other object $d$ of $c$ the set of morphisms from $d$ into $c$:

$$Y(c):C^{\mathrm{op}}\stackrel{C(-,c)}{\to }\mathrm{Set}.$$Y(c) : C^{op} \stackrel{C(-,c)}{\to} Set \,.

Remarks

One way to appreciate the meaning of this and of what the Yoneda lemma has to say about it is to regard this in the context of space and quantity: thinking of the objects of $C$ as test spaces, presheaves on $C$ are generalized spaces modeled on $C$ which are characterized by the way one can map objects of $C$ into them.

The Yoneda lemma states that the functor $Y$ has good properties which make this interpretation consistent.

The Yoneda Lemma

Let $C$ be a locally small category, $[C^{\mathrm{op}},\mathrm{Set}]$ the category of presheaves on $C$, then for all $c\in C$ there is a canonical isomorphism

$$[C^{\mathrm{op}},\mathrm{Set}](C(-,c),X)\simeq X(c).$$[C^op,Set](C(-,c),X) \simeq X(c) \,.

This is natural in $c$ and $X$, i.e. there is in fact an isomorphism in the functor category $[C^{\mathrm{op}}\times [C^{\mathrm{op}},\mathrm{Set}],\mathrm{Set}]$ between the left and the right side.

Proof

The crucial point is that the naturality condition on any natural transformation $\eta :C(-,c)\Rightarrow X$ is sufficient to ensure that $\eta$ is already entirely fixed by the value ${\eta }_c({\mathrm{Id}}_c)\in F(c)$ of its component ${\eta }_c:C(c,c)\to X(c)$ on the identity morphism ${\mathrm{Id}}_c$. And every such value extends to a natural transformation $\eta$.

More in detail, the bijection is established by the map

$$[C^{\mathrm{op}},\mathrm{Set}](C(-,c),X)\stackrel{{\mid }_c}{\to }\mathrm{Set}(C(c,c),X(c))\stackrel{{\mathrm{ev}}_{{\mathrm{Id}}_c}}{\to }X(c)$$[C^{op}, Set](C(-,c),X) \stackrel{|_{c}}{\to} Set(C(c,c), X(c)) \stackrel{ev_{Id_c}}{\to} X(c)

where the first step is taking the component of a natural transformation at $c\in C$ and the second step is evaluation at ${\mathrm{Id}}_c\in C(c,c)$.

The inverse of this map takes $f\in X(c)$ to the natural transformation ${\eta }^f$ with components

$${\eta }_d^f:=X(-)(f):C(d,c)\to X(d).$$\eta^f_d := X(-)(f) : C(d,c) \to X(d) \,.

Remarks

In the light of the interpretation in terms of space and quantity mentioned above this says that for $X$ a generalized space modeled on $C$, and for $c$ a test space, morphisms from $c$ to $X$ with $c$ regarded as a generalized space are just the morphisms from $c$ into $X$.

Corollaries

The Yoneda lemma has the following direct consequences. As the Yoneda lemma itself, these are as easily established as they are useful and important.

corollary I: Yoneda embedding

The Yoneda lemma implies that the Yoneda embedding functor $Y:C\to [C^{\mathrm{op}},\mathrm{Set}]$ really is an embedding in that it is a full and faithful functor, because for $c,d\in C$ it naturally induces the isomorphism of Hom-sets.

$$[C^{\mathrm{op}},\mathrm{Set}](C(-,c),C(-,d))\simeq (C(-,d))(c)=C(c,d)$$[C^{op},Set](C(-,c),C(-,d)) \simeq (C(-,d))(c) = C(c,d)

corollary II: uniqueness of representing objects

Since the Yoneda embedding is a full and faithful functor, an isomorphism of representable presheaves $Y(c)\simeq Y(d)$ must come from an isomorphism of the representing objects $c\simeq d$:

$$Y(c)\simeq Y(d)\iff c\simeq d$$Y(c) \simeq Y(d) \;\; \Leftrightarrow \;\; c \simeq d

corollary III: universality of representing objects

A presheaf $X:C^{\mathrm{op}}\to \mathrm{Set}$ is representable precisely if the comma category $(Y,{\mathrm{const}}_X)$ has a terminal object. If a terminal object is $(d,f:Y(d)\to X)\simeq (d,f\in X(d))$ then $X\simeq Y(d)$.

This follows from unwrapping the definition of morphisms in the comma category $(Y,{\mathrm{const}}_X)$ and applying the Yoneda lemma to find

$$(Y,{\mathrm{const}}_X)((c,f\in X(c)),(d,g\in X(d)))\simeq \{u\in C(c,d):X(u)(g)=f\}.$$(Y,const_X)((c,f \in X(c)), (d, g \in X(d))) \simeq \{ u \in C(c,d) : X(u)(g) = f \} \,.

Hence $(Y,{\mathrm{const}}_X)((c,f\in X(c),(d,g\in X(d)))\simeq \mathrm{pt}$ says precisely that $X(-)(f):C(c,d)\to X(c)$ is a bijection.

Interpretation

For emphasis, here is the interpretation of these three corollaries in words:

• corollary I says that the interpretation of presheaves in $C$ as generalized objects probeable by objects of $c$ is consistent: the probes of $X$ by $c$ are indeed the maps of generalized objects from $c$ into $X$;

• corollary II says that probes by objects of $C$ are sufficient to distinguish objects of $C$: two objects of $C$ are the same if they have the same probes by other objects of $C$.

• corollary III characterizes representable functors by a universal property and is hence the bridge between the notion of representable functor and universal constructions.

Generalizations

The Yoneda lemma tends to carry over to all important generalizations of the context of categories:

• There is an analog of the Yoneda lemma in enriched category theory.

• In the context of modules (see also Day convolution) the Yoneda lemma becomes the important statement of Yoneda reduction, which identifies the bimodule ${\mathrm{hom}}_C(-,-)$ as a unit bimodule.

• There is a Yoneda lemma for bicategories.

• There is a Yoneda lemma for (∞,1)-categories.

• In functional programming?, the Yoneda embedding is the continuation passing style? transform.

Related constructions

• Yoneda reduction

• co-Yoneda lemma

Applications

• The Yoneda lemma is the or a central ingredient in various reconstruction theorems, such as those of Tannaka duality.

• In its incarnations as Yoneda reduction the Yoneda lemma governs the algebra of ends and coends and hence that of bimodules and profunctors.

References

• Tom Leinster, The Yoneda Lemma: What's it all about?

A discussion of the Yoneda lemma from the point of view of universal algebra is in

• Vaughan Pratt, The Yoneda lemma without category theory: algebra and applications (pdf)