Foundations of mathematics

The Yoneda lemma

An object is completely determined, up to isomorphism, by the pattern of every arrow pointing into it from everywhere else in the category — the Yoneda lemma turns that observation into a precise bijection, and its corollary that the embedding $A\mapsto\mathrm{Hom}(-,A)$ is fully faithful is the single fact that makes "study objects by their maps" a rigorous method rather than a slogan.

IntuitionAn object is what it does

To know an electronic component completely, you do not need to look inside it — it is enough to know, for every possible surrounding circuit, exactly how the component could be wired into it. In a category, the analogous fact is that an object $A$ is completely pinned down, up to isomorphism, by knowing $\mathrm{Hom}(X,A)$ — the set of ways to map into $A$ — for every single object $X$ at once.

Every arrow from every object

X

into

A

, collected at once — the data the presheaf

h_A

records.

UndergraduateRepresentable presheaves

Definition: The presheaf $h_A$

For an object $A$ of $\mathcal{C}$ , the representable presheaf $h_A=\mathrm{Hom}_{\mathcal{C}}(-,A)$ assigns to every object $X$ the set $h_A(X)=\mathrm{Hom}_{\mathcal{C}}(X,A)$ , and to every morphism $g:X\to Y$ the precomposition map $h_A(g):\mathrm{Hom}(Y,A)\to\mathrm{Hom}(X,A),\quad f\mapsto f\circ g$ . This makes $h_A$ a functor $\mathcal{C}^{\mathrm{op}}\to\mathbf{Set}$ — contravariant, because composing on the right with $g$ reverses the direction of the assignment.

h_A(X) = \mathrm{Hom}_{\mathcal{C}}(X,A)

Given any functor $F:\mathcal{C}^{\mathrm{op}}\to\mathbf{Set}$ , the Yoneda lemma says the natural transformations from $h_A$ to $F$ are in bijection with the elements of the single set $F(A)$ : $\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A)$ . The bijection is built from two maps, $\Phi$ and $\Psi$ , going in opposite directions.

\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A), F) \cong F(A)

The two directions of the Yoneda bijection
Map	Direction	Formula
$\Phi$	$\mathrm{Nat}(h_A,F)\to F(A)$	$\Phi(\eta)=\eta_A(1_A)$
$\Psi$	$F(A)\to\mathrm{Nat}(h_A,F)$	$\Psi(x)_X(f)=F(f)(x)$

AdvancedThe bijection, proved step by step

$\Phi$ evaluates a natural transformation $\eta:h_A\Rightarrow F$ at the most economical possible input — the identity $1_A\in h_A(A)=\mathrm{Hom}(A,A)$ — producing the element $\eta_A(1_A)$ of $F(A)$ . In the reverse direction, $\Psi$ starts from an element $x\in F(A)$ and reconstructs, for every object $X$ and every $f\in\mathrm{Hom}(X,A)$ , an element of $F(X)$ by pushing $x$ forward along $F(f)$ : $\Psi(x)_X(f)=F(f)(x)$ . Naturality of $\eta$ is exactly what makes $\Psi(\Phi(\eta))$ recover $\eta$ , and this is what the next theorem proves in full.

\Phi(\eta) = \eta_A(1_A)

\Psi(x)_X(f) = F(f)(x)

Theorem: The Yoneda lemma

For every functor $F:\mathcal{C}^{\mathrm{op}}\to\mathbf{Set}$ and object $A$ , the maps $\Phi$ and $\Psi$ above are mutually inverse, so $\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A)$ as a genuine bijection of sets.

Why is it true?

This is what lets category theorists trade an infinite, hard-to-grasp family of natural transformations for a single concrete element of $F(A)$ — every question about maps out of the representable presheaf $h_A$ collapses to a question about one set.

Proof

We first check $\Phi(\Psi(x))=x$ for every $x\in F(A)$ . Unwind the definitions: $\Psi(x)_A(1_A)=F(1_A)(x)$ by the formula for $\Psi$ , specialized to $X=A$ , $f=1_A$ . Since $F$ is a functor, it sends the identity morphism $1_A$ to the identity function on $F(A)$ , so $F(1_A)(x)=x$ . Therefore $\Phi(\Psi(x))=\Psi(x)_A(1_A)=x$ , exactly as required — this direction uses nothing but the functor identity law.

Now we check the harder direction, $\Psi(\Phi(\eta))=\eta$ for every natural transformation $\eta:h_A\Rightarrow F$ . Both sides are natural transformations $h_A\Rightarrow F$ , so it suffices to show their components agree at every object $X$ and every element $f\in h_A(X)=\mathrm{Hom}(X,A)$ .

Unwind $\Psi(\Phi(\eta))_X(f)$ using the formula for $\Psi$ with $x:=\Phi(\eta)=\eta_A(1_A)$ : this equals $F(f)(\eta_A(1_A))$ .

Now invoke naturality of $\eta$ itself, in the form $\eta_Y(f\circ g)=F(g)(\eta_X(f))$ with $g:=f:X\to A$ and the other variable set to $A$ : taking $f:=1_A\in h_A(A)$ in that naturality square gives exactly $\eta_X(1_A\circ f)=F(f)(\eta_A(1_A))$ , i.e. $\eta_X(f)=F(f)(\eta_A(1_A))$ , since $1_A\circ f=f$ .

Combining the last two displays: $\Psi(\Phi(\eta))_X(f)=F(f)(\eta_A(1_A))=\eta_X(f)$ . Since $X$ and $f$ were arbitrary, the two natural transformations agree everywhere, so $\Psi(\Phi(\eta))=\eta$ . Together with the first paragraph, $\Phi$ and $\Psi$ are mutually inverse bijections.

Theorem: The Yoneda embedding is fully faithful

The Yoneda embedding $y:\mathcal{C}\hookrightarrow[\mathcal{C}^{\mathrm{op}},\mathbf{Set}]$ , $y(A)=h_A$ , is fully faithful: for every $A,B\in\mathcal{C}$ , $\mathrm{Nat}(h_A,h_B)\cong\mathrm{Hom}_{\mathcal{C}}(A,B)$ , and this bijection sends a morphism $f:A\to B$ to the natural transformation $h_A\Rightarrow h_B$ given by postcomposition with $f$ .

Why is it true?

Full faithfulness is exactly the guarantee that the translation $A\mapsto h_A$ loses no information whatsoever: distinct morphisms of $\mathcal{C}$ become distinct natural transformations, and every natural transformation between two representable presheaves comes from an actual morphism of $\mathcal{C}$ , which is what justifies studying objects purely through the maps into them.

Proof

Apply the Yoneda lemma with the target functor set to $F:=h_B$ . The lemma gives a bijection $\mathrm{Nat}(h_A,h_B)\cong h_B(A)$ , and unwinding the definition $h_B(A)=\mathrm{Hom}_{\mathcal{C}}(A,B)$ gives exactly $\mathrm{Nat}(h_A,h_B)\cong\mathrm{Hom}_{\mathcal{C}}(A,B)$ .

It remains to identify what morphism of $\mathcal{C}$ a natural transformation $\eta:h_A\Rightarrow h_B$ corresponds to under this bijection, and to check it is postcomposition. By the formula for $\Phi$ , $\eta$ corresponds to the element $\Phi(\eta)=\eta_A(1_A)\in\mathrm{Hom}(A,B)$ ; call this morphism $f$ .

Now use $\Psi(\Phi(\eta))=\eta$ (the theorem above, applied with $F=h_B$ ) to recover every component of $\eta$ from $f$ : for any object $X$ and any $g\in h_A(X)=\mathrm{Hom}(X,A)$ , $\Psi(f)_X(g)=h_B(g)(f)$ . Unwinding the contravariant action of $h_B$ on morphisms — precomposition — gives $h_B(g)(f)=f\circ g$ . So $\eta_X(g)=f\circ g$ : every component of $\eta$ is literally postcomposition with $f$ .

Because $\Phi$ and $\Psi$ are mutually inverse bijections (proved above) and postcomposition with $f$ is exactly $\Psi(f)$ , the assignment sending $f$ to postcomposition with $f$ is itself a bijection $\mathrm{Hom}(A,B)\to\mathrm{Nat}(h_A,h_B)$ — which is precisely the statement that $y$ is fully faithful.

UndergraduateApplications: moduli spaces and continuation-passing style

In algebraic geometry, a moduli space for some kind of geometric object (curves, vector bundles, ...) is defined by first writing down a functor $F$ sending a test object $X$ to the set of families of that geometric structure over $X$ ; the moduli space, if it exists, is an object $M$ representing $F$ , i.e. $F\cong h_M$ . The Yoneda embedding being fully faithful is exactly why such an $M$ , when it exists, is unique up to a unique isomorphism — Grothendieck's "functor of points" philosophy treats every scheme as nothing more than its representable presheaf. In functional programming, the type $\forall r.\ (a\to r)\to r$ of continuation-passing style functions is, by construction, the type of natural transformations from the covariant Hom-functor $\mathrm{Hom}(a,-)$ to the identity functor; the (covariant, dual) Yoneda lemma says exactly $\forall r.\ (a\to r)\to r \\cong\ a$ , matching the everyday fact that a CPS-transformed value is nothing more than a repackaged ordinary value.

Example: Checking the bijection on a two-object category

Let $\mathcal{C}$ have two objects $0,1$ , identities, and one non-identity morphism $\iota:0\to1$ . Take $A=1$ and $F=h_1$ itself. Verify by direct enumeration that $\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A)$ for this $F$ , i.e. that $\mathrm{Nat}(h_1,h_1)$ has exactly as many elements as $h_1(1)=\mathrm{Hom}(1,1)$ .

Solution

First compute $h_1$ explicitly: $h_1(0)=\mathrm{Hom}(0,1)=\{\iota\}$ (one element) and $h_1(1)=\mathrm{Hom}(1,1)=\{1_1\}$ (one element, since $\mathcal{C}$ has no other morphism ending at $1$ from $1$ ). So $F(A)=h_1(1)$ has exactly one element, $1_1$ .

By the Yoneda lemma, $\mathrm{Nat}(h_1,h_1)$ should also have exactly one element. Check this directly: a natural transformation $\eta:h_1\Rightarrow h_1$ needs components $\eta_0:\{\iota\}\to\{\iota\}$ and $\eta_1:\{1_1\}\to\{1_1\}$ . Each of these sets has one element, so there is exactly one possible function at each object — the identity function — giving exactly one candidate $\eta$ overall.

One must still check this candidate satisfies naturality (it automatically does here, since the naturality square forces $\eta_0(\iota)=\eta_0(1_1\circ\iota)=h_1(\iota)(\eta_1(1_1))=h_1(\iota)(1_1)=1_1\circ\iota=\iota$ , which holds since there is only one available value anyway).

So $\mathrm{Nat}(h_1,h_1)=\{\mathrm{id}_{h_1}\}$ has exactly one element, matching $F(A)=\{1_1\}$ having exactly one element — the bijection $\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A)$ holds concretely, and $\Phi(\mathrm{id}_{h_1})=(\mathrm{id}_{h_1})_1(1_1)=1_1$ recovers the single element directly.

Example: Continuation-passing style as Yoneda

In a functional language, a value of type $\forall r.\ (a\to r)\to r$ is a function $k$ that, given any way of consuming an $a$ (a function $a\to r$ ), produces an $r$ . Show $k$ is completely determined by, and recovers, an ordinary value of type $a$ .

Solution

Identify $\mathcal{C}=\mathbf{Set}$ (or the category of types and functions), fix the object $a$ , and let $F=\mathrm{Id}$ be the identity functor. A value $k:\forall r.\ (a\to r)\to r$ is, by definition, a choice of function $k_r:(a\to r)\to r$ for every type $r$ — exactly a natural transformation from the covariant functor $\mathrm{Hom}(a,-)$ to $\mathrm{Id}$ (naturality here is exactly the parametricity that "for all $r$ " enforces).

Apply $\Phi$ from the (covariant, dual) Yoneda lemma: $\Phi(k)=k(\mathrm{id}_a)$ evaluates $k$ at $r:=a$ on the identity function $\mathrm{id}_a:a\to a$ , producing an ordinary value of type $a$ . This is the direction "continuation determines a value".

Apply $\Psi$ in reverse: given a value $n:a$ , define $\Psi(n)_r(g)=g(n)$ for every $r$ and every $g:a\to r$ — that is, $\Psi(n)_r(g)=g(n)$ , the standard CPS-transform of a value: "the continuation that, given any consumer $g$ , hands $n$ to it".

By the Yoneda lemma applied to $F=\mathrm{Id}$ , these two constructions are mutually inverse: $\Phi(\Psi(n))=\Psi(n)_a(\mathrm{id}_a)=\mathrm{id}_a(n)=n$ recovers the value, and $\Psi(\Phi(k))=k$ by the naturality argument from the theorem above, specialized to $F=\mathrm{Id}$ . Hence $\forall r.\ (a\to r)\to r \\cong\ a$ , confirming that continuation-passing style values carry exactly the information of an ordinary value, no more and no less.

Research frontier as of 2026

The Yoneda lemma keeps being generalized: Jacob Lurie's ∞-categorical Yoneda lemma (Higher Topos Theory, 2009) upgrades the bijection to a homotopy equivalence of spaces, the correct statement once "equality" of natural transformations is itself allowed to have higher structure, and homotopy type theory reformulates the same fact internally to type theory via the univalence axiom. In applied work, "profunctor optics" in functional programming use a Yoneda-style embedding to represent composable getters/setters as natural transformations, and 2020s efforts to formalize category theory in Lean's mathlib have made the Yoneda lemma itself (and its ∞-categorical cousins) one of the standard machine-checked benchmarks for a formalization library, tightening the historical loop between this lemma and the proof assistants used to verify it.

What does $\Phi$ do to a natural transformation $\eta:h_A\Rightarrow F$ ?

The uniqueness step in $\Psi(\Phi(\eta))=\eta$ relies on which property of $\eta$ ?

In continuation-passing style, the type $\forall r.\ (a\to r)\to r$ is naturally isomorphic to which type?

The Yoneda embedding being fully faithful lets us conclude that a representing object $M$ for a moduli functor $F$ is:

References

Saunders Mac Lane (1998). Categories for the Working Mathematician
Emily Riehl (2016). Category Theory in Context
Jacob Lurie (2009). Higher Topos Theory · arXiv:math/0608040