Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Advanced undergraduate

The Yoneda lemma

Name: ______________________

Date: ______________________

You will learn to

State and prove the Yoneda lemma $\mathrm{Nat}(\Hom(A, -), F) \cong F(A)$ , including its naturality in $A$ and $F$
Deduce that the Yoneda embedding $\mathcal{C} \to [\mathcal{C}^{\mathrm{op}}, \cat{Set}]$ is full and faithful, and that $\Hom(-, A) \cong \Hom(-, B)$ implies $A \cong B$
Apply the lemma to recover Cayley's theorem, the down-set embedding of a poset and the natural operations on groups
Prove that every presheaf on a small category is a colimit of representable presheaves
Explain the functor-of-points idea and why an object is determined by the arrows into it, not by its elements

1.
In the Yoneda lemma $\mathrm{Nat}(\Hom(A, -), F) \cong F(A)$ , which element of $F(A)$ corresponds to a natural transformation $\alpha : \Hom(A, -) \Rightarrow F$ ?
- A. $\alpha_A(\id_A)$
- B. $F(\id_A)$
- C. $\alpha_X(f)$ for some arrow $f : A \to X$ chosen in advance
- D.The image of all of $\Hom(A, A)$ under $\alpha_A$
2.
A directed graph $G$ (allowing loops and parallel edges) has $7$ vertices and $12$ edges. View it as a functor on the category $\mathbb{E}$ with arrows $s, t : E \to V$ . How many graph homomorphisms are there from the walking edge $\Hom(E, -)$ — one edge from a vertex $s$ to a vertex $t$ — to $G$ ?
3.
On the category $\cat{Ab}$ of abelian groups, $\Hom(\Z/3, -)$ sends $G$ to its elements of order dividing $3$ , and $\Hom(\Z, -)$ sends $G$ to all of its elements. How many natural transformations $\Hom(\Z/3, -) \Rightarrow \Hom(\Z, -)$ are there?
4.
Which of these rules define natural transformations $U \Rightarrow U$ , where $U : \cat{Grp} \to \cat{Set}$ is the forgetful functor (a rule must be defined for every group and commute with every homomorphism)? Choose all that apply.
- A. $g \mapsto g^{-1}$
- B. $g \mapsto g^5$
- C. $g \mapsto g$ if $G$ is abelian, and $g \mapsto e$ otherwise
- D. $g \mapsto h g h^{-1}$ for a fixed element $h$
5.
In the proof that $\Psi(\Phi(\alpha)) = \alpha$ we write $\alpha_X(f) = \alpha_X(f \circ \id_A) = F(f)(\alpha_A(\id_A))$ . Which fact justifies the second equality?
- A.Naturality of $\alpha$ along the arrow $f : A \to X$ , applied to the element $\id_A$
- B.Functoriality of $F$ : $F(f \circ \id_A) = F(f)$
- C.The identity law $f \circ \id_A = f$
- D.The Yoneda lemma itself
6.
Which of these conclusions are justified for objects $A, B$ of a locally small category? Choose all that apply.
- A.If $\Hom(X, A) \cong \Hom(X, B)$ naturally in $X$ , then $A \cong B$ .
- B.If $\Hom(A, X) \cong \Hom(B, X)$ naturally in $X$ , then $A \cong B$ .
- C.In $\cat{Top}$ : if $\Hom(1, A) \cong \Hom(1, B)$ , i.e. $A$ and $B$ have the same number of points, then $A \cong B$ .
- D.If $\Hom(-, A) \cong \Hom(-, B)$ , then there is exactly one isomorphism $A \to B$ .
7.
Let $G$ be a group. Which permutations $\sigma$ of the set $G$ satisfy $\sigma(xh) = \sigma(x)h$ for all $x, h \in G$ ?
- A.Exactly the left multiplications $x \mapsto gx$
- B.Exactly the right multiplications $x \mapsto xg$
- C.Only the identity
- D.All permutations of $G$
8.
Mathlib's coyoneda.obj (op A) is the functor $\Hom(A, -)$ . Which Lean statement formalises "if $\Hom(A, -) \cong \Hom(B, -)$ naturally, then $A \cong B$ "?
- A.theorem iso_of_corepresentable_iso {A B : C} (e : coyoneda.obj (op A) ≅ coyoneda.obj (op B)) : Nonempty (A ≅ B)
- B.theorem t {A B : C} (e : A ≅ B) : Nonempty (coyoneda.obj (op A) ≅ coyoneda.obj (op B))
- C.theorem t {A B : C} (h : ∀ X : C, Nonempty ((A ⟶ X) ≃ (B ⟶ X))) : Nonempty (A ≅ B)
- D.theorem t {A B : C} (α : coyoneda.obj (op A) ⟶ coyoneda.obj (op B)) : A ⟶ B
9.
The cyclic group $\Z/n$ acts on $X = \{0, \dots, m-1\}$ when its generator acts by a permutation p (a list with p[x] the image of x) satisfying $p^n = \mathrm{id}$ . An equivariant map from the regular action is a function a : Z/n → X (a list of length n) with a[(k + 1) % n] == p[a[k]] for all k. Write count_equivariant(n, p) that counts such maps by brute force over all functions (use itertools.product). The Yoneda lemma predicts the answer len(p).
Computational — Practice

Answer key — The Yoneda lemma

1.
$\Phi(\alpha) = \alpha_A(\id_A)$ . Every $f : A \to X$ equals $f \circ \id_A$ , so naturality gives $\alpha_X(f) = F(f)(\alpha_A(\id_A))$ : the single element $\alpha_A(\id_A)$ determines $\alpha$ , and every element of $F(A)$ arises this way.
2.
By the Yoneda lemma, homomorphisms $\Hom(E, -) \Rightarrow G$ correspond to elements of $G(E)$ , the edges: $12$ . Concretely, the edge $\id_E$ can go to any edge $e$ of $G$ , and then $s \mapsto$ source of $e$ and $t \mapsto$ target of $e$ are forced by naturality.
3.
By the Yoneda lemma, $\mathrm{Nat}(\Hom(\Z/3, -), \Hom(\Z, -)) \cong \Hom(\Z, \Z/3)$ , which has $3$ elements ( $1 \mapsto 0, 1, 2$ ). Concretely the three natural maps from $3$ -torsion elements to all elements are $x \mapsto 0$ , $x \mapsto x$ (the inclusion) and $x \mapsto 2x$ .
4.
Since $U \cong \Hom(\Z, -)$ , the Yoneda lemma gives $\mathrm{Nat}(U, U) \cong U(\Z) = \Z$ : the natural operations are exactly $g \mapsto g^n$ . So $g^{-1}$ ( $n = -1$ ) and $g^5$ ( $n = 5$ ) are natural; the abelian-or-not rule fails for the inclusion $\Z/3 \to S_3$ ; and 'conjugate by a fixed $h$ ' does not even make sense uniformly in all groups.
5.
Naturality of $\alpha$ along $f : A \to X$ is the square $\alpha_X \circ (f \circ -) = F(f) \circ \alpha_A$ of functions $\Hom(A, A) \to F(X)$ . Applying both sides to $\id_A$ gives $\alpha_X(f \circ \id_A) = F(f)(\alpha_A(\id_A))$ .
6.
(a) is Corollary 5 and (b) its dual. (c) fails: probing only with the one-point space loses the topology. (d) confuses 'unique isomorphism compatible with a given $\theta$ ' with 'unique isomorphism': $y$ gives a bijection between natural isomorphisms $y(A) \cong y(B)$ and isomorphisms $A \cong B$ , and there may be many of both.
7.
If $\sigma(xh) = \sigma(x)h$ for all $x, h$ , then $\sigma(x) = \sigma(e\,x) = \sigma(e)\,x$ , so $\sigma$ is left multiplication by $\sigma(e)$ . Conversely $\lambda_g(xh) = gxh = \lambda_g(x)h$ . This is the Yoneda lemma for the one-object category $\mathbf{B}G$ , and with functoriality it gives Cayley's theorem: $g \mapsto \lambda_g$ is an injective homomorphism $G \to \mathrm{Sym}(G)$ .
8.
Option (a), proved in the lesson's file: from e take g = e.hom.app A (𝟙 A) : B ⟶ A and h = e.inv.app B (𝟙 B) : A ⟶ B; the components of e and e⁻¹ are precomposition with g and h, and e.hom ≫ e.inv = 𝟙 evaluated at 𝟙 A gives h ≫ g = 𝟙 A.
9.
```
import itertools

def count_equivariant(n, p):
    count = 0
    for a in itertools.product(range(len(p)), repeat=n):
        if all(a[(k + 1) % n] == p[a[k]] for k in range(n)):
            count += 1
    return count
```
Out of $m^n$ candidate functions, exactly $m$ are equivariant: each is determined by $a[0]$ (the image of the identity element), since then $a[k] = p^k(a[0])$ — and any choice of $a[0]$ works because $p^n = \mathrm{id}$ . This is the Yoneda lemma for the one-object category of $\Z/n$ .