The Yoneda lemma · The Lumenary

Lens

MotivationH

Known by your relationships

In 1854 Arthur Cayley observed that every group is a group of permutations: an element $g$ of $G$ can be replaced by the permutation $x \mapsto gx$ of $G$ , and nothing is lost. In a partially ordered set, an element $x$ is completely determined by the set $\{z \mid z \le x\}$ of elements below it. In linear algebra, a finite-dimensional vector space can be recovered from its dual, the linear maps out of it.

But "determined by its relationships" needs care. A topological space is not determined by its points: the sets $\{0, 1\}$ with the discrete and with the indiscrete topology have the same points — the same continuous maps from a one-point space — but they are different spaces. One kind of probe is not enough.

The Yoneda lemma says what is enough: probe an object $A$ with all objects, recording every arrow $X \to A$ and how the arrows compose. Then nothing is lost — $A$ can be recovered up to isomorphism, and arrows between objects are recovered exactly. The lemma itself is short and its proof is a single idea, but it is the reason universal properties determine objects, the reason Grothendieck could treat geometric spaces as functors, and the reason so many constructions in mathematics are "the same". This lesson builds on representable functors and natural transformations.

IntuitionH

Follow the identity

Fix an object $A$ and a functor $F : \mathcal{C} \to \cat{Set}$ . A natural transformation $\alpha : \Hom(A, -) \Rightarrow F$ consists of a function $\alpha_X : \Hom(A, X) \to F(X)$ for every object $X$ — a huge amount of data, one function per object.

But among all arrows out of $A$ there is one special one: $\id_A$ . Every arrow $f : A \to X$ is obtained from it by composing, $f = f \circ \id_A$ . Naturality says that $\alpha$ commutes with composing, so $\alpha_X(f)$ must be obtained from $\alpha_A(\id_A)$ by applying $F(f)$ . All the data of $\alpha$ is packed into the single element

\alpha_A(\id_A) \in F(A),

and any element of $F(A)$ can be unpacked into a natural transformation. The identity arrow is a generic element: the most general $A$ -shaped thing, of which every other is a specialisation.

Naturality along

f : A \to X

, applied to

\id_A

: going down then across gives

\alpha_X(f)

, going across then down gives

F(f)(\alpha_A(\id_A))

DefinitionsH

Definitions

Throughout, $\mathcal{C}$ is locally small: every $\Hom(A, B)$ is a set. For functors $F, G$ we write $\mathrm{Nat}(F, G)$ for the collection of natural transformations $F \Rightarrow G$ .

Definition— presheaf

A presheaf on $\mathcal{C}$ is a functor $P : \mathcal{C}^{\mathrm{op}} \to \cat{Set}$ . Presheaves and natural transformations form the presheaf category $\widehat{\mathcal{C}} = [\mathcal{C}^{\mathrm{op}}, \cat{Set}]$ . When $\mathcal{C}$ is small (its objects and arrows form sets), $\widehat{\mathcal{C}}$ is locally small.

Definition— Yoneda embedding

The Yoneda embedding $y : \mathcal{C} \to \widehat{\mathcal{C}}$ sends an object $A$ to the representable presheaf $y(A) = \Hom(-, A)$ and an arrow $f : A \to B$ to the natural transformation $y(f) = f \circ - : \Hom(-, A) \Rightarrow \Hom(-, B)$ .

Definition— the Yoneda map

For $F : \mathcal{C} \to \cat{Set}$ and an object $A$ , define

\Phi : \mathrm{Nat}(\Hom(A, -), F) \to F(A), \qquad \Phi(\alpha) = \alpha_A(\id_A),

and, in the other direction, for $x \in F(A)$ let $\Psi(x) : \Hom(A, -) \Rightarrow F$ have components $\Psi(x)_X(f) = F(f)(x)$ .

Some examples of the objects involved:

A group $G$ is a category $\mathbf{B}G$ with one object $\ast$ , one arrow for each $g \in G$ , and composition $g \circ h = gh$ . A functor $\mathbf{B}G \to \cat{Set}$ is a set with a left $G$ -action, a presheaf on $\mathbf{B}G$ is a set with a right action, and natural transformations are equivariant maps. The representable presheaf $y(\ast)$ is $G$ acting on itself by right multiplication.
A directed graph is a functor $G : \mathbb{E} \to \cat{Set}$ , where $\mathbb{E}$ has two objects $E, V$ and two arrows $s, t : E \to V$ besides identities: $G(E)$ is the set of edges, $G(V)$ the set of vertices, $G(s)$ and $G(t)$ give the source and target. Natural transformations are graph homomorphisms. The representable $\Hom(E, -)$ is the walking edge (one edge, from $s$ to $t$ ), and $\Hom(V, -)$ is a single vertex.
A poset $(P, \le)$ is a category with an arrow $x \to y$ exactly when $x \le y$ . The representable $\Hom(-, x)$ is, in effect, the down-set $\downarrow x = \{z \mid z \le x\}$ .
A simplicial set is a presheaf on the category $\Delta$ of finite ordinals $[n] = \{0 < 1 < \dots < n\}$ and order-preserving maps; the representable $\Delta[n] = \Hom_\Delta(-, [n])$ is the standard $n$ -simplex.

ProofH

The Yoneda lemma and its consequences

Theorem— Theorem 1 (the Yoneda lemma)

Let $\mathcal{C}$ be locally small, $F : \mathcal{C} \to \cat{Set}$ a functor and $A$ an object. Then $\Psi(x)$ is a natural transformation for every $x \in F(A)$ , and $\Phi$ and $\Psi$ are mutually inverse bijections

\mathrm{Nat}(\Hom(A, -), F) \;\cong\; F(A).

Proof

$\Psi(x)$ is natural. For $g : X \to Y$ and $f : A \to X$ , functoriality of $F$ gives

\Psi(x)_Y(g \circ f) = F(g \circ f)(x) = F(g)\big(F(f)(x)\big) = F(g)\big(\Psi(x)_X(f)\big).

$\Phi \circ \Psi = \id$ . $\Phi(\Psi(x)) = \Psi(x)_A(\id_A) = F(\id_A)(x) = x$ .

$\Psi \circ \Phi = \id$ . Let $\alpha : \Hom(A, -) \Rightarrow F$ and $f : A \to X$ . Naturality of $\alpha$ along $f$ says $\alpha_X(f \circ h) = F(f)(\alpha_A(h))$ for every $h : A \to A$ . Take $h = \id_A$ :

\alpha_X(f) = \alpha_X(f \circ \id_A) = F(f)\big(\alpha_A(\id_A)\big) = \Psi(\Phi(\alpha))_X(f).

So $\Psi(\Phi(\alpha))$ and $\alpha$ agree at every component, at every arrow.

∎

A remark on size: even when $\mathcal{C}$ is large, so that a natural transformation is a "large" family, the lemma shows that $\mathrm{Nat}(\Hom(A, -), F)$ is in bijection with a set.

Theorem— Theorem 2 (naturality of the Yoneda bijection)

The bijection $\Phi$ is natural in both $F$ and $A$ :

for a natural transformation $\beta : F \Rightarrow G$ , $\;\Phi(\beta \circ \alpha) = \beta_A(\Phi(\alpha))$ ;
for an arrow $f : A \to A'$ , $\;\Phi\big(\alpha \circ \Hom(f, -)\big) = F(f)(\Phi(\alpha))$ , where $\Hom(f, -) : \Hom(A', -) \Rightarrow \Hom(A, -)$ is precomposition with $f$ .

So $\Phi$ is a natural isomorphism between the two functors $\mathcal{C} \times [\mathcal{C}, \cat{Set}] \to \cat{Set}$ given by $(A, F) \mapsto \mathrm{Nat}(\Hom(A, -), F)$ and $(A, F) \mapsto F(A)$ .

Proof

(1) $\Phi(\beta \circ \alpha) = (\beta \circ \alpha)_A(\id_A) = \beta_A(\alpha_A(\id_A))$ , by the definition of vertical composition.

(2) $\Phi(\alpha \circ \Hom(f, -)) = \alpha_{A'}\big(\Hom(f, -)_{A'}(\id_{A'})\big) = \alpha_{A'}(\id_{A'} \circ f) = \alpha_{A'}(f)$ , and by the last step of the proof of Theorem 1, $\alpha_{A'}(f) = F(f)(\alpha_A(\id_A))$ .

∎

Applying Theorem 1 to $\mathcal{C}^{\mathrm{op}}$ gives the form used for presheaves.

Theorem— Corollary 3 (contravariant form)

For a presheaf $P : \mathcal{C}^{\mathrm{op}} \to \cat{Set}$ and an object $A$ , the map $\alpha \mapsto \alpha_A(\id_A)$ is a bijection $\mathrm{Nat}(\Hom(-, A), P) \cong P(A)$ , natural in $A$ and $P$ . Its inverse sends $x \in P(A)$ to the transformation $f \mapsto P(f)(x)$ , for $f : X \to A$ .

Theorem— Corollary 4 (the Yoneda embedding is full and faithful)

For all objects $A, B$ , the map $f \mapsto y(f)$ is a bijection $\Hom(A, B) \cong \mathrm{Nat}(y(A), y(B))$ .

Proof

Take $P = y(B) = \Hom(-, B)$ in Corollary 3: $\mathrm{Nat}(y(A), y(B)) \cong \Hom(A, B)$ . The inverse bijection sends $f : A \to B$ to the transformation $g \mapsto y(B)(g)(f) = f \circ g$ , which is exactly $y(f)$ . So $f \mapsto y(f)$ is a bijection.

∎

Theorem— Corollary 5 (the Yoneda principle)

If $\Hom(-, A) \cong \Hom(-, B)$ as presheaves, then $A \cong B$ . More precisely, every natural isomorphism $\theta : y(A) \cong y(B)$ is $y(\varphi)$ for a unique isomorphism $\varphi : A \to B$ . Dually, $\Hom(A, -) \cong \Hom(B, -)$ implies $A \cong B$ .

Proof

By Corollary 4, $\theta = y(\varphi)$ and $\theta^{-1} = y(\psi)$ for unique arrows $\varphi : A \to B$ and $\psi : B \to A$ . Since $y$ is a functor, $y(\psi \circ \varphi) = \theta^{-1} \circ \theta = \id_{y(A)} = y(\id_A)$ , and since $y$ is faithful, $\psi \circ \varphi = \id_A$ . Likewise $\varphi \circ \psi = \id_B$ . The dual statement is the same argument for the covariant embedding $A \mapsto \Hom(A, -)$ of $\mathcal{C}^{\mathrm{op}}$ , using Theorem 1.

∎

This is why every universal property determines its object up to a unique isomorphism: a universal property says that some object represents a given functor, and two representing objects have isomorphic hom functors.

Theorem— Corollary 6 (Cayley's theorem)

For a group $G$ , the map $g \mapsto \lambda_g$ , $\lambda_g(x) = gx$ , is an injective group homomorphism $G \to \mathrm{Sym}(G)$ . Its image consists exactly of the permutations $\sigma$ with $\sigma(xh) = \sigma(x)h$ for all $x, h$ .

Proof

Apply Corollary 4 to $\mathbf{B}G$ . The presheaf $y(\ast)$ is the set $G$ , on which an arrow $h$ acts by precomposition, $x \mapsto x \circ h = xh$ . A natural transformation $y(\ast) \Rightarrow y(\ast)$ is therefore a map $\sigma : G \to G$ with $\sigma(xh) = \sigma(x)h$ , and $y(g)$ is post-composition $x \mapsto g \circ x = gx$ , which is $\lambda_g$ . Full faithfulness says every such $\sigma$ is $\lambda_g$ for exactly one $g$ (concretely, $g = \sigma(e)$ , because $\sigma(x) = \sigma(e\,x) = \sigma(e)\,x$ ). Functoriality of $y$ says $\lambda_{gh} = \lambda_g \circ \lambda_h$ and $\lambda_e = \id$ . So $g \mapsto \lambda_g$ is an injective homomorphism into $\mathrm{Sym}(G)$ , with the stated image.

∎

Theorem— Corollary 7 (Yoneda for posets)

In a poset, $x \le y$ if and only if every $z \le x$ also satisfies $z \le y$ , i.e. $\downarrow x \subseteq \downarrow y$ . In particular $\downarrow x = \downarrow y$ implies $x = y$ .

Proof

This is Corollary 4 for a thin category, where a hom-set has at most one element: a natural transformation $\Hom(-, x) \Rightarrow \Hom(-, y)$ exists exactly when $\downarrow x \subseteq \downarrow y$ , and an arrow $x \to y$ exists exactly when $x \le y$ . Directly: if $x \le y$ and $z \le x$ then $z \le y$ by transitivity; conversely take $z = x$ . The second claim follows by antisymmetry.

∎

Theorem— Corollary 8 (natural operations on groups)

Let $U : \cat{Grp} \to \cat{Set}$ be the forgetful functor. Every natural transformation $\theta : U \Rightarrow U$ is $g \mapsto g^n$ for a unique $n \in \Z$ . Every natural transformation $U \times U \Rightarrow U$ is $(g, h) \mapsto w(g, h)$ for a unique word $w$ in the free group $F_2 = \langle a, b \rangle$ .

Proof

$U \cong \Hom(\Z, -)$ with universal element $1$ , and $U \times U \cong \Hom(F_2, -)$ with universal element $(a, b)$ . By Theorem 1, $\mathrm{Nat}(\Hom(\Z, -), U) \cong U(\Z) = \Z$ ; the element $n$ corresponds to $\theta_G(g) = U(\varphi_g)(n) = g^n$ , where $\varphi_g : \Z \to G$ is the homomorphism with $1 \mapsto g$ . Similarly $\mathrm{Nat}(\Hom(F_2, -), U) \cong U(F_2)$ : the word $w$ corresponds to $(g, h) \mapsto w(g, h)$ , the image of $w$ under the homomorphism $a \mapsto g$ , $b \mapsto h$ .

∎

So the only operations that make sense uniformly in all groups and commute with all homomorphisms are words: $g^{-1}$ , $g^2 h^{-3}$ , the commutator $ghg^{-1}h^{-1}$ , and so on. "Conjugate by a fixed element" is not one of them — there is no fixed element common to all groups.

Theorem— Theorem 9 (density: presheaves are colimits of representables)

Let $\mathcal{C}$ be small and $P$ a presheaf on $\mathcal{C}$ . Let $\int P$ be its category of elements: objects are pairs $(c, x)$ with $x \in P(c)$ , and an arrow $(c, x) \to (c', x')$ is an arrow $f : c \to c'$ with $P(f)(x') = x$ . Then $P$ is the colimit of the diagram $\int P \to \widehat{\mathcal{C}}$ , $(c, x) \mapsto y(c)$ , with coprojections $\lambda_{(c, x)} : y(c) \Rightarrow P$ the transformations corresponding to $x$ under Corollary 3.

Proof

Write $\Phi(\alpha) = \alpha_c(\id_c)$ for $\alpha : y(c) \Rightarrow Q$ , so that $\Phi(\lambda_{(c, x)}) = x$ . Corollary 3 with its naturality gives, for $f : c' \to c$ and $\beta : Q \Rightarrow R$ ,

\Phi(\alpha \circ y(f)) = Q(f)(\Phi(\alpha)), \qquad \Phi(\beta \circ \alpha) = \beta_c(\Phi(\alpha)).

Cocone. For an arrow $f : (c, x) \to (c', x')$ of $\int P$ : $\Phi(\lambda_{(c', x')} \circ y(f)) = P(f)(x') = x = \Phi(\lambda_{(c, x)})$ , so $\lambda_{(c', x')} \circ y(f) = \lambda_{(c, x)}$ because $\Phi$ is injective.

Factorisation. Let $\mu_{(c, x)} : y(c) \Rightarrow Q$ be another cocone. Define $\tau_c : P(c) \to Q(c)$ by $\tau_c(x) = \Phi(\mu_{(c, x)})$ . It is natural: for $f : c' \to c$ and $x \in P(c)$ , $f$ is an arrow $(c', P(f)(x)) \to (c, x)$ of $\int P$ , so $\mu_{(c, x)} \circ y(f) = \mu_{(c', P(f)(x))}$ and

\tau_{c'}\big(P(f)(x)\big) = \Phi\big(\mu_{(c, x)} \circ y(f)\big) = Q(f)\big(\Phi(\mu_{(c, x)})\big) = Q(f)\big(\tau_c(x)\big).

And $\Phi(\tau \circ \lambda_{(c, x)}) = \tau_c(x) = \Phi(\mu_{(c, x)})$ , so $\tau \circ \lambda_{(c, x)} = \mu_{(c, x)}$ .

Uniqueness. If also $\tau' \circ \lambda_{(c, x)} = \mu_{(c, x)}$ for all $(c, x)$ , then $\tau'_c(x) = \tau'_c(\Phi(\lambda_{(c, x)})) = \Phi(\tau' \circ \lambda_{(c, x)}) = \Phi(\mu_{(c, x)}) = \tau_c(x)$ .

Since $\mathcal{C}$ is small, so is $\int P$ , and this is a small colimit.

∎

For a simplicial set $X$ this says that $X$ is glued from standard simplices $\Delta[n]$ , one for each $n$ -simplex of $X$ — and Corollary 3 says that the $n$ -simplices of $X$ are the maps $\Delta[n] \to X$ . In the Kan extensions lesson, density is the starting point for extending functors from $\mathcal{C}$ to all presheaves.

Worked examplesH

Worked examples

Example— Edges and vertices of a graph

Let $G$ be a directed graph, viewed as a functor $\mathbb{E} \to \cat{Set}$ . A graph homomorphism from the walking edge $\Hom(E, -)$ to $G$ is determined by where it sends the edge $\id_E$ ; by Theorem 1 it can send it to any edge of $G$ , and the endpoints $s, t$ must then go to that edge's source and target. So $\mathrm{Nat}(\Hom(E, -), G) \cong G(E)$ , the edges. Likewise homomorphisms from the one-vertex graph are the vertices. "The edges of $G$ are the maps from an edge" is the Yoneda lemma.

Example— Cayley's theorem for $S_3$

Write $S_3 = \{e, r, r^2, s, rs, r^2 s\}$ with $r^3 = s^2 = e$ and $srs^{-1} = r^{-1}$ . Left multiplication by $r$ permutes the six elements as two 3-cycles, $(e\ \ r\ \ r^2)(s\ \ rs\ \ r^2 s)$ ; that is the permutation $\lambda_r$ . Of the $6! = 720$ permutations of $S_3$ , exactly six commute with every right multiplication, and they are $\lambda_e, \lambda_r, \dots$ — the computation section finds them by brute force. Corollary 6 explains why: a permutation commuting with right multiplications is determined by where it sends $e$ .

Example— Divisibility

In $(\N_{\ge 1}, \mid)$ , $a \mid b$ exactly when every divisor of $a$ divides $b$ (Corollary 7). Two numbers with the same set of divisors are equal. Nothing deep — but it is the same theorem as Cayley's.

Example— Proving an isomorphism by Yoneda

For objects with products, $(A \times B) \times C \cong A \times (B \times C)$ . Instead of building the isomorphism by hand, compute hom-sets: naturally in $X$ ,

\Hom(X, (A \times B) \times C) \cong \Hom(X, A) \times \Hom(X, B) \times \Hom(X, C) \cong \Hom(X, A \times (B \times C)).

So $y((A \times B) \times C) \cong y(A \times (B \times C))$ , and Corollary 5 gives the isomorphism. The same technique proves $A \times B \cong B \times A$ and, in a cartesian closed category, $(C^B)^A \cong C^{A \times B}$ .

Example— A natural operation that is not a power

Inversion $g \mapsto g^{-1}$ is natural on groups: it is the power $n = -1$ . On the category of abelian groups, $U \cong \Hom(\Z, -)$ still, so the natural operations are again $g \mapsto ng$ . But on rings, $U \cong \Hom(\Z[x], -)$ , and the natural unary operations are the integer polynomials: $r \mapsto r^2 + 3r - 1$ , and so on, one for each element of $\Z[x]$ .

Formal mathematicsF

The Yoneda lemma in Lean

Mathlib's yoneda : C ⥤ (Cᵒᵖ ⥤ Type) sends A to Hom(−, A), and coyoneda sends A to Hom(A, −). Composition f ≫ g means "first f, then g" (so $g \circ f$ is f ≫ g).

Theorem 1, independently. The two maps of the proof, then the two composites. The key step ofElement_toElement is the human proof's last line as a calc block: naturality applied to the identity, then 𝟙 A ≫ f = f.

toElementLean 4Formally verified

/-- The Yoneda map: a natural transformation `α : Hom(A, −) ⇒ F` goes to the element
`α_A(id_A) ∈ F(A)` — "where `α` sends the identity". -/
def toElement {A : C} {F : C ⥤ Type v} (α : coyoneda.obj (op A) ⟶ F) : F.obj A :=
  α.app A (𝟙 A)