8. Yoneda’s Lemma

8.1. Presheaves

Recall that, given two objects \(A, B\) in a category \(\mathcal C\), the collection of morphisms from \(A\) to \(B\) may be denoted by \(\mathrm{Hom}_{\mathcal C}(A, B)\). However, we will often use the more convenient notation, \(\mathcal C(A, B) := \mathrm{Hom}_{\mathcal C}(A, B)\), which is also quite standard.

Let us recall a few definitions from Chapter 7.

A category is called

• small if the collection of all morphisms is a set (as opposed to a class),
• locally small if for every pair \(A\), \(B\) of objects in \(\mathcal C\), the collection \(\mathcal C(A, B)\) is a set.

Many categories that come up in practice are locally small. For functor categories, however, this is often not the case. Nonetheless, if \(\mathcal C\) is small and \(\mathcal D\) is locally small, then the functor category \(\mathcal D^{\mathcal C}\) is locally small. Indeed, the components of the natural transformations are indexed by the objects of \(\mathcal C\); so, given two functors \(\mathcal F, \mathcal{G}: \mathcal C\to \mathcal D\) (objects in \(\mathcal D^{\mathcal C}\)), the collection \(\mathcal D^{\mathcal C}(\mathcal F, \mathcal{G})\) of natural transformations (morphisms in \(\mathcal D^{\mathcal C}\)) from \(\mathcal F\) to \(\mathcal G\) is a set.

Let \(\mathcal C\) be a locally small category.

The elements of \(\mathbf{Set}^{\mathcal C^{\mathrm{op}}}\) are called presheaves on \({\mathcal C}\); it is a category whose objects are contravariant functors from \({\mathcal C}\) to \(\mathbf{Set}\) and whose morphisms are natural transformations between such functors.

Intuitively we may think of the category \({\mathcal C}\) as a catalogue from from a shop that sells ready-to-assemble hardware or furniture. Every object of \({\mathcal C}\) is a page of the catalogue showing one kind of objects for sale, for example a screw, a rod, or a panel. The morphisms of \({\mathcal C}\) are building instructions specifying how the components can be assembled: for example it may specify that a screw can be fitted at either ends of a rod by having two morphisms from the screw object to the rod object.

For example the category of directed graphs \(\mathbf{Grph}\) can be seen as a presheaf category. A catalogue for the construction of graphs is the simple category \(\mathsf{grph}\) (the identity morphisms are not shown):

This catalogue has just two pages showing that there are two kinds of objects that we can order, one denoted by \(v\) (for vertices) and the other denoted by \(e\) (for edges). The two arrows indicate that a vertex can be mounted at either the source or the target of an edge.

When we order from a catalogue, we must specify how many items for each kind of object we want. This is done by mapping each object to a set: for example, if we want a graph with four vertices and five edges, we will map \(v\) to a set with four elements, say \(V = \{v_0,v_1,v_2,v_3\}\) and \(e\) to a set with five elements, say \(E = \{e_0,e_1,e_2,e_3,e_4\}\). We must also state how we are going to assemble the graph: for every edge we must specify which vertices we are going to mount as its source and target. We are allowed to reuse the vertices multiple times, a vertex can be used as source of several edges and target of several other edges, an edge can even use the same vertex both as its source and target. So we need two functions \(\mathsf{source},\mathsf{target}: E \rightarrow V\). Notice that these functions go in the opposite direction with respect to the arrows in \(\mathsf{grph}\): the arrows \(s\) and \(t\) describe how the the vertices can be mounted on the edges, the functions \(\mathsf{source}\) and \(\mathsf{target}\) state which vertices are mounted on each edge.

In conclusion, a full specification of a graph (an order from the catalogue) is a contravariant functor \(G:\mathsf{grph}^{\mathrm{op}}\rightarrow \mathbf{Set}\), that is, a presheaf on \(\mathsf{grph}\).

As an exercise, check that given two presheaves \(G_1, G_2: {\mathbf{Set}}^{\mathsf{grph}^{\mathrm{op}}}\), the natural transformations between them exactly describe the graph morphisms. This shows that the category \(\mathbf{Grph}\) is isomorphic to \({\mathbf{Set}}^{\mathsf{grph}^{\mathrm{op}}}\).

8.2. Representable functors

Imagine now that we want to order a single item from a catalogue. For example we want to order just a single edge. So we want a presheaf \(G: {\mathbf{Set}}^{\mathsf{grph}^{\mathrm{op}}}\) such that \(G e\) is a singleton set.

Since the mounting instructions (the arrows in \(\mathsf{grph}\)) prescribe that every edge must have a source and a target, we are forced to order also two vertices. (We could order a single vertex and use it in both positions, but we’re going to do the order in a free way and use a single component for every required position.) There is a clever way to do this: define \(G\) as the functor that maps every object \(x\) to the set of morphism \(\mathsf{grph}(x,e)\). We get indeed that \(G e = \mathsf{grph}(e,e)\) is a singleton set containing just \(\mathrm{id}_e\) and \(G v = \mathsf{grph}(v,e)\) contains two elements \(s\) and \(t\).

In general this kind of single-item order is called a representable functor.

A representable (contravariant) functor in \({\mathbf{Set}}^{\mathcal{C}^{\mathrm{op}}}\) is a presheaf of the form \(\mathcal C(\underline{\phantom{x}},B)\), for some object \(B\) in \(\mathcal C\), as diagrammed below.

Here \(f\) is a morphism from \(A\) to \(A'\) in \(\mathcal{C}^{\mathrm{op}}\), which is the same as a morphism from \(A'\) to \(A\) in \(\mathcal{C}\).

Dually, we can fix the domain rather than the codomain of morphisms. A representable (covariant) functor from \(\mathcal C\) to \(\mathbf{Set}\) is a functor of the form \(\mathcal C(A, \underline{\phantom{x}})\), for some object \(A\) in \(\mathcal C\), as diagrammed below.

The standard notation for functors is “overloaded,” which can be a bit unsettling, especially when trying to compute with such things. Indeed, the functor \(\mathcal C(A, \underline{\phantom{x}})\) takes arguments of two distinct types—namely, objects from \(\mathcal C_{\mathrm{obj}}\) on the one hand, and morphisms from \(\mathcal C_{\mathrm{mor}}\) on the other.

To facilitate computing with functors, we make the typing rules less ambiguous by writing \(λ (x : \mathcal C_{\mathrm{obj}} + \mathcal C_{\mathrm{mor}}). \mathcal C(A, x)\). Then objects and morphisms are passed in as \(\mathrm{inl}\, B\) and \(\mathrm{inr}\,f\), respectively, and the action of \(\mathcal C(A, \underline{\phantom{x}})\) can be described in the following way:

• On objects

  Each \(B : \mathcal C_{\mathrm{obj}}\) is mapped to \((λ x . \mathcal C(A, x)) (\mathrm{inl}\, B) = \mathcal C(A, \mathrm{inl}\, B)\), the set of morphisms from \(A\) to \(B\).

• On morphisms

  Each \(f\colon \mathcal C(B, B')\) is mapped to the set map \(\mathcal C(A, \mathrm{inr}\, f)\), which is an object in \(\mathbf{Set}\bigl(\mathcal C(A, B), \mathcal C(A, B')\bigr)\) that takes each \(g : \mathcal C (A, B)\) to the morphism \(f g\). That is,

  \[\mathcal C(A, \mathrm{inr}\, f)(g) = (λ x . \mathcal C(A, x)) (\mathrm{inr}\, f) (g) =f g : \mathcal C(A, B').\]

The action of \(\mathcal C(A, \underline{\phantom{x}})\) on morphisms is illustrated in the diagram below.

The functor \(\mathcal C(A, \underline{\phantom{x}}) : \mathcal C_{\mathrm{obj}} + \mathcal C_{\mathrm{mor}} \to \mathbf{Set}\) has a dual, namely, \(\mathcal C(\underline{\phantom{x}}, B) : \mathcal C_{\mathrm{obj}} + \mathcal C_{\mathrm{mor}}^{\mathrm{op}} \to \mathbf{Set}\) defined as follows: [1]

An object \(A\) is mapped to the set \(\mathcal C(\mathrm{inl} A, B)\).

A morphism \(f\) in \(\mathcal C^{\mathrm{op}}\) with source \(A\) and target \(A'\), is mapped to \(\mathcal C(\mathrm{inr} f, B) : \mathcal C(A, B) \to \mathcal C(A', B)\).

The latter takes \(g : A\to B\) to \(\mathcal C(\mathrm{inr} f, B)(g) = gf : A' \to B\).

---

8.3. Yoneda embedding

Representable functors allow us to embed any category \(\mathcal{C}\) into the category of presheaves over it. This is a very useful fact, since the category \(\mathbf{Set}^{\mathcal C^{\mathrm{op}}}\) is a topos, which is a mathematical universe with its own internal logic; such categories underlie many important constructions. We will study them in a later chapter.

The (covariant) Yoneda embedding is a functor from a category \(\mathcal{C}\) to the category of presheaves over it, diagrammed as follows:

---

Exercise 8.3.1: Prove for every morphism \(f\) that \(Y_f\) is a natural transformation. Prove that \(Y_{-}\) is a functor.

---

We will prove that \(Y_{-}\) is an embedding; that is,

1. \(Y_{-}\) is injective on objects and
2. \(Y_{-}\) is full and faithful (bijective on hom-sets).

So, \(Y_{-}\) makes \(\mathcal C\) a subcategory of the category \(\mathbf{Set}^{\mathcal C^{\mathrm{op}}}\) of presheaves on \(\mathcal C\).

---

The contravariant Yoneda embedding is diagrammed as follows:

---

Example 8.1

In the first example of Section 7.1 we defined the simplex category \(\Delta\). A compact graphical representation of \(\Delta\) is

where only the generating face and degeneracy morphisms are shown.

Presheaves over \(\mathcal \Delta\), that is objects of \(\mathbf{Set}^{\Delta^{\mathrm{op}}}\), are called a simplicial sets.

Using the order-catalogue metaphor, \(\mathcal \Delta\) is a catalogue with an infinite number of pages, each offering a geometric component of a different dimension: points, lines, triangles, tetrahedra, higher-dimension triangles.

These are simply denoted by numbers: \(\bar{1}\) is the catalogue page for a point, \(\bar{2}\) is the page for a line, \(\bar{3}\) is the page for a triangle, and so on. Ordering from the catalogue means specifying how many components of each shape we want: for example 10 points, 7 lines, 5 triangles, 2 tetrahedra, and so on. This is done by mapping each page \(\bar{n}\) to a set \(X_n\).

As in the case for graphs, the arrows in the catalogue-category \(\mathcal \Delta\) prescribe how the components can be assembled.

The two arrows from \(\bar{1}\) to \(\bar{2}\) tell us that a point can be mounted at either end of a line; the four arrows from \(\bar{3}\) to \(\bar{4}\) tell us that a triangle can be mounted on any of the four faces of a tetrahedron, and so on. The corresponding functions between the simplicial sets, for example the four functions between \(X_4\) and \(X_3\) map each tetrahedron to its four faces.

(There are some extra things in \(\mathcal \Delta\) that don’t fit too well with this intuitive description: the initial object \(\bar{0}\) and the degeneracy arrows going back from a component to the previous one. They have a technical importance but are not essential, let’s ignore them in this metaphorical explanation.)

Intuitively, a simplicial set is a geometric object constructed with simplices; i.e., \(n\)-dimensional triangles.

If \(X : \Delta^{\mathrm{op}} \to \mathbf{Set}\), think of \(X_n\) as the set of simplices of dimension \(n-1\).

In \(X_1\) there are points; in \(X_2\), lines; \(X_3\), triangles; \(X_4\) tetrahedra, etc.

The images of the face maps tell us how the simplices are glued together.

The representable simplicial sets, given by the Yoneda embedding, are the standard simplices. For example, if we want to order just a single triangle, we can do it by the presheaf \(Y_3\). As in the case of graphs, we also need to order the necessary subcomponents, three points for the vertices of the triangle and three lines for its sides. (There will also be a number of degenerate components that need to be ordered even if they don’t do anything useful!)

---

8.4. Yoneda’s Lemma

Now imagine that I intend to make such a simple order of a single triangle \(Y_3\). It just happens that my friend Alice has recently made a big order from the shop herself, buying many triangles and other components of various dimensions. That is, Alice has made an order based on a presheaf \(X: \mathbf{Set}^{\Delta^{\mathrm{op}}}\). She offers to lend me what I need and I can choose any of her triangles from \(X_3\). Of course, I will need to borrow from her also the required subcomponents: three points from \(X_1\), three lines from \(X_2\) and all the degenerate components. I must do this in a way that guarantees that the components are assembled in the way I need them to be. This all can be expressed by saying that my borrowing from Alice is a natural transformation from \(Y_3\) to \(X\).

You may think this is a rather complex thing to do: I must specify for each dimension which simplices of that dimension I’m borrowing from Alice, making sure that they are mounted in the correct way. But in fact the task turns out to be much simpler than expected: Once I’ve chosen the main triangle that I want from \(X_3\), everything else follows automatically: of course I will have to choose from \(X_2\) exactly the three lines that Alice used as sides for that triangle, and similarly for the points and all the degenerate components. In short, the whole natural transformation is determined by a single choice from \(X_3\). This is the content of the famous Yoneda Lemma, probably the most important result in Category Theory.

The Yoneda Lemma says that if we take a functor \(F : \mathcal C^{\mathrm{op}} \to \mathbf{Set}\) and an object \(B\) of \(\mathcal C\), then the set \(\mathrm{Nat}(Y_B, F)\) of natural transformations from \(Y_B = \mathcal C(-, B)\) to \(F\) is naturally isomorphic to \(FB\).

Theorem:

(Yoneda’s Lemma) For every object \(B\) of \(\mathcal C\) and functor (presheaf) \(F : \mathcal C^{\mathrm{op}} \to \mathbf{Set}\), we have \(\mathrm{Nat}(Y_B, F) \cong FB\), and this isomorphism is natural in \(B\) and \(F\).

Proof:

(\(\Rightarrow\)) Given \(\alpha \in \mathrm{Nat}(Y_B, F)\), we construct \(x_\alpha \in FB\).

Define \(x_\alpha = \alpha_B(\mathrm{id}_B)\).

(\(\Leftarrow\)) Given \(x \in FB\), we construct \(\alpha_x \in \mathrm{Nat}(Y_B, F)\).

Define \((\alpha_x)_X = \lambda f. Ff(x)\). To complete the proof, we must check the naturality of the isomorphism in \(B\) and \(F\). This is left as an exercise.

---

Exercise 8.4.1: Check the naturality of the isomorphism in \(B\) and \(F\) in the previous proof.

---

Exercise 8.4.2: Verify that \(Y_v\) represents the graph with a single vertex and no edges and \(Y_e\) represents the graph with two distinct vertices and a single edge between them.

---

8.5. Solutions

Exercise 8.3.1

Solution (to do).

---

Exercise 8.4.1

Solution (to do).

---

Exercise 8.4.2

Solution (to do).

---

Footnotes

[1]	Note that \(\mathcal C_{\mathrm{obj}}^{\mathrm{op}} = \mathcal C_{\mathrm{obj}}\). Also, \(\mathcal C^{\mathrm{op}}(A, B) = \mathcal C(B, A)\).