Yoneda's Lemma

Euripides

Every man is like the company he is wont to keep.

One of the most consistent philosophies throughout all of category theory is "It's all about the arrows." This is built into the very core of the theory, in that you don't even really need objects to define a category: they are in one-to-one correspondence with the identity arrows!

At a metaphorical level, an arrow $f : c \to c^{'}$ in a category $C$ can be thought of some information that each of $c$ and $c^{'}$ "see" about the other. So for a fixed object $c$ , the collection of all arrows from $c$ is the total information about the category $C$ available to the object $c$ ; or dually, the set of all arrows to a fixed object $c^{'}$ is all information available in the category $C$ about the object $c^{'}$ . From this point of view, what more information could there be about a given object? Nothing. The category is all there is, and in the category the only data are the arrows.

But how does one formalize this idea?

The original inspiration: universal properties

First revisit our pantheon of objects with universal properties. Looking over these examples, a clear pattern emerges. In each case was have an object $c$ in a category $C$ that is characterized by a "universal property," which can always be expressed in the form of a bijection

τ_{d} : {Hom}_{C} (c, d) \tilde{\to} F (d)

that is "natural in $d$ ", where $F : C \to Set$ is some functor. This naturality, often stated but not articulated, is the formal embodiment of the idea that the bijection $τ_{d}$ is defined "in the same way" for every $d \in C$ , or at least "in a compatible way." What that means precisely is that for every arrow $f : d_{1} \to d_{2}$ in $C$ we have a commutative diagram

This is exactly the diagram for a natural transformation.

Examples

For illustration, we recall some specific examples of universal properties.

Coequalizers of set maps

Suppose $X$ and $Y$ are sets. Their disjoint union $X ⊔ Y$ is the set characterized by the universal property that set maps $f : X ⊔ Y \to Z$ are in natural bijection with pairs of set maps $g : X \to Z$ , $h : Y \to Z$ . To put this into the above context, let $F : Set \to Set$ be the functor that assigns:

to each set $Z$ the set $F (Z)$ consisting of all pairs of set maps $g : X \to Z$ , $h : Y \to Z$ ; and
to each set map $p : Z \to W$ the set map $F (p) : F (Z) \to F (W)$ that takes each pair of set maps $g : X \to Z$ , $h : Y \to Z$ the pair of set maps $p \circ g : X \to W$ , $p \circ h : Y \to W$ .
Then there is a bijection that is natural in $Z$ :

τ_{Z} : {Hom}_{Set} (X ⊔ Y, Z) \tilde{\to} F (Z)

Quotients by normal subgroups

Let $N$ be a normal subgroup of a group $G$ . The quotient group $G / N$ , together with its projection morphism $π : G \to G / N$ defined by $g \mapsto g + N$ , satisfies a universal property. Let $F : Grp \to Set$ be the functor that assigns to each group $H$ the set of group morphisms $f : G \to H$ such that $N \leq \ker (f)$ . Then there is a natural bijection

ϕ_{H} : {Hom}_{Grp} (G / N, H) \tilde{\to} F (H) .

Under this bijection, each group morphism $g : G / N \to H$ is sent to the group morphism $g \circ π : G \to H$ .

Direct sums of abelian groups

If $A$ and $B$ are abelian groups, their direct sum is the abelian group $A \oplus B$ . As a set, it consists of all pairs of formal sums $a + b$ with $a \in A$ and $b \in B$ . The operation is defined "component-wise": $(a + b) + (a^{'} + b^{'}) = (a + a^{'}) + (b + b^{'})$ . (Although not common, one could reasonably argue that a different notation should be used for the formal sum symbol, such as $a \oplus b$ .) One can verify that $A \oplus B$ is an abelian group, and that it comes equipped with two injective group morphisms $i_{1} : A \to A \oplus B$ and $i_{2} : B \to A \oplus B$ . Moreover, there is a natural bijection between group morphisms from $A \oplus B$ and pairs of groups morphisms $A \to C$ , $B \to C$ :

ϕ_{C} : {Hom}_{Ab} (A \oplus B, C) \tilde{\to} {(g_{1}, g_{2}) ∣ g_{1} \in {Hom}_{Ab} (A, C), g_{2} \in {Hom}_{Ab} (B, C)}

Under this bijection, each group morphism $f : A \oplus B \to C$ is sent to the pair of group morphisms $f \circ i_{1} : A \to C$ , $f \circ i_{2} : B \to C$ .

Free $R$ -modules

Let $R$ be a ring and $U : R -Mod \to Set$ be the usual forgetful functor. The free module construction takes each set $A$ and produces an $R$ -module $F (A)$ . The function which sends each $a \in A$ to the same element $a \in F (A)$ regarded as a formal $R$ -linear sum of elements of $A$ is an arrow $j : A \to U (F (A))$ . For any other $R$ -module $M$ , each function $f : A \to U (M)$ can be extended uniquely to a module morphism $h : F (A) \to M$ with $f = U (h) \circ j$ .

In the current context, let $G : R -Mod \to Set$ be the functor that assigns to each $R$ -module $M$ the collection of set maps $f : A \to U (M)$ ; i.e., $G (M) = {Hom}_{Set} (A, U (M))$ . Then there is a natural bijection

ϕ_{N} : {Hom}_{R -Mod} (F (A), M) \tilde{\to} G (M) .

From objects to (hom) functors

We first notice that in every universal property, we are always characterizing morphisms from an object (or dually, to an object) in terms of a "natural" bijection with some other info. To make this functorial, consider the following:

Definition of hom functor

For each object $c$ in a given category $C$ , we can define a functor $H_{c} : C \to Set$ as follows:

For each object $d \in C$ , we let $H_{c} (d) = {Hom}_{C} (c, d)$ .
For each arrow $f : d \to d^{'}$ , we let $H_{c} (f) : H_{c} (d) \to H_{c} (d^{'})$ be the set map that takes each morphism $g : c \to d$ to the morphism $f \circ g : c \to d^{'}$ .

It is also common to write ${Hom}_{C} (c, -)$ for $H_{c}$ , but when doing so we will then also write $f \circ -$ for $H_{c} (f)$ , rather than the awkward looking ${Hom}_{C} (c, f)$ .

We should verify that $H_{c}$ is indeed a functor.

First note that for each identity arrow $1_{d}$ in $C$ we have $H_{c} (1_{d}) : H_{c} (d) \to H_{c} (d)$ is the set map that send each arrow $g : c \to d$ to the arrow $1_{d} \circ g : c \to d$ ; since $C$ is a category, we certainly have $1_{d} \circ g = g$ and so $H_{c} (1_{d})$ is the identity map on $H_{c} (d)$ .

Next, for a pair of composable arrows $f_{1} : d_{1} \to d_{2}$ and $f_{2} : d_{2} \to d_{3}$ , we have

H_{c} (f_{2} \circ f_{1}) = (f_{2} \circ f_{1}) \circ - = f_{2} \circ (f_{1} \circ -) = H_{c} (f_{2}) \circ H_{c} (f_{1}) .

More formally, for each object $g \in H_{c} (d_{1})$ (i.e., arrow $g : c \to d_{1}$ ), we have

H_{c} (f_{2} \circ f_{1}) (g) = (f_{2} \circ f_{1}) \circ g,

while

(H_{c} (f_{2}) \circ H_{c} (f_{1})) (g) = f_{2} \circ (f_{1} \circ g) .

By the associativity of composition in $C$ these two are equal.

From the category $C$ to the functor category ${Set}^{C}$

For each object $c \in C$ we have defined a functor $H_{c} : C \to Set$ , which is an object of the functor category ${Set}^{C} .$ Have we actually defined a functor $H : C \to {Set}^{C}$ ? To answer that, we need to specify what $H$ should do to arrows.

To that end, suppose $h : c \to c^{'}$ is an arrow in $C$ . Each arrow from $H_{c}$ to $H_{c^{'}}$ in ${Set}^{C}$ is a natural transformation $τ : H_{c} \Rightarrow H_{c^{'}}$ . This is the data of a family of arrows $τ_{d} : H_{c} (d) \to H_{c^{'}} (d)$ , one for each object $d \in D$ , satisfying the usual naturality condition. So let's consider the sets $H_{c} (d) = {Hom}_{C} (c, d)$ and $H_{c^{'}} (d) = {Hom}_{C} (c^{'}, d)$ .

Given an element $f \in H_{c} (d)$ (i.e., an arrow $f : c \to d$ ), it's not exactly clear how we can use the arrow $h : c \to c^{'}$ to produce an arrow $c^{'} \to d$ , i.e., an element of $H_{c^{'}} (d))$ .

However, there is an obvious way to take an element $f^{'} \in H_{c^{'}} (d)$ (i.e., an arrow $f^{'} : c^{'} \to d$ ) and use the arrow $h : c \to c^{'}$ to produce an arrow $c \to d$ , namely by pre-composing with $h : c \to c^{'}$ .

This defines a set map $τ_{d} : H_{c^{'}} (d) \to H_{c} (d),$ which (we hope) defines a natural transformation $τ : H_{c^{'}} \Rightarrow H_{c}$ . However, this natural transformation is going "the wrong way." In the classical parlance, we would be describing a so-called contravariant functor from $C$ to ${Set}^{C}$ . This language has generally (but not entirely) fallen out of favor and been replaced by the use of the opposite category construction.^[1] In other words, we can use our construction above to define a (covariant) functor^[2]

H : C^{op} \to {Set}^{C} .

Note that the category $C^{op}$ has the same objects as the category $C$ , and each arrow in $C^{op}$ from an object $c$ to an object $c^{'}$ corresponds to an arrow $f : c^{'} \to c$ in $C$ . Because of this, and in an effort to avoid confusion, we often denote arrows in $C^{op}$ by $f^{op} : c \to c^{'}$ , where the corresponding arrow in $C$ is $f : c^{'} \to c$ .

The hom functor

For a given category $C$ , we have defined a functor $H : C^{op} \to {Set}^{C}$ as follows:

For each object $c \in C^{op}$ (which is the same as an object $c \in C$ ), we have $H (c) = H_{c} = {Hom}_{C} (c, -)$ .
For each arrow $h^{op} : c \to c^{'}$ in $C^{op}$ (which corresponds to an arrow $h : c^{'} \to c$ in $C$ ), the natural transformation $H (h^{op}) : H_{c} \Rightarrow H_{c^{'}}$ is defined by "pre-composition with $h$ ," i.e., for each $d \in C$ the set map $H (h^{op})_{d} : H_{c} (d) \to H_{c^{'}} (d)$ is given by sending each arrow $f : c \to d$ to the arrow $f \circ h : c^{'} \to d$ .

Note that the naturality of our supposedly natural transformation follows from the associativity of arrow composition. To see this, suppose $g : d_{1} \to d_{2}$ is an arrow in $C$ and consider the diagram below:

Starting from the top-left, suppose $f \in H_{c} (d_{1})$ , i.e., we have an arrow $f : c \to d_{1}$ . Going over and down yields the arrow $g \circ (f \circ h) : c^{'} \to d_{2}$ , while going down and then over yields the arrow $(g \circ f) \circ h : c^{'} \to d_{2}$ . By associativity of arrow composition in $C$ , these two arrows are equal.

Was this a good idea?

If we hadn't been inspired by the myriad constructions objects with universal properties, this wouldn't seem like a great way to understand objects in a given category $C$ . Arbitrary functors $F : C \to Set$ can presumably be very complicated and difficult to comprehend, and so the category ${Set}^{C}$ of all such functors is huge and mysterious, at least in comparison with the original category $C$ . It would seem impossible that useful knowledge about an object $c \in C$ could be gained from studying the corresponding functor $H_{c} \in {Set}^{C}$ .

Following the general principle of "knowing an object by knowing the maps from it"^[3], we should first examine what we can say about arrows from $H_{c}$ to other objects $F \in {Set}^{C}$ . In other words, we should examine natural transformation $H_{c} \Rightarrow F .$

And here we at last come to it, the great lemma of category theory:

Yoneda's Lemma

Suppose $c$ is an object of a category $C$ and $F : C \to Set$ is a functor. Then there is a bijection between the set of natural transformation $H_{c} \Rightarrow F$ and the set $F (c)$ , given by sending each natural transformation $τ : H_{c} \Rightarrow F$ to the element $τ_{c} (1_{c}) \in F (c)$ .

In other words, there is a bijection

y : {Hom}_{{Set}^{C}} (H_{c}, F) \tilde{\to} F (c) .

We can upgrade this bijection to a full-on natural isomorphism between two functors, but for now let's examine the proof of this lemma.

First suppose $τ : H_{c} \Rightarrow F$ is a natural transformation. This means that for every object $d \in C$ we have a set map $τ_{d} : H_{c} (d) \to F (d)$ . In particular, by taking $d = c$ we have a set map $τ_{c} : H_{c} (c) \to F (c)$ . The domain of this set map is ${Hom}_{C} (c, c)$ which contains (by the axioms of $C$ being category!) a unique identity arrow