The Yoneda Lemma - Category Theory

2 The Yoneda Lemma

Definition 2.1 (Locally small). We say a category $C$ is locally small if, for any two objects $A$ and $B$ , the morphisms $A \to B$ in $C$ are parameterised by a set $C (A, B)$ .

If $A$ is an object of a locally small category $C$ , we have a functor $C (A, ∙) : C \to S e t$ sending $B$ to $C (A, B)$ and a morphism $B \overset{g}{\to} C$ to the mapping $(f \mapsto g f) : C (A, B) \to C (A, C)$ (this is functorial since composition in $C$ is associative).

Dually, we have $C (∙, B) : C^{o p} \to S e t$ .

Lemma 2.2 (Yoneda). Assuming that:

$C$ is a locally small category
$A \in ob C$
$F : C \to S e t$ a functor

Then

(i) There is a bijection between natural transformations $C (A, ∙) \to F$ and elements of $F A$ .
(ii) Moreover, this bijection is natural in $A$ and $F$ .

Proof.

(i) Given $α : C (A, ∙) \to F$ , we define $Φ (α) = α_{A} (1_{A}) \in F A$ .
Given $x \in F A$ , we define $Ψ (x) : C (A, ∙) \to F$ by $Ψ {(x)}_{B} (f : A \to B) = F f (x) \in F B$ . This is natural in $B$ since $F$ is a functor: given $g : B \to C$ we have
$(F g) Ψ {(x)}_{B} (f) = (F g) (F f) (x) = F (g f) (x) = Ψ {(x)}_{C} (g f) .$

For any $x$ , $Φ Ψ (x) = Ψ {(x)}_{A} (1_{A}) = F 1_{A} (x) = x$ .

For any $α$ , $Ψ Φ {(α)}_{B} (f) = F f (α_{A} (1_{A})) = α_{B} (C (A, f) (1_{A}) = α_{B} (f)$ for all $f : A \to B$ . So $Ψ Φ (α) = α$ .
(ii) Later. Seeing examples of usage of (i) is interesting first. □

Corollary 2.3. Assuming that:

$C$ a locally small category

Then

A \mapsto C (A, ∙)

is a full and faithful functor

C^{o p} \to [C, S e t]

Proof. Substitute $C (B, ∙)$ for $F$ in Lemma 2.2(i): we have a bijection from $C (B, A)$ to the collection of natural transformations $C (A, ∙) \to C (B, ∙)$ .

For a given $f$ , the natural transformation $C (f, ∙)$ sends $g : B \to C$ to $g f$ , so this is functorial by associativity of composition $C$ .

Similarly, we have a full and faithful functor $C \to [C^{o p}, S e t]$ sending $A$ to $C (∙, A)$ . We call this the Yoneda embedding: it allows us to regard any locally small category $C$ as a full subcategory of a $S e t$ -valued functor category. □

Compare with Cayley’s Theorem in group theory (every group is isomorphic to a subgroup of a permutation group) and ‘Dedekind’s Theorem’ (every poset is isomorphic to a sub-poset of a power set).

Definition 2.4 (Representable). We say a functor $F : C \to S e t$ is representable if it’s isomorphic to a $C (A, ∙)$ for some $A$ . By a representation of $F$ , we mean a pair $(A, x)$ where $x \in F A$ is such that $Φ (x)$ is an isomorphism. We call $x$ a universal element of $F$ .

Corollary 2.5. Suppose $(A, x)$ and $(B, y)$ are both representations of $F$ . Then there is a unique isomorphism $A \overset{f}{\to} B$ such that $(F f) (x) = y$ .

Proof. $(F f) (x) = g$ is equivalent to saying that

commutes, so

f

must be the unique isomorphism, whose image under Yoneda is

Φ {(x)}^{- 1} Φ (y)

. □

Proof of Yoneda(ii).

Suppose for the moment that

C

is small, so that

[C, S e t]

is locally small. Given two functors

C \times [C, S e t] \to S e t

: the first sends an object

(A, F)

F A

, and a morphism

(A \overset{f}{\to} A^{'}, F \overset{α}{\to} F^{'})

to the diagonal of

The second is the composite

C \times [C, S e t] \overset{Y \times 1}{\to} {[C, S e t]}^{o p} \times [C, S e t] \overset{[C, S e t] (∙, ∙)}{\to} S e t

where $Y$ is a Yoneda embedding. Then $Φ$ and $Ψ$ define a natural isomorphism between these two.

In elementary terms, this says that if $x \in F A$ , and $x^{'} \in F^{'} A^{'}$ is its image under the diagonal, then $Ψ (x^{'})$ is the composite

C (A^{'}, ∙) \overset{C (f, ∙)}{\to} C (A, ∙) \overset{Ψ (x)}{\to} F \overset{α}{\to} F^{'} .

This makes sense without the assumption that $C$ is small, and it’s true since the composite maps

1_{A^{'}} \mapsto f \mapsto (F f) (x) \mapsto α_{A^{'}} (F f) (x) . □

Example 2.6.

(a) The forgetful functor $G p \to S e t$ is represented by $(ℤ, 1)$ , $R n g \to S e t$ is represented by $(ℤ [X], X)$ , $T o p \to S e t$ is represented by $({*}, *)$ .
(b) The functor $P^{*} : {S e t}^{o p} \to S e t$ is represented by $({0, 1}, {1})$ . This is the bijection between subsets of $A$ and functions $A \overset{f}{\to} {0, 1}$ , and it’s natural. But $P : S e t \to S e t$ is not representable, since $P ({*})$ isn’t a singleton.
(c) The functor $Ω : {T o p}^{o p} \to S e t$ sending $X$ to the set of open subsets of $X$ , and $X \overset{f}{\to} Y$ to $f^{- 1} : Ω (Y) \to Ω (X)$ is representable by the Sierpinski space $Σ = {0, 1}$ with ${1}$ open but ${0}$ not open. This works since continuous maps $X \to Ω$ are the characteristic functions of open subsets of $X$ .
(d) The functor ${(∙)}^{*} : {V e c t}_{k} \to {V e c t}_{k}$ isn’t representable, but its composite with ${V e c t}_{k} \to S e t$ is represented by $k$ .
(e) For a group $G$ considered as a $1$ -object category, the unique representable functor $G \to S e t$ is the Cayley representation: $G$ acting on itself by multiplication.
(f) Given two objects $A, B$ in a locally small category $C$ , we have a functor $C^{o p} \to S e t$ sending $C$ to $C (C, A) \times C (C, B)$ . If this functor is representable, we call the representing object a categorical product $A \times B$ and write $(π_{1} : A \times B \to A, π_{2} : A \times B \to B)$ for the universal element. Its defining property is that given any pair $(f : C \to A, g : C \to B)$ , there is a unique isomorphism $h : C \to A \times B$ such that $π_{q} h = f$ and $π_{2} h = g$ .
Dually, we have the notion of coproduct $A + B$ with coprojections $γ_{1} : A \to A + B$ , $γ_{2} : B \to A + B$ .
(g) Given a parallel pair $A ⇉_{g}^{f} B$ in a locally small category $C$ , we have a functor $F : C^{o p} \to S e t$ sending $C$ to ${h : C \to A | f h = g h}$ and defined on morphisms in the same way as $C (∙, A)$ .
A representation of this functor is called an equaliser of $(f, g)$ : it consists of $E \overset{e}{\to} A$ satisfying $f e = g e$ , and such that any $h$ with $f h = g h$ factors uniquely as $e k$ . Note that $e$ is monic; we call a monomorphism regular if it occurs as an equaliser.

Dually, we have the notions of coequaliser and regular epi.

In $S e t$ , products are just cartesian products (also in $G p$ , $R n g$ , $T o p$ , …). coproducts in $S e t$ are disjoint unions $A ∐ B = (A \times {0}) \cup (B \times {1})$ . In $G p$ , coproducts are free products $G * H$ .

In $S e t$ , the equaliser of $A ⇉_{g}^{f} B$ is the inclusion of ${a \in A | f (a) = g (a)}$ and the coequaliser of $(f, g)$ is the quotient of $B$ by the smallest equivalence relation containing ${(f (a), g (a)) | a + A}$ .

Note that in $S e t$ , all monomorphisms and all epimorphisms are regular, but in $T o p$ , a monomorphism $X \overset{f}{\to} Y$ is regular if and only if $X$ is topologised as a subspace of $Y$ . An epimorphism $X \overset{f}{\to} Y$ is regular if and only if $Y$ is topologised as a quotient of $X$ .

Note that if $f$ is both regular monic and regular epic, then it’s an isomorphism since the pair $(g, h)$ of which its equaliser must satisfy $g = h$ .

Warning. The following terminology is not standard. These are usually (both!) referred to as “generating”, but to avoid confusion, in this course we will refer to them with separate names.

Definition 2.7 (Separating / detecting family). Let $G$ be a family of objects of a locally small category $C$ .

(a)
We say $G$ is a separating family if the functors $C (G, ∙)$ , $G \in G$ are jointly faithful, i.e. given a parallel pair $A ⇉_{g}^{f} B$ , the equations $f h = g h$ for all $h : G \to A$ with $G \in G$ imply $f = g$ .
(b)
We say $G$ is a detecting family if the $G (G, ∙)$ jointly reflect isomorphisms, i.e. given $A \overset{f}{\to} B$ , if every $G \overset{g}{\to} B$ with $G \in G$ factors uniquely through $f$ , then $f$ is an isomorphism.

If $G = {G}$ , we call $G$ a separator or a detector.

Lemma 2.8.

(i)
If $C$ has equalisers (i.e. every pair of parallel arrows has an equaliser), then any detecting family in $C$ is separating.
(ii)
If $C$ is balanced, then any separating family in $C$ is detecting.

Proof.

(i) Suppose $G$ is a detecting family, and suppose $A ⇉_{g}^{f} B$ satisfy the hypothesis of Definition 2.7(a). Let $E \overset{e}{\to} A$ of $(f, g)$ : then any $G \overset{h}{\to} A$ with $G \in G$ factors uniquely through $e$ , so $e$ is an isomorphism, so $f = g$ .
(ii) Suppose $G$ is separating, and $A \overset{f}{\to} B$ satisfies the hypothesis of Definition 2.7(b). If $C ⇉_{h}^{g} A$ satisfy $f g = f h$ , then any $G \overset{k}{\to} C$ with $G \in G$ satisfies $g k = h k$ , since both are factorisations of $f g k$ through $f$ . So $g = h$ ; hence $f$ is monic.
Similarly, if $B ⇉_{m}^{l} D$ satisfy $l f = m f$ , then any $G \overset{n}{\to} B$ satisfies $l n = m n$ , since it factors through $f$ , so $l = m$ and hence $f$ is epic. Since $C$ is balanced, $f$ is an isomorphism. □

Example 2.9.

(a) In $S e t$ , $1 = {*}$ is a separator and a detector, since $S e t (1, ∙)$ is isomorphic to the identity functor. Also, $2 = {0, 1}$ is a coseparator and a codetector, since it represents $P^{*} : {S e t}^{o p} \to S e t$ .
(b) In $G p$ (respectively $R n g$ ), $ℤ$ (respectively $ℤ [X]$ ) is a separator and a detector, since it represents the forgetful functor.
But $G p$ has no coseparator or codetector set: given any set $G$ of groups, there is a simple group $H$ with $card H > card G$ for all $G \in G$ , so the only homomorphisms $H \to G$ with $G \in G$ are trivial.
(c) For any small category $C$ , the set ${C (A, ∙) | A \in ob C}$ is separating and detecting in $[C, S e t]$ . This uses Yoneda and Lemma 1.8 (for the detecting case).
(d) In $T o p$ , $1$ is a separator since it represents $U : T o p \to S e t$ . But $T o p$ has no detecting set of objects: given a set $G$ of spaces, choose $κ > card X$ for all $X \in G$ , and let $Y$ and $Z$ be a set of $card κ$ . Give $Y$ the discrete topology and for $Z$ , we set the closed sets be $Z$ plus all the subsets of $card κ$ . The identity $Y \to Z$ is continuous, but not a homeomorphism, but its restriction to any subset of $card < κ$ is a homeomorphism, so $G$ can’t detect the fact that $f$ isn’t an isomorphism.
(e) Let $G$ be the category whose objects are the ordinals, with identities plus two morphisms $α ⇉_{g}^{f} β$ whenever $α < β$ with composition defined by $f f = f g = g f = g g = f$ .
Then $0$ is a detector for $C$ : it can tell that $0 ⇉_{g}^{f} α$ aren’t isomorphisms since neither factors through the other, and if $0 < α < β$ it can tell that $α ⇉_{g}^{f} β$ aren’t isomorphisms since $0 \overset{g}{\to} β$ doesn’t factor through either.

But $C$ has no separating set: if $G$ is any set of ordinals, choose $α > β$ for all $β \in G$ and then $G$ can’t separate $α ⇉_{g}^{f} α + 1$ .

By definition, the functors $C (A, ∙) : C \to S e t$ preserve monomorphisms, but they don’t always preserve epimorphisms.

Definition 2.10 (Projective). We say an object $P$ in a locally small category $C$ is projective if $C (P, ∙)$ preserves epimorphisms, i.e. if given

there exists

h : P \to Q

with

g h = f

. Dually,

P

is injective if it’s projective in

C^{o p}

If $P$ satisfies this condition for all $g$ in some class $E$ of epimorphisms, we call it $E$ -projective.

In $[C, S e t]$ , we consider the class of pointwise epimorphisms, i.e. those $α$ such that $α_{A}$ is surjective for all $A$ .

Corollary 2.11. If $C$ is small, then functors of the form $C (A, ∙)$ are pointwise projective in $[C, S e t]$ .

Proof. Immediate from Yoneda; given

with

β

pointwise epic,

Φ (α) \in R A

β_{A} (y)

for some

y \in Q A

, so

β Ψ (y) = α

. □

“ $[C, S e t]$ has enough pointwise projectives”:

Proposition 2.12. Assuming that:

$C$ is small
$F : C \to S e t$

Then there exists a pointwise epimorphism

P ↠ F

where

P

is pointwise projective.

Proof. Set $P = ∐_{(A, x)} C (A, ∙)$ where the disjoint union is over all pairs $(A, x)$ with $A \in ob C$ and $x \in F A$ . A morphism $P \to Q$ is uniquely determined by a family of morphisms $C (A, ∙) \to Q$ . . Hence $P$ is pointwise projective, since all the $C (A, ∙)$ are. But we have $α : P \to F$ whose $(A, x)$ -th component is $Ψ (x) : C (A, ∙) \to F$ and this is pointwise epic since any $x \in F A$ appears as $Ψ (x) (1_{A})$ . □