For an arbitrary categoryC, the functors fromC toSetare special because the hom functors Hom(C,−) for each objectCofC are set-valued functors.
In this section, we introduce the concept of representable functor, the Yoneda Lemma, and universal elements, all of which are based on these hom functors.
These ideas have turned out to be fundamental tools for categorists. They are also closely connected with the concept of adjunction, to be discussed later (note Theorem 13.3.2 and Proposition 13.3.6).
If you are familiar with group theory, it may be illuminating to realize that representable functors are a generalization of the regular representation, and the Yoneda embedding is a generalization of Cayley’s Theorem.
We have already considered set-valued functors as actions in Section 3.2.
4.5.1 Representable functors A functor from a categoryC to the cat-egory of sets (aset-valued functor) is said to be representable if it is naturally isomorphic to a hom functor; see 3.1.20. A covariant functor is representable if it is naturally isomorphic to Hom(C,−) for some objectC ofC; in this case one says thatC represents the functor. A contravariant functor is representable if it is naturally isomorphic to Hom(−, C) for some objectC(and thenC represents the contravariant functor).
We have already looked at one example of representable functor in some detail in 4.3.10, where we showed that the set-of-nodes functor for graphs is represented by the graph with one node and no arrows. The set-of-arrows functor is represented by the graph with two nodes and one arrow between them (Exercise 3).
4.5.2 The Yoneda embedding LetC be a category. There is a functor Y : Cop −→Func(C,Set), the Yoneda functor, defined as follows. Note thatY must take an object ofC to a functor and an arrow ofC to a natural transformation.
Y–1 For an objectCofC,Y(C) = Hom(C,−).
Y–2 If f : D −→ C in C and A is an object of C, then the component Y(f)A of Y(f) : Hom(C,−)−→Hom(D,−) is Hom(f, A) : Hom(C, A)
−→Hom(D, A) (see 3.1.21).
Note thatY(C) is acovariant hom functor and thatY(f)Ais a component of acontravariant hom functor.
To see thatY(f) is a natural transformation requires checking that this diagram commutes for every arrowk:A−→B ofC:
Hom(C, A) - Hom(C, B)
Hom(C, k)
Hom(D, A) Hom(D, k)- Hom(D, B) 6
Y(f)A
6 Y(f)B
To see that it commutes, start withh:C−→A, an arbitrary element of the lower left corner. The lower route takes this tok◦h, then to (k◦h)◦f. The upper route takes it tok◦(h◦f), so the fact that the diagram commutes is simply a statement of the associative law. In a monoid, that this diagram commutes is the statement that the function defined by left multiplying by a given element commutes with the function defined by right multiplying by another given element.
Y(f) : Hom(C,−)−→Hom(D,−) is theinduced natural transforma-tioncorresponding tof.
The main theorem concerningY is the following.
4.5.3 Theorem Y :Cop−→Func(C,Set) is a full and faithful functor.
The fact that Y is full and faithful is encapsulated in the following re-markable corollary.
4.5.4 Corollary Every natural transformation Hom(C,−)−→Hom(D,−)
is given by composition with a unique arrowD−→C. The natural transfor-mation is an isomorphism if and only if the corresponding arrowD−→Cis an isomorphism. In particular, ifF :C −→Setis represented by bothCand D, thenC∼=D.
This means that you can construct an arrow in a category by constructing a natural transformation between hom functors. This is one of the most widely used techniques in category theory.
Proof. Theorem 4.5.3 is an immediate consequence of the Yoneda Lemma (4.5.8). We give a direct proof here. This proof is an excellent exercise in manipulating natural transformations and hom sets.
Letf, g:D−→C inC. The component
Y(f)C: Hom(C, C)−→Hom(D, C)
4.5 Yoneda Lemma 123 of the natural transformationY(f) atCtakes idC tof, and similarlyY(g)C takes idC tog. Thus if f 6=g, thenY(f)C6=Y(g)C, so thatY(f)6=Y(g).
ThusY is faithful.
We must show that Y is full. Given φ: Hom(C,−)−→Hom(D,−), we get the requiredf :D−→Cby one of the basic tricks of category theory: we definef =φC(idC). The component ofφatCis a functionφC: Hom(C, C)
−→Hom(D, C), so this definition makes sense.
To complete the proof, we must prove that if k:C −→A is any arrow of C, then φA(k) =k ◦ f : D −→A. This follows from the fact that the following diagram commutes by naturality ofφ:
Hom(D, C) - Hom(D, A)
Hom(D, k)
Hom(C, C) Hom(C, k)-Hom(C, A)
? φC
? φA
If you start in the northwest corner with idC, the upper route takes you to φA(k) in the southeast corner, whereas the lower route takes you tok◦f, as required.
4.5.5 By replacingC byCopin Theorem 4.5.3, we derive a second Yoneda functorJ :C −→Func(Cop,Set) which is also full and faithful. For an object C of C, J(C) = Hom(−, C), the contravariant hom functor. If f :C −→D inC andAis an object ofC, then the component
J(f)A: Hom(A, C)−→Hom(A, D)
of the natural transformationJ(f) : Hom(−, C)−→Hom(−, D) is Hom(A, f) : Hom(A, C)−→Hom(A, D)
The fact that J is full and faithful means that an arrow from A to B of C can be uniquely defined by giving a natural transformation from Hom(−, A) to Hom(−, B). This statement is the dual of Corollary 4.5.4.
Such a natural transformation α : Hom(−, A) −→Hom(−, B) has a com-ponent αT : Hom(T, A)−→Hom(T, B) for each object T of C. The effect of this is that you can define an arrow fromA to B by giving a function αT : Hom(T, A)−→Hom(T, B) for each objectT which prescribes a variable element ofB for each variable element of A(as described in 2.8.2), in such
a way that for eachf :T0−→T, the diagram
Hom(T0, A) - Hom(T0, B) αT0
Hom(T, A) αT- Hom(T, B)
? Hom(f, A)
?
Hom(f, B)
commutes. This can be summed up by saying, ‘An arrow is induced by defining its value on each variable element of its domain, provided that the definition is natural with respect to change of parameters.’
4.5.6 Elements of a set-valued functor Corollary 4.5.4 says that any natural transformation from Hom(C,−) to Hom(D,−) is given by a unique arrow fromD toC, that is, by an element of Hom(D, C) = Hom(D,−)(C).
Remarkably, the result remains true when Hom(D,−) is replaced by an arbitrary set-valued functor.
SupposeF :C −→Setis a functor andC is an object ofC. An element c∈F(C) induces a natural transformation from the representable functor Hom(C,−) toF by the formula
f 7→F(f)(c) (4.33)
That is, iff :C−→C0is an element of Hom(C, C0), the definition of functor requires an induced functionF(f) :F(C)−→F(C0) and this function can be evaluated atc∈F(C).
4.5.7 Proposition Formula (4.33) defines a natural transformation Hom(C,−)−→F
Proof. LetαC0: Hom(C, C0)−→F(C0) takef to F(f)(c) forc∈F(C). We must show that for anyg:C0−→B,
Hom(C, B) -F(B) αB
Hom(C, C0) αC0-F(C0)
? Hom(C, g)
?
F(g) (4.34)
commutes. We have, forf ∈Hom(C, C0),
αB(Hom(C, g)(f)) =αB(g◦f) =F(g◦f)(c)
=F(g)(F(f)(c)) =F(g)(αC0(f)) as required.
4.5 Yoneda Lemma 125 4.5.8 Theorem (Yoneda Lemma) Formula (4.33) defines a one to one correspondence between elements ofF(C)and natural transformations
Hom(C,−)−→F
Proof. Suppose thatcandc0 are different elements ofF(C). Then the nat-ural transformation corresponding toc takes idC to c whereas the one cor-responding toc0 takes idC toc0. Thus the mapping of the Yoneda Lemma is injective.
Supposeβ : Hom(C,−)−→F is a natural transformation. Then we have βC: Hom(C, C)−→F(C). Let c=βC(idC)∈F(C). For any f :C −→C0, the naturality ofβ gives that
βC0(Hom(C, f)(idC)) =F(f)(βC)(idC)
The left hand side isβC0(f) and the right hand side isF(f)(c). Thus β is the natural transformation given by Formula (4.33), so that the mapping of the Yoneda Lemma is surjective.
4.5.9 Definition LetF :C −→Setbe a functor and letcbe an element of F(C) for some objectCofC. If the natural transformation from Hom(C,−) toF induced byc is an isomorphism, thencis auniversal element ofF.
The existence of a universal element means thatFis representable (see 4.5.1).
The converse is also true because a natural isomorphismα: Hom(C,−)−→F is, from the Yoneda lemma, induced by a unique elementcofF(C) and by definitionαis an isomorphism if and only ifcis universal.
The unique elementccan be calculated using the following fact.
4.5.10 Proposition Let α: Hom(C,−)−→F be a natural isomorphism.
The unique elementc∈F(C)inducing αisαC(idC).
Proof. For an arbitraryf :C−→C0,αC0(f) =F(f)(αC(idC)) because this diagram must commute (chase idC around the square):
Hom(C, C0) -F(C0) αC0
Hom(C, C) αC-F(C)
? Hom(C, f)
? F(f)
Then, by Formula (4.33),αC(idC) must be the required unique elementc.
A detailed example of the use of this construction is in the proof of Proposition 5.2.14.
4.5.11 The definition of universal element can be reworded in elementary terms using Formula (4.33), as follows.
4.5.12 Proposition Let F : C −→Set be a functor, C an object of C andc an element ofF(C). Thenc is a universal element ofF if and only if for any objectC0 of C and any elementx∈F(C0)there is a unique arrow f :C−→C0 of C for which x=F(f)(c).
Proof. Ifc is a universal element then the mapping (4.33) must be an iso-morphism, hence every component must be bijective by Theorem 4.2.20. This immediately ensures the existence and uniqueness of the required arrowf. Conversely, the existence and uniqueness of f for each C0 and x∈F(C0) means that there is a bijection αC0 : Hom(C, C0)−→ F(C0) for every C0 which takes f : C −→C0 to F(f)(c). By Proposition 4.5.7, these are the components of a natural transformation, which is therefore a natural iso-morphism by Theorem 4.2.20.
In the case of a functorF :Cop−→Set,cinF(C) is a universal element if for any objectC0 ofC and any elementx∈F(C0) there is a unique arrow f :C0−→Cfor which x=F(f)(c).
4.5.13 Corollary Ifc∈F(C)andc0∈F(C0)are universal elements, then there is a unique isomorphismf :C−→C0 such thatF(f)(c) =c0.
The proof is left as Exercise 10.
Universal elements are considered again in Proposition 13.3.6. The ex-position in [Mac Lane, 1971] uses the concept of universal element (defined in the manner of the preceding proposition) as the central idea in discussing representable functors and adjunction.
4.5.14 Exercises
1. Show that a representable functor preserves terminal objects but not nec-essarily initial objects.
2. Show that HomSet(1,−) is naturally isomorphic to the identity functor onSet. (‘A set is its set of global elements.’ In terms of 4.5.1 this says that a singleton set represents the identity functor onSet.)
3. Show that the arrow functor A:Grf −→Set of 3.1.9 is represented by the graph2 which is pictured as
1 e -2
(Compare Exercise 10 of Section 4.3.)
4.6 Linear sketches 127 4. Show that the set of objects of a small category is ‘essentially the same thing’ as the set of global elements of the category (as an object of Cat), and translate this into a natural isomorphism following the pattern of 4.3.10.
5. Is the set of arrows of a small category the object part of a functor? If it is, is it representable?
6. Prove that any set-valued functorF :C −→Setis naturally isomorphic to a functor for which ifC andD are distinct objects ofC, thenF(C) and F(D) are disjoint sets.
7. LetD:Set−→Setbe the functor for which for a setA,D(A) =A×A, and for a function f : A −→ B, D(f) :A×A −→ B×B is the function defined byD(f)(a1, a2) = (f(a1), f(a2)). Show thatD is representable and find a universal element forD.
8. Show that the second Yoneda embedding J defined in 4.5.5 is full and faithful.
9.† Formulate carefully and prove that the equivalence in the Yoneda Lemma is natural in bothC andF.
10.Verify the claim made in 4.5.13 that if c ∈F(C) and c0 ∈F(C0) are both universal elements of the functorF:C −→Set, then there is a unique isomorphismf :C−→C0 such thatF(f)(c) =c0.