Yoneda Lemma

What Representables See

The previous page embedded a locally small category into its category of presheaves by sending each object \(A\) to the presheaf of maps into it, \(H_A = \mathscr{A}(-, A)\). The embedding placed \(\mathscr{A}\) inside the presheaf category \([\mathscr{A}^{\mathrm{op}}, \mathbf{Set}]\), a richly structured world when \(\mathscr{A}\) is small. That page also claimed, without proof, that no information is lost in the passage. This page proves the single result that makes redeeming that claim possible, a result that governs everything that follows. It answers a question that looks innocent and turns out to be the hinge on which the subject swings: inside the presheaf category, what does a representable look like to the rest?

Fix a locally small category \(\mathscr{A}\), an object \(A \in \mathscr{A}\), and an arbitrary presheaf \(X : \mathscr{A}^{\mathrm{op}} \to \mathbf{Set}\). The representable \(H_A\) and the presheaf \(X\) are both objects of \([\mathscr{A}^{\mathrm{op}}, \mathbf{Set}]\), so the maps between them are the maps of that category, namely the natural transformations \(H_A \to X\). We ask what they are. Written in the hom-set notation, the question is to determine the set \[ [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) , \] the collection of natural transformations from the representable \(H_A\) to \(X\). Newcomers to the subject commonly find that this is the first place they get stuck, and the difficulty is usually in grasping what the question asks rather than in any subsequent calculation.

A principle for guessing the answer

There is an informal principle, visible throughout the foundations of the theory, that lets one guess the answer before proving it. The definitions of category, functor, and natural transformation each have the same shape. From input data of one kind, exactly one output of another kind can be built. A composable string of maps yields exactly one composite, and a functor sends a composite to exactly one map. The two paths around a naturality square, likewise, yield exactly one function. Whenever such a forced construction appears, one may reasonably suspect that the set of all constructions of that type is naturally isomorphic to the set of input data, with nothing added or lost.

Apply the principle to the data at hand. Given an object \(A\) and a presheaf \(X\), one set we have just built from them is \([\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X)\). Is there another set constructible from the same data \((A, X)\)? There is, and it is far simpler. Evaluating the presheaf at the object forms the set \(X(A)\). The principle suggests that the elaborate set of natural transformations and the bare set \(X(A)\) should coincide, \[ [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) \cong X(A) . \]

The suggestion is correct, and its confirmation is the lemma named for Yoneda. Stripped of formality, the lemma asserts that a natural transformation \(H_A \to X\) is nothing more nor less than an element of the set \(X(A)\). The entire web of compatible components carries exactly the information of one element, sitting at one object.

The Yoneda Lemma

The informal reading is now made exact. The lemma asserts an isomorphism between the set of natural transformations out of a representable and the value of the presheaf at the representing object. It also asserts that this isomorphism is natural, that is, compatible with variation in both the object and the presheaf. The naturality is not decoration. It carries the structural weight, and we unpack it right after the statement.

Theorem: The Yoneda Lemma

Let \(\mathscr{A}\) be a locally small category. For every object \(A \in \mathscr{A}\) and every presheaf \(X \in [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}]\), there is an isomorphism of sets \[ [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) \cong X(A) , \] natural in \(A\) and in \(X\).

A word on the phrase isomorphism of sets is in order, since it conceals a subtlety. For a merely locally small \(\mathscr{A}\), a natural transformation has one component for each object of \(\mathscr{A}\), and those objects may form a proper class, so the collection of natural transformations between two presheaves need not, in general, be a set. The lemma includes the assertion that when the source is a representable \(H_A\), this collection is a set, indeed one in bijection with \(X(A)\). This is not assumed in advance. The bijection below is constructed by exhibiting explicit maps in each direction without presupposing that the left-hand side is small, so that its smallness is an output of the proof rather than an input to it. No appeal to a universe or to global smallness of \(\mathscr{A}\) is needed.

What naturality in two variables means here

The phrase natural in \(A\) and \(X\) says that each side of the isomorphism is the value of a functor of the pair \((A, X)\), and that the isomorphism is a natural isomorphism between those two functors. Both arguments must therefore be allowed to vary at once. A map \(f : A \to B\) acts on the value side by \(X(f) : X(B) \to X(A)\), in the direction opposite to \(f\), so each side is contravariant in the object variable. The common domain of variation is accordingly \(\mathscr{A}^{\mathrm{op}} \times [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}]\).

The right-hand side is the easier functor to name. Sending a pair \((A, X)\) to the set \(X(A)\) defines the evaluation functor \[ \mathscr{A}^{\mathrm{op}} \times [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}] \to \mathbf{Set}, \quad (A, X) \mapsto X(A) , \] which feeds an object into a presheaf and reads off the resulting set, contravariantly in the object and covariantly in the presheaf.

The left-hand side is the composite that first forms the representable presheaf of \(A\) and then takes natural transformations into \(X\). The Yoneda embedding \(H_\bullet\) supplies the presheaf \(H_A\), and the natural transformations \(H_A \to X\) are then collected, with a map of presheaves acting on this collection by composition on either side, exactly as in the hom-bifunctor of a locally small category. Although the presheaf category itself need not be locally small, the lemma certifies that these particular collections are sets, so the composite is again a functor into \(\mathbf{Set}\). The content of the naturality clause is that this composite is naturally isomorphic to evaluation. Concretely, a map \(X \to X'\) of presheaves must induce a commuting passage between the corresponding sets of natural transformations, \[ [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) \to [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X') , \] matched under the isomorphism with the induced map \(X(A) \to X'(A)\), and likewise, in the reversed direction, for a map in the object variable \(A\). The isomorphism of the lemma is thus required not merely to exist for each fixed pair, but to be chosen compatibly across all of them.

Why so much rides on it

The strength of the statement is easiest to feel by imagining its failure. Take any presheaf \(X\) and manufacture a new presheaf \(X'\) by setting \[ X'(A) = [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) , \] the very set whose identity the lemma settles. This \(X'\) is again a presheaf on \(\mathscr{A}\), acting on a map \(f : A \to B\) by pre-composition with \(H_f\), so the construction may be repeated, producing \(X''\), then \(X'''\), and so on without end. Were the lemma false, this chain could march off through an unbounded sequence of genuinely different presheaves, each built from the last. The lemma collapses the entire sequence at the first step. The presheaf \(X'\) is naturally isomorphic to \(X\), so every presheaf in the chain is the same as the one before it. A construction that threatens to spiral outward forever instead closes immediately, and that closure is what makes the presheaf category tractable rather than wild.

The Proof

The proof is long, but it demands no ingenuity. At each step there is essentially one thing that can be written down, and writing it down is the whole task. Understanding every term in the statement is enough to reconstruct the argument unaided. We build the isomorphism for each fixed pair \((A, X)\) first, then verify that the construction is natural in both variables.

The two maps

Fix \(A \in \mathscr{A}\) and a presheaf \(X\). We must produce a bijection \[ [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) \rightleftarrows X(A) \] and exhibit the two directions as mutually inverse. Write \(\widehat{(\ )}\) for the forward map, carrying a natural transformation to an element of \(X(A)\), and \(\widetilde{(\ )}\) for the backward map, carrying an element of \(X(A)\) to a natural transformation. Four things are then required: define \(\widehat{(\ )}\), define \(\widetilde{(\ )}\), and show that each composite \(\widehat{\widetilde{(\ )}}\) and \(\widetilde{\widehat{(\ )}}\) is the identity.

Proof.

The forward map.
Given a natural transformation \(\alpha : H_A \to X\), there is only one element of \(X(A)\) it can reasonably be sent to. The component of \(\alpha\) at \(A\) is a function \(\alpha_A : H_A(A) = \mathscr{A}(A, A) \to X(A)\), and the domain contains a distinguished element, the identity \(1_A\). Define \[ \widehat{\alpha} = \alpha_A(1_A) \in X(A) . \] There is no other element canonically available, which is the first sign that this map is forced.

The backward map.
Conversely, take an element \(x \in X(A)\). We must build from it a natural transformation \(\widetilde{x} : H_A \to X\), that is, for each object \(B \in \mathscr{A}\) a function \[ \widetilde{x}_B : H_A(B) = \mathscr{A}(B, A) \to X(B) . \] Again there is only one sensible definition. An element of \(\mathscr{A}(B, A)\) is a map \(f : B \to A\). Applying the presheaf \(X\) to it gives a function \(X(f) : X(A) \to X(B)\), into which the element \(x\) may be fed. Set \[ \widetilde{x}_B(f) = \big(X(f)\big)(x) \in X(B) . \] This is well posed because \(X(f)\) maps \(X(A)\) to \(X(B)\) and \(x\) lies in \(X(A)\).

Naturality of \(\widetilde{x}\).
For the family \(\widetilde{x} = (\widetilde{x}_B)_{B \in \mathscr{A}}\) to be a natural transformation, each map \(g : B' \to B\) in \(\mathscr{A}\) must make the square \[ \begin{array}{ccc} \mathscr{A}(B, A) & \xrightarrow{-\circ\, g} & \mathscr{A}(B', A) \\[4pt] {\scriptstyle \widetilde{x}_B}\big\downarrow & & \big\downarrow{\scriptstyle \widetilde{x}_{B'}} \\[4pt] X(B) & \xrightarrow{X(g)} & X(B') \end{array} \] commute, where the top arrow is the action of \(H_A\) on \(g\), namely pre-composition by \(g\), and the bottom is \(X(g)\). Take \(f \in \mathscr{A}(B, A)\). Down-then-across and across-then-down send it, respectively, to \[ \begin{align*} \big(X(g)\big)\big(\widetilde{x}_B(f)\big) &= \big(X(g)\big)\big(\big(X(f)\big)(x)\big) , \\\\ \widetilde{x}_{B'}(f \circ g) &= \big(X(f \circ g)\big)(x) . \end{align*} \] The presheaf \(X\) is contravariant, so it reverses the order of composition, \[ X(f \circ g) = X(g) \circ X(f) , \] and applying both sides to \(x\) shows the two paths agree. The square commutes for every \(g\), so \(\widetilde{x}\) is a genuine natural transformation \(H_A \to X\).

The forward map undoes the backward map.
Starting from an element \(x \in X(A)\), form \(\widetilde{x}\) and then evaluate it by the forward rule. By definition \(\widehat{\widetilde{x}} = \widetilde{x}_A(1_A)\), and the backward construction gives \(\widetilde{x}_A(1_A) = \big(X(1_A)\big)(x)\). A presheaf preserves identities, so \(X(1_A)\) is the identity function on \(X(A)\), and therefore \[ \widehat{\widetilde{x}} = \big(X(1_A)\big)(x) = 1_{X(A)}(x) = x . \] The round trip from \(X(A)\) and back is the identity.

The backward map undoes the forward map.
Starting now from a natural transformation \(\alpha : H_A \to X\), we must show that rebuilding a transformation from its element returns \(\alpha\) itself, that is, \(\widetilde{\widehat{\alpha}} = \alpha\). Two natural transformations agree exactly when all their components agree, so it suffices to prove \(\big(\widetilde{\widehat{\alpha}}\big)_B = \alpha_B\) for every \(B \in \mathscr{A}\). Both sides are functions \(H_A(B) = \mathscr{A}(B, A) \to X(B)\), and two functions agree when they agree on each element of the domain, so it is enough to verify \[ \big(\widetilde{\widehat{\alpha}}\big)_B(f) = \alpha_B(f) \quad \text{for all } f : B \to A . \] Unwinding the left-hand side by the two definitions, \(\widehat{\alpha} = \alpha_A(1_A)\) and the backward construction give \[ \begin{align*} \big(\widetilde{\widehat{\alpha}}\big)_B(f) &= \big(X(f)\big)(\widehat{\alpha}) \\\\ &= \big(X(f)\big)\big(\alpha_A(1_A)\big) , \end{align*} \] so the whole matter reduces to the single identity \[ \big(X(f)\big)\big(\alpha_A(1_A)\big) = \alpha_B(f) . \]

Here naturality of \(\alpha\) is the only tool available, and it is exactly enough. The map \(f : B \to A\) acts on the representable by pre-composition, \(H_A(f) = - \circ f\), and the naturality square of \(\alpha\) at \(f\), \[ \begin{array}{ccc} \mathscr{A}(A, A) & \xrightarrow{-\circ\, f} & \mathscr{A}(B, A) \\[4pt] {\scriptstyle \alpha_A}\big\downarrow & & \big\downarrow{\scriptstyle \alpha_B} \\[4pt] X(A) & \xrightarrow{X(f)} & X(B) \end{array} \] commutes. Tracing the identity \(1_A \in \mathscr{A}(A, A)\) around it gives, along one path, \(\big(X(f)\big)\big(\alpha_A(1_A)\big)\), and along the other, \(\alpha_B(1_A \circ f) = \alpha_B(f)\). The two are therefore equal, which is the required identity. Hence \(\widetilde{\widehat{\alpha}} = \alpha\), and the forward and backward maps are mutually inverse. The bijection \([\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) \cong X(A)\) is established for each fixed pair \((A, X)\).

Naturality in \(X\).
It remains to show the bijection is natural in both variables. We may economize twice. First, for a pair of mutually inverse families it is enough to prove that one of them is natural. A natural transformation whose components are all invertible is a natural isomorphism, and its inverse is then natural by definition, so we check only \(\widehat{(\ )}\). Second, a construction in two variables is natural in the pair precisely when it is natural in each variable separately, the other held fixed. Every map \((f, \theta)\) of the product category factors as \((1, \theta) \circ (f, 1)\), and naturality squares paste along this factorization, so we check the two variables singly.

Fix \(A\) and let \(\theta : X \to X'\) be a map of presheaves. Naturality in \(X\) asks that the square \[ \begin{array}{ccc} [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) & \xrightarrow{\theta \circ -} & [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X') \\[4pt] {\scriptstyle \widehat{(\ )}}\big\downarrow & & \big\downarrow{\scriptstyle \widehat{(\ )}} \\[4pt] X(A) & \xrightarrow{\theta_A} & X'(A) \end{array} \] commute, the top arrow being post-composition with \(\theta\) and the bottom the component \(\theta_A\). For \(\alpha : H_A \to X\), down-then-across yields \(\theta_A(\widehat{\alpha}) = \theta_A\big(\alpha_A(1_A)\big)\), while across-then-down yields \(\widehat{\theta \circ \alpha} = (\theta \circ \alpha)_A(1_A)\). By the definition of composition of natural transformations, \((\theta \circ \alpha)_A = \theta_A \circ \alpha_A\), so the two results coincide and the square commutes.

Naturality in \(A\).
Fix \(X\) and let \(f : B \to A\) be a map in \(\mathscr{A}\). The Yoneda embedding carries \(f\) to a map of presheaves \(H_f : H_B \to H_A\), and composing with it sends a natural transformation \(H_A \to X\) to one \(H_B \to X\), the operation \(- \circ H_f\). On the value side, \(X(f)\) carries \(X(A)\) to \(X(B)\). Naturality in \(A\) asks that \[ \begin{array}{ccc} [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) & \xrightarrow{-\circ\, H_f} & [\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_B, X) \\[4pt] {\scriptstyle \widehat{(\ )}}\big\downarrow & & \big\downarrow{\scriptstyle \widehat{(\ )}} \\[4pt] X(A) & \xrightarrow{X(f)} & X(B) \end{array} \] commute. For \(\alpha : H_A \to X\), the down-then-across path gives \(\big(X(f)\big)\big(\widehat{\alpha}\big) = \big(X(f)\big)\big(\alpha_A(1_A)\big)\), which by the identity already proved equals \(\alpha_B(f)\). The across-then-down path gives \(\widehat{\alpha \circ H_f} = (\alpha \circ H_f)_B(1_B)\). The component of \(H_f\) at \(B\) sends \(1_B\) to \(f \circ 1_B = f\), so this path also gives \(\alpha_B(f)\). The square therefore commutes, and the bijection is natural in \(A\). Naturality in both variables is thus secured, completing the proof.

It is worth pausing on the heart of the argument. The proof that \(\widetilde{\widehat{\alpha}} = \alpha\) showed that the value \(\alpha_A(1_A)\), through the single equation \(\big(X(f)\big)\big(\alpha_A(1_A)\big) = \alpha_B(f)\), already fixes the value of every component \(\alpha_B\) on every map \(f : B \to A\). Nothing about \(\alpha\) is left free once its action on the identity is known. In a phrase:

A natural transformation \(H_A \to X\) is determined by its value at \(1_A\).

This one sentence is the whole of the Yoneda lemma in miniature. The bijection does not merely count the natural transformations and the elements of \(X(A)\) and find the totals equal. It identifies each transformation with the one element it produces at the identity. That element may be chosen freely, and it reconstructs the transformation uniquely. The elaborate compatibility encoded in a natural transformation out of a representable is, in the end, no constraint at all beyond the choice of a single point.

Determined by One Element

The lemma rewards a second look at its own shape. Three readings of the same equation, \([\mathscr{A}^{\mathrm{op}}, \mathbf{Set}](H_A, X) \cong X(A)\), open the doors that the next page walks through in turn.

Read with \(X\) an arbitrary presheaf, the lemma says that a natural transformation \(H_A \to X\) is an element of \(X(A)\). The abstract notion of a map between presheaves thereby becomes the concrete one of an element, and in this form the lemma recasts a representation of a presheaf as the choice of a single universal element. This recasting is the first door, the one that leads to recognizing universal properties wherever a representable appears.

Read with \(X\) itself a representable, say \(X = H_{A'}\), the lemma describes the maps between two representables. Natural transformations \(H_A \to H_{A'}\) correspond to elements of \(H_{A'}(A) = \mathscr{A}(A, A')\), which is to say to maps \(A \to A'\). The Yoneda embedding thus loses no maps and invents none. It is full and faithful once this correspondence is identified with the assignment \(f \mapsto H_f\), so the passage from an object to its presheaf of incoming maps discards nothing. The promise left open at the end of the previous page, that the embedding preserves all information, is the second door.

Read for what it says about objects themselves, the lemma yields a criterion of identity. If two objects look the same through every map into them, that is, if their representable presheaves are isomorphic, then the objects are isomorphic. An object is pinned down, up to isomorphism, by the bare pattern of arrows it receives. What a thing is, categorically, is exhausted by how it is seen. This is the third door. Through it, familiar uniqueness results become instances of one principle, among them the facts that a tensor product, a free construction, and a left adjoint are each determined up to isomorphism by the universal property it satisfies.

One universal element as a compressed encoding

The reading that a representation is a single universal element has a concrete echo in the categorical treatment of data. A database schema can be presented as a small category, with tables as objects and the links between them as maps. A body of data conforming to the schema is then a set-valued functor on that category. It assigns to each table its set of rows and to each link the function that follows it. The representable attached to a table \(A\) is the schema's own description of that single table, and the Yoneda lemma reads as the statement that the natural transformations from this description into a given body of data are exactly the rows that the data stores in table \(A\). The reading holds whichever way round the schema's arrows are taken to run, since the lemma and its dual say the same thing.

A potentially intricate family of compatible components collapses to a plain set of records, with no information added or lost. The same collapse explains why a structured object encoded by its incoming maps can often be summarized by a single distinguished element. When the encoding functor is representable, the whole of it is recoverable from one universal element, and the apparent complexity of the encoding is a compression of that single datum rather than an enlargement of it.

Loading...