Yoneda lemma

Formal statement

Yoneda's lemma concerns functors from a fixed category ${\displaystyle \mathcal{C}}$ to a category of sets, ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$. If ${\displaystyle \mathcal{C}}$ is a locally small category (i.e. the hom-sets are actual sets and not proper classes), then each object ${\displaystyle A}$ of ${\displaystyle \mathcal{C}}$ gives rise to a functor to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$ called a hom-functor. This functor is denoted:

${\displaystyle h_A(-)\equiv \mathrm{H}\mathrm{o}\mathrm{m}(A,-)}$.

The (covariant) hom-functor ${\displaystyle h_A}$ sends ${\displaystyle X\in \mathcal{C}}$ to the set of morphisms ${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(A,X)}$ and sends a morphism ${\displaystyle f:X\to Y}$ (where ${\displaystyle Y\in \mathcal{C}}$) to the morphism ${\displaystyle f\circ -}$ (composition with ${\displaystyle f}$ on the left) that sends a morphism ${\displaystyle g}$ in ${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(A,X)}$ to the morphism ${\displaystyle f\circ g}$ in ${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(A,Y)}$. That is,

${\displaystyle h_A(f)=\mathrm{H}\mathrm{o}\mathrm{m}(A,f),\text{ or}}$

${\displaystyle h_A(f)(g)=f\circ g}$

Yoneda's lemma says that:

Lemma (Yoneda)—Let ${\displaystyle F}$ be a functor from a locally small category ${\displaystyle \mathcal{C}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$. Then for each object ${\displaystyle A}$ of ${\displaystyle \mathcal{C}}$, the natural transformations ${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}(h_A,F)\equiv \mathrm{H}\mathrm{o}\mathrm{m}(\mathrm{H}\mathrm{o}\mathrm{m}(A,-),F)}$ from ${\displaystyle h_A}$ to ${\displaystyle F}$ are in one-to-one correspondence with the elements of ${\displaystyle F(A)}$; rather intuitively, there exists a bijection between ${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(\mathrm{H}\mathrm{o}\mathrm{m}(A,-),F)}$ and ${\displaystyle F(A)}$. That is,

${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}(h_A,F)\cong F(A)}$

Moreover, this isomorphism is natural in ${\displaystyle A}$ and ${\displaystyle F}$ when both sides are regarded as functors from ${\displaystyle \mathcal{C}\times {\mathbf{S}\mathbf{e}\mathbf{t}}^{\mathcal{C}}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$.

Here the notation ${\displaystyle {\mathbf{S}\mathbf{e}\mathbf{t}}^{\mathcal{C}}}$ denotes the category of functors from ${\displaystyle \mathcal{C}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$.

Given a natural transformation ${\displaystyle \mathrm{\Phi }}$ from ${\displaystyle h_A}$ to ${\displaystyle F}$, the corresponding element of ${\displaystyle F(A)}$ is ${\displaystyle u={\mathrm{\Phi }}_A({\mathrm{i}\mathrm{d}}_A)}$; and given an element ${\displaystyle u}$ of ${\displaystyle F(A)}$, the corresponding natural transformation is given by ${\displaystyle {\mathrm{\Phi }}_X(f)=F(f)(u)}$ which assigns to a morphism ${\displaystyle f:A\to X}$ a value of ${\displaystyle F(X)}$.

Contravariant version

There is a contravariant version of Yoneda's lemma, which concerns contravariant functors from ${\displaystyle \mathcal{C}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$ (also known as presheaves). This version involves the contravariant hom-functor

${\displaystyle h^A(-)\equiv \mathrm{H}\mathrm{o}\mathrm{m}(-,A),}$

which sends ${\displaystyle X}$ to the hom-set ${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(X,A)}$. Given an arbitrary contravariant functor ${\displaystyle G}$ from ${\displaystyle \mathcal{C}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$, Yoneda's lemma asserts that

${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}(h^A,G)\cong G(A).}$

Naturality

The bijections provided in the (covariant) Yoneda lemma (for each ${\displaystyle A}$ and ${\displaystyle F}$) are the components of a natural isomorphism between two certain functors from ${\displaystyle \mathcal{C}\times {\mathbf{S}\mathbf{e}\mathbf{t}}^{\mathcal{C}}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$. One of the two functors is the evaluation functor

${\displaystyle -(-):\mathcal{C}\times {\mathbf{S}\mathbf{e}\mathbf{t}}^{\mathcal{C}}\to \mathbf{S}\mathbf{e}\mathbf{t}}$

${\displaystyle -(-):(A,F)\mapsto F(A)}$

that sends a pair ${\displaystyle (f,\mathrm{\Phi })}$ of a morphism ${\displaystyle f:A\to B}$ in ${\displaystyle \mathcal{C}}$ and a natural transformation ${\displaystyle \mathrm{\Phi }:F\to G}$ to the map

${\displaystyle {\mathrm{\Phi }}_B\circ F(f)=G(f)\circ {\mathrm{\Phi }}_A:F(A)\to G(B).}$

This is enough to determine the other functor since we know what the natural isomorphism is. Under the second functor

${\displaystyle \mathrm{Nat}(\mathrm{hom}(-,-),-):\mathcal{C}\times {\mathrm{Set}}^{\mathcal{C}}\to \mathrm{Set},}$

${\displaystyle \mathrm{Nat}(\mathrm{hom}(-,-),-):(A,F)\mapsto \mathrm{Nat}(\mathrm{hom}(A,-),F),}$

the image of a pair ${\displaystyle (f,\mathrm{\Phi })}$ is the map

${\displaystyle \mathrm{Nat}(\mathrm{hom}(f,-),\mathrm{\Phi })=\mathrm{Nat}(\mathrm{hom}(B,-),\mathrm{\Phi })\circ \mathrm{Nat}(\mathrm{hom}(f,-),F)=\mathrm{Nat}(\mathrm{hom}(f,-),G)\circ \mathrm{Nat}(\mathrm{hom}(A,-),\mathrm{\Phi })}$

that sends a natural transformation ${\displaystyle \mathrm{\Psi }:\mathrm{hom}(A,-)\to F}$ to the natural transformation ${\displaystyle \mathrm{\Phi }\circ \mathrm{\Psi }\circ \mathrm{hom}(f,-):\mathrm{hom}(B,-)\to G}$, whose components are

${\displaystyle (\mathrm{\Phi }\circ \mathrm{\Psi }\circ \mathrm{hom}(f,-){)}_C(g)=(\mathrm{\Phi }\circ \mathrm{\Psi }{)}_C(g\circ f)(g:B\to C).}$

Naming conventions

The use of ${\displaystyle h_A}$ for the covariant hom-functor and ${\displaystyle h^A}$ for the contravariant hom-functor is not completely standard. Many texts and articles either use the opposite convention or completely unrelated symbols for these two functors. Alexander Grothendieck's foundational EGA also follows the opposite convention and defines ${\displaystyle h_X(Y)=\mathrm{Hom}(Y,X)}$.

The mnemonic "falling into something" can be helpful in remembering that ${\displaystyle h_A}$ is the covariant hom-functor. When the letter ${\displaystyle A}$ is falling (i.e. a subscript), ${\displaystyle h_A}$ assigns to an object ${\displaystyle X}$ the morphisms from ${\displaystyle A}$ into ${\displaystyle X}$.

Proof

Since ${\displaystyle \mathrm{\Phi }}$ is a natural transformation, we have the following commutative diagram:

This diagram shows that the natural transformation ${\displaystyle \mathrm{\Phi }}$ is completely determined by ${\displaystyle {\mathrm{\Phi }}_A({\mathrm{i}\mathrm{d}}_A)=u}$ since for each morphism ${\displaystyle f:A\to X}$ one has

${\displaystyle {\mathrm{\Phi }}_X(f)=(Ff)u.}$

Moreover, any element ${\displaystyle u\in F(A)}$ defines a natural transformation in this way. The proof in the contravariant case is completely analogous.

The Yoneda embedding

An important special case of Yoneda's lemma is when the functor ${\displaystyle F}$ from ${\displaystyle \mathcal{C}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$ is another hom-functor ${\displaystyle h_B}$. In this case, the covariant version of Yoneda's lemma states that

${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}(h_A,h_B)\cong \mathrm{H}\mathrm{o}\mathrm{m}(B,A).}$

That is, natural transformations between hom-functors are in one-to-one correspondence with morphisms (in the reverse direction) between the associated objects. Given a morphism ${\displaystyle f:B\to A}$ the associated natural transformation is denoted ${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(f,-)}$.

Mapping each object ${\displaystyle A}$ in ${\displaystyle \mathcal{C}}$ to its associated hom-functor ${\displaystyle h_A=\mathrm{H}\mathrm{o}\mathrm{m}(A,-)}$ and each morphism ${\displaystyle f:B\to A}$ to the corresponding natural transformation ${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(f,-)}$ determines a contravariant functor ${\displaystyle h_{\bullet }}$ from ${\displaystyle \mathcal{C}}$ to ${\displaystyle {\mathbf{S}\mathbf{e}\mathbf{t}}^{\mathcal{C}}}$, the functor category of all (covariant) functors from ${\displaystyle \mathcal{C}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$. One can interpret ${\displaystyle h_{\bullet }}$ as a covariant functor:

${\displaystyle h_{\bullet }:{\mathcal{C}}^{\text{op}}\to {\mathbf{S}\mathbf{e}\mathbf{t}}^{\mathcal{C}}.}$

The meaning of Yoneda's lemma in this setting is that the functor ${\displaystyle h_{\bullet }}$ is fully faithful, and therefore gives an embedding of ${\displaystyle {\mathcal{C}}^{\mathrm{o}\mathrm{p}}}$ in the category of functors to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$. The collection of all functors ${\displaystyle \{h_A|A\in C\}}$ is a subcategory of ${\displaystyle {\mathbf{S}\mathbf{e}\mathbf{t}}^{\mathcal{C}}}$. Therefore, Yoneda embedding implies that the category ${\displaystyle {\mathcal{C}}^{\mathrm{o}\mathrm{p}}}$ is isomorphic to the category ${\displaystyle \{h_A|A\in C\}}$.

The contravariant version of Yoneda's lemma states that

${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}(h^A,h^B)\cong \mathrm{H}\mathrm{o}\mathrm{m}(A,B).}$

Therefore, ${\displaystyle h^{\bullet }}$ gives rise to a covariant functor from ${\displaystyle \mathcal{C}}$ to the category of contravariant functors to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$:

${\displaystyle h^{\bullet }:\mathcal{C}\to {\mathbf{S}\mathbf{e}\mathbf{t}}^{{\mathcal{C}}^{\mathrm{o}\mathrm{p}}}.}$

Yoneda's lemma then states that any locally small category ${\displaystyle \mathcal{C}}$ can be embedded in the category of contravariant functors from ${\displaystyle \mathcal{C}}$ to ${\displaystyle \mathbf{S}\mathbf{e}\mathbf{t}}$ via ${\displaystyle h^{\bullet }}$. This is called the Yoneda embedding.

The Yoneda embedding is sometimes denoted by よ, the hiragana Yo.

Representable functor

The Yoneda embedding essentially states that for every (locally small) category, objects in that category can be represented by presheaves, in a full and faithful manner. That is,

${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}(h^A,P)\cong P(A)}$

for a presheaf P. Many common categories are, in fact, categories of pre-sheaves, and on closer inspection, prove to be categories of sheaves, and as such examples are commonly topological in nature, they can be seen to be topoi in general. The Yoneda lemma provides a point of leverage by which the topological structure of a category can be studied and understood.

In terms of (co)end calculus

Given two categories ${\displaystyle \mathbf{C}}$ and ${\displaystyle \mathbf{D}}$ with two functors ${\displaystyle F,G:\mathbf{C}\to \mathbf{D}}$, natural transformations between them can be written as the following end.

${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}(F,G)={\int }_{c\in \mathbf{C}}{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{D}}(Fc,Gc)}$

For any functors ${\displaystyle K:{\mathbf{C}}^{op}\to \mathbf{S}\mathbf{e}\mathbf{t}}$ and ${\displaystyle H:\mathbf{C}\to \mathbf{S}\mathbf{e}\mathbf{t}}$ the following formulas are all formulations of the Yoneda lemma.

${\displaystyle K\cong {\int }^{c\in \mathbf{C}}Kc\times {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{C}}(-,c),K\cong {\int }_{c\in \mathbf{C}}(Kc{)}^{{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{C}}(c,-)},}$

${\displaystyle H\cong {\int }^{c\in \mathbf{C}}Hc\times {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{C}}(c,-),H\cong {\int }_{c\in \mathbf{C}}(Hc{)}^{{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{C}}(-,c)}.}$

Yoneda extension

Let ${\displaystyle \mathcal{C}}$ be a small category, ${\displaystyle F:\mathcal{C}\to \mathcal{D}}$ a functor, and ${\displaystyle [{\mathcal{C}}^{op},\mathbf{S}\mathbf{e}\mathbf{t}]}$ the category of presheaves, its Yoneda extension

${\displaystyle \tilde{F}:[{\mathcal{C}}^{op},\mathbf{S}\mathbf{e}\mathbf{t}]\to \mathcal{D}}$

is the left Kan extension ${\displaystyle {\mathrm{L}\mathrm{a}\mathrm{n}}_{H^{\bullet }}F:[{\mathcal{C}}^{op},\mathbf{S}\mathbf{e}\mathbf{t}]\to \mathcal{D}}$ of ${\displaystyle F}$ along the Yoneda embedding ${\displaystyle H^{\bullet }}$:

${\displaystyle \tilde{F}:={\mathrm{L}\mathrm{a}\mathrm{n}}_{H^{\bullet }}F}$

Preadditive categories, rings and modules

A preadditive category is a category where the morphism sets form abelian groups and the composition of morphisms is bilinear; examples are categories of abelian groups or modules. In a preadditive category, there is both a "multiplication" and an "addition" of morphisms, which is why preadditive categories are viewed as generalizations of rings. Rings are preadditive categories with one object.

The Yoneda lemma remains true for preadditive categories if we choose as our extension the category of additive contravariant functors from the original category into the category of abelian groups; these are functors which are compatible with the addition of morphisms and should be thought of as forming a module category over the original category. The Yoneda lemma then yields the natural procedure to enlarge a preadditive category so that the enlarged version remains preadditive — in fact, the enlarged version is an abelian category, a much more powerful condition. In the case of a ring ${\displaystyle R}$, the extended category is the category of all right modules over ${\displaystyle R}$, and the statement of the Yoneda lemma reduces to the well-known isomorphism

${\displaystyle M\cong {\mathrm{H}\mathrm{o}\mathrm{m}}_R(R,M)}$ for all right modules ${\displaystyle M}$ over ${\displaystyle R}$.

Relationship to Cayley's theorem

As stated above, the Yoneda lemma may be considered as a vast generalization of Cayley's theorem from group theory. To see this, let ${\displaystyle \mathcal{C}}$ be a category with a single object ${\displaystyle \ast }$ such that every morphism is an isomorphism (i.e. a groupoid with one object). Then ${\displaystyle G={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(\ast ,\ast )}$ forms a group under the operation of composition, and any group can be realized as a category in this way.

In this context, a covariant functor ${\displaystyle \mathcal{C}\to \mathbf{S}\mathbf{e}\mathbf{t}}$ consists of a set ${\displaystyle X}$ and a group homomorphism ${\displaystyle G\to \mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}(X)}$, where ${\displaystyle \mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}(X)}$ is the group of permutations of ${\displaystyle X}$; in other words, ${\displaystyle X}$ is a G-set. A natural transformation between such functors is the same thing as an equivariant map between ${\displaystyle G}$-sets: a set function ${\displaystyle \alpha :X\to Y}$ with the property that ${\displaystyle \alpha (g\cdot x)=g\cdot \alpha (x)}$ for all ${\displaystyle g}$ in ${\displaystyle G}$ and ${\displaystyle x}$ in ${\displaystyle X}$. (On the left side of this equation, the ${\displaystyle \cdot }$ denotes the action of ${\displaystyle G}$ on ${\displaystyle X}$, and on the right side the action on ${\displaystyle Y}$.)

Now the covariant hom-functor ${\displaystyle {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(\ast ,-)}$ corresponds to the action of ${\displaystyle G}$ on itself by left-multiplication (the contravariant version corresponds to right-multiplication). The Yoneda lemma with ${\displaystyle F={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(\ast ,-)}$ states that

${\displaystyle \mathrm{N}\mathrm{a}\mathrm{t}({\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(\ast ,-),{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(\ast ,-))\cong {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(\ast ,\ast )}$,

that is, the equivariant maps from this ${\displaystyle G}$-set to itself are in bijection with ${\displaystyle G}$. But it is easy to see that (1) these maps form a group under composition, which is a subgroup of ${\displaystyle \mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}(G)}$, and (2) the function which gives the bijection is a group homomorphism. (Going in the reverse direction, it associates to every ${\displaystyle g}$ in ${\displaystyle G}$ the equivariant map of right-multiplication by ${\displaystyle g}$.) Thus ${\displaystyle G}$ is isomorphic to a subgroup of ${\displaystyle \mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}(G)}$, which is the statement of Cayley's theorem.

History

Yoshiki Kinoshita stated in 1996 that the term "Yoneda lemma" was coined by Saunders Mac Lane following an interview he had with Yoneda in the Gare du Nord station.