The Yoneda Lemma

What Representables See The Yoneda Lemma The Proof Determined by One Element

What Representables See

The previous stage 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 richly structured world \([\mathscr{A}^{\mathrm{op}}, \mathbf{Set}]\), and it was claimed there — without proof — that no information is lost in the passage. Redeeming that claim is the work of this stage, and the single result that makes it possible 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 — 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 almost always 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; a functor sends a composite to exactly one map; the components of a natural transformation are forced by a single naturality condition. 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 — that nothing has been 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: evaluate the presheaf at the object, forming \(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, it 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, and it asserts that this isomorphism is natural — compatible with variation in both the object and the presheaf. The naturality is not decoration; it is the part that carries the structural weight, and we state the bare isomorphism first and the naturality immediately after.

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}\), the objects of the presheaf category form a proper class, and the collection of natural transformations between two presheaves need not, in general, be a set rather than a proper class. 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}, \qquad (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 hom-bifunctor of the presheaf category records the natural transformations \(H_A \to X\). 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}\), 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: \(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 the longest so far, 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 sends it to \(\big(X(g)\big)\big(\widetilde{x}_B(f)\big) = \big(X(g)\big)\big(\big(X(f)\big)(x)\big)\), while across-then-down sends it to \(\widetilde{x}_{B'}(f \circ g) = \big(X(f \circ g)\big)(x)\). 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 suffices to prove \[ \big(\widetilde{\widehat{\alpha}}\big)_B(f) = \alpha_B(f) \qquad \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 \[ \big(\widetilde{\widehat{\alpha}}\big)_B(f) = \big(X(f)\big)(\widehat{\alpha}) = \big(X(f)\big)\big(\alpha_A(1_A)\big) , \] 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, since naturality of an isomorphism transfers to its inverse; we check \(\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; we check the two 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)\); unwinding the component of \(H_f\) at \(B\), which sends \(1_B\) to \(f \circ 1_B = f\), this is \(\alpha_B(f)\) as well. The two paths agree, the square 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 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, and shows that this element may be chosen freely and 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 three doors that the next stage walks through in turn.

Read with \(X\) an arbitrary presheaf, the lemma says that a natural transformation out of a representable is an element of \(X\) at the representing object. This converts the abstract notion of a map between presheaves into the concrete one of an element, and it is the form that recasts a representation of a presheaf as the choice of a single universal element — the door 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 — so the passage from an object to its presheaf of incoming maps discards nothing. The promise left open at the end of the previous stage, that the embedding preserves all information, is the second door, and the next stage proves it outright.

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 — 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, and through it the next stage recovers familiar uniqueness results — that a tensor product, or a free construction, or a left adjoint is determined up to isomorphism by the universal property it satisfies — as instances of one principle.

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, assigning 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\) — a reading that 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 underlies 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.

With the lemma in hand and its three readings identified, the consequences can be drawn. Each reading becomes a theorem at the next stage: representations as universal elements, the Yoneda embedding as a full and faithful embedding, and the identity of objects determined by their representables.