The Yoneda Lemma

Fix a locally small category $\mathcal{A}$, an object $A$, and a presheaf $X:{\mathcal{A}}^{\mathrm{op}}\to \mathbf{Set}$. The representable presheaf$H_A=\mathcal{A}(-,A)$ and the arbitrary presheaf $X$ are both objects of the functor category $[{\mathcal{A}}^{\mathrm{op}},\mathbf{Set}]$, so it makes sense to ask what the maps between them are. The maps are natural transformations, and they form the set $[{\mathcal{A}}^{\mathrm{op}},\mathbf{Set}](H_A,X)$. The Yoneda lemma identifies this set exactly.¹

The answer is guessable from an informal principle: from a piece of input data there is usually only one output of a given type that can be built. The input here is a pair $(A,X)$. One set built from it is the collection of natural transformations $H_A\to X$. Another is $X(A)$ itself, obtained by evaluating $X$ at $A$. The principle suggests these are the same set, and they are.

Informally: a natural transformation $H_A\to X$ is an element of $X(A)$. The lemma holds equally in covariant form, with $H^A=\mathcal{A}(A,-)$ and a covariant $X:\mathcal{A}\to \mathbf{Set}$; the statement above uses presheaves to match the Yoneda embedding.

The explicit bijection

The bijection has an explicit form. Given a natural transformation $\alpha :H_A\to X$, its component at $A$ is a function ${\alpha }_A:H_A(A)=\mathcal{A}(A,A)\to X(A)$. Feed it the one canonical element of $\mathcal{A}(A,A)$, the identity $1_A$, and record the result.

The formula for ${\tilde{x}}_B$ is forced: $x$ lives in $X(A)$, a map $f:B\to A$ gives $X(f):X(A)\to X(B)$, and applying it to $x$ is the only element of $X(B)$ that $f$ and $x$ produce. The Yoneda lemma asserts that $\widehat{(-)}$ and $\widetilde{(-)}$ are mutually inverse bijections, natural in $A$ and $X$. The proof does four things: define each map (done above), then check each composite is an identity.

The proof

The map $\tilde{x}$ is natural. For a map $g:B_0\to B$ in $\mathcal{A}$, naturality of $\tilde{x}$ is the square below, whose top edge is $H_A(g)=-\circ g$ and whose bottom edge is $X(g)$.

Chasing $f\in \mathcal{A}(B,A)$: the top-then-right route gives ${\tilde{x}}_{B_0}(f\circ g)=(X(f\circ g))(x)$, and the left-then-bottom route gives $(X(g))({\tilde{x}}_B(f))=(X(g)\circ X(f))(x)$. Functoriality $X(f\circ g)=X(g)\circ X(f)$ makes the two equal, so the square commutes and $\tilde{x}$ is a genuine natural transformation.

The composite $\hat{\tilde{x}}=x$. Directly,

using $X(1_A)=1_{X(A)}$.

The composite $\tilde{\hat{\alpha }}=\alpha$. Two natural transformations agree iff all components agree, and two functions agree iff they agree on every element, so it suffices to fix $B$ and $f:B\to A$ and show ${\tilde{\hat{\alpha }}}_B(f)={\alpha }_B(f)$. The left side unfolds to

so the claim is $(X(f))({\alpha }_A(1_A))={\alpha }_B(f)$. This is exactly what naturality of $\alpha$ supplies. Naturality of $\alpha$ at the map $f:B\to A$ is the square

evaluated at $1_A\in H_A(A)$. The top edge $H_A(f)=-\circ f$ sends $1_A$ to $1_A\circ f=f$, so the right-then-down route is ${\alpha }_B(f)$; the left-then-down route is $(X(f))({\alpha }_A(1_A))$; commutativity equates them. (In the figure the components ${\alpha }_A,{\alpha }_B$ are labelled $a_A,a_B$.) This establishes the bijection for each fixed $A$ and $X$.

The chase records the structural content of the lemma:

Naturality in both variables

The bijection is not merely one bijection per pair $(A,X)$; the whole family is natural. By a standard lemma it is enough to check naturality of one of the two maps, and by another it is enough to check naturality separately in each variable. Take $\widehat{(-)}$.

• Naturality in $A$. A map $f:B\to A$ induces $-\circ H_f$ on transformations and $X(f)$ on values, and for $\alpha :H_A\to X$, $$(\alpha \circ H_f{)}_B(1_B)={\alpha }_B((H_f{)}_B(1_B))={\alpha }_B(f\circ 1_B)={\alpha }_B(f)=(X(f))({\alpha }_A(1_A)),$$ the last step by the identity-arrow computation above. So the naturality square in $A$ commutes.
• Naturality in $X$. A map $\theta :X\to X^{\prime }$ of presheaves induces $\theta \circ -$ on transformations and ${\theta }_A$ on values, and $$\widehat{\theta \circ \alpha }=(\theta \circ \alpha {)}_A(1_A)={\theta }_A({\alpha }_A(1_A))={\theta }_A(\hat{\alpha }),$$ using componentwise composition in $[{\mathcal{A}}^{\mathrm{op}},\mathbf{Set}]$. So the naturality square in $X$ commutes.

Both squares commute, so the bijection is natural in $(A,X)$, completing the proof. Naturality distinguishes there exists a bijection from the bijection is canonical. Without it, one could iterate the construction $X\mapsto X^{\prime }$ with $X^{\prime }(A)=[{\mathcal{A}}^{\mathrm{op}},\mathbf{Set}](H_A,X)$ and manufacture an infinite sequence of presheaves $X,X^{\prime },X^{\prime \prime },\dots$. The Yoneda lemma says $X^{\prime }\cong X$ naturally, so the sequence never leaves $X$.

The covariant form and duality

Replacing $\mathcal{A}$ by ${\mathcal{A}}^{\mathrm{op}}$ dualizes the lemma. A presheaf on ${\mathcal{A}}^{\mathrm{op}}$ is a covariant functor $X:\mathcal{A}\to \mathbf{Set}$, and the representable presheaf at $A$ becomes the covariant hom-functor $H^A=\mathcal{A}(A,-)$, so the dual statement reads

naturally in $A$ and $X$. The explicit maps are the same up to reversal: a natural transformation $\beta :H^A\to X$ corresponds to ${\beta }_A(1_A)\in X(A)$, and an element $c\in X(A)$ induces the transformation with components $f\mapsto (X(f))(c)$ for $f:A\to B$.² Nothing new needs proving; both forms are used freely, the contravariant one because the Yoneda embedding lands in presheaves, the covariant one because forgetful and hom-set functors are covariant.

Directed graphs

For a computation where every set can be written down, take directed graphs. A graph is a pair of sets with source and target functions, which is exactly a set-valued functor on a two-object category: let $\mathcal{G}$ have objects $N$ and $E$ and two non-identity arrows $s,t:N\to E$. A presheaf $X:{\mathcal{G}}^{\mathrm{op}}\to \mathbf{Set}$ assigns a set $X(E)$ of edges, a set $X(N)$ of nodes, and two functions $X(s),X(t):X(E)\to X(N)$ giving each edge its source and target.³

The representable presheaf $H_N=\mathcal{G}(-,N)$ has

so $H_N$ is the graph with one node and no edges. The Yoneda lemma then says, for any graph $X$,

a map from the one-node graph into $X$ is the same as a node of $X$. This is visibly true: a graph map out of a single node picks a node and nothing else, and the identity-arrow chase is one line, since the only element of $H_N(N)$ to chase is $1_N$.

The representable $H_E$ works the same way: $H_E(E)=\{1_E\}$ and $H_E(N)=\mathcal{G}(N,E)=\{s,t\}$, with $H_E(s)$ and $H_E(t)$ sending $1_E$ to $s$ and $t$ respectively. So $H_E$ is the graph with two nodes and a single edge from one to the other, and Yoneda gives $[{\mathcal{G}}^{\mathrm{op}},\mathbf{Set}](H_E,X)\cong X(E)$: maps from the single-edge graph into $X$ are the edges of $X$. Again this is visible directly, since placing the generic edge into $X$ means choosing an edge together with its (determined) endpoints. In both cases the lemma converts a statement about all components of a natural transformation at once into a statement about a single generator.

The one-object case

The lemma's content is visible already for a monoid $M$ viewed as a one-object category, where a presheaf $M^{\mathrm{op}}\to \mathbf{Set}$ is a right $M$-set.⁴ The unique representable presheaf is the right regular representation: the underlying set of $M$ acted on by right multiplication, $x\cdot m=xm$. Write it $\underline{M}$. For any right $M$-set $X$ and any $x\in X$, there is a unique map of $M$-sets $\alpha :\underline{M}\to X$ with $\alpha (1)=x$, namely $\alpha (m)=x\cdot m$. So maps $\underline{M}\to X$ correspond bijectively to elements of $X$:

This is the Yoneda lemma for a one-object category, with the abstract $X(A)$ made concrete as the underlying set of the $M$-set $X$. A map out of the regular representation is a choice of where to send the generator $1$, and equivariance forces the rest.

Because a map $H_A\to X$ is an element of $X(A)$, taking $X$ to be another representable $H_{A^{\prime }}$ shows that maps of representables are exactly maps of objects, so the Yoneda embedding $H_{\bullet }$ is full and faithful, and an object is determined by the maps into it.