To attain the uniqueness condition in the de¬nition of universal arrow, we

construct a subobject LA of W A with the property that ζA factors through

RLA via a map ·A: A ’ RLA. It is easy to set that any such ·A is also a weak

’

universal arrow. The idea is to make LA as small as possible so as to obtain the

uniqueness property.

The natural thing to do would be to take LA to be the intersection of all the

equalizers of maps f1 , f2 : W A ’ D such that Rfi —¦ ζA = d for all d: A ’ RD.

’ ’

The trouble is that these equalizers may not form a set. This is where the clever

part of the proof is: Let U = {u: W A ’ W A | Ru —¦ ζA = ζA}. U is a set, in fact

’

a submonoid of the endomorphism monoid of W A. (By dc¬nition of category,

Hom(A, B) is a set for any objects A and B). Then de¬ne w: LA ’ W A to ’

be collective equalizer [z ∈ W A | u(z) = v(z) for all u, v ∈ U ], and let ·A: A

’ RLA be the map induced by the facts that Rw must be an equalizer and ζA

’

equalizes the image of U under R. Clearly ·A is a weak universal arrow, and it

is easy to see that to get the uniqueness property we had to equalize at least the

elements of U . We now show that equalizing the elements of U is enough.

Suppose d: A ’ RD and for i = 1, 2, gi : LA ’ D have the property that

’ ’

Rgi —¦ ·A = d. Let e: E ’ LA be the equalizer of g1 and g2 , so the horizontal

’

part of the following commutative diagram, in which v and z have yet to be

1.9 Adjoint functors 61

constructed, is an equalizer:

A

d

d

d

ν ·A dd

d

d

Rg1 E

© ‚

d

c

E RLA

RE E RD

Re Rg2

d

s

d

d

Rzd Rw

d

d

dc

RW A

Since Re is an equalizer, there is an arrow v making the upper left triangle

commute as shown, and because ζA = Rw —¦ ·A is a weak universal arrow, there

is an arrow z making Rz —¦ ζA = V . It is easy to see that wez ∈ U , whence

wezw = w. Because w is monic, this means that zw is a right inverse to e, which

implies that g1 = g2 as required.

The solution set condition is often shown to be satis¬ed in practice by using

a cardinality condition. For example, if U is the underlying functor from Grp to

Set, in constructing a solution set for a particular set A one can clearly restrict

one™s attention to maps A ’ U G (G a group) with the property that the image

’

of A generates G. Since the cardinality of such a group is bounded by some

cardinal ±, a solution set for A consists of all those pairs (y, B), where B ranges

over the distinct (up to isomorphism) groups of cardinality ¤ a and y over all

functions from A to RB for all such B.

Kan extensions

If A , C and D are categories and F : D ’ C is a functor, then F induces a

’

functor

Func(F, A ): Func(C , A ) ’ Func(D, A )

’

which takes a functor G: C ’ A to G —¦ F (like any homfunctor) and a natural

’

transformation »: G ’ H to »F : G —¦ F ’ H —¦ F . The left Kan extension of

’ ’

a functor T : D ’ A along F is a functor LF (T ): C ’ A with the property

’ ’

62 1 Categories

that there is for each G: C ’ A a bijection

’

Nat(LF (T ), G) ’ Nat(T, G —¦ F )

’

which is natural in G.

In the presence of su¬cient colimits in A one can construct the Kan extension

of a functor T : D ’ A provided that D is a small category. We give the

’

construction and leave the detailed veri¬cations (which are not trivial!) to the

reader.

Given F : D ’ C and T : D ’ A , we must construct LF (T ): C ’ A . For

’ ’ ’

any object C of C , the functor F determines a comma category (F, C) which has

a projection p onto D. We de¬ne LF (T )(C) to be the colimit of the composite

T —¦ p: (F, C) ’ A . An arrow f : C ’ C in C determines a functor from (F, C)

’ ’

to (F, C ) which by the universal property of colimits determines a map

LF (T )(f ): LF (T )(C) ’ LF (T )(C )

’

This makes LF (T ) a functor.

De¬ne the natural transformation ·: T ’ LF (T ) —¦ F by requiring that for

’

each object D of D, ·D is the element of the colimiting cocone to LF (T )(F (D))

at the object (D, idF D , F D) of the comma category (F, F D). For each G: C

’ A , the required bijection

’

Nat(LF (T ), G) ’ Nat(T, G —¦ F )

’

takes »: LF (T ) ’ G to (»F ) —¦ ·. Conversely, given a natural transformation µ: T

’

’ GF and an object C of C , there is a cocone from T —¦ p to GC whose element

’

at an object (D, g, C) of (F, C) is

Gg —¦ µD: T D ’ GF D

’

This induces a map »C: LF (T )(C) ’ GC; these are the components of a natural

’

transformation »: LF (T ) ’ G. The inverse of the bijection just given takes µ

’

to the » thus constructed.

We have immediately from Theorem 1 (the pointwise construction of adjoints):

Proposition 5. In the notation of the preceding paragraphs, if every functor

T : D ’ A has a left Kan extension along F , then Func(F, A ): Func(C , A )

’

’ Func(D, A ) has a left adjoint.

’

Note that by the construction given of Kan extensions, the hypothesis of

Proposition 5 will be true if A is cocomplete.

Right Kan extensions can be de¬ned similarly. A detailed construction of

right Kan extensions is given in Mac Lane [1971].

1.9 Adjoint functors 63

Exercises 1.9

1. Show that the following construction describes the adjoint to the underlying

functor Ab ’ Set: The adjoint takes a set S to the set of all ¬nite sums

’

ns s

s∈S

where for each s ∈ S, ns is an integer, but in any given sum, only ¬nitely many of

them are non-zero. The abelian group structure is just term-wise addition (and

subtraction).

2. Show that the adjoint to the underlying functor CommMon ’ Set takes a set

’

S to the set of all terms

sns

s∈S

where for each s ∈ S, ns is a non-negative integer, but in any given product, only

¬nitely many of them are non-zero.

3. Show that the adjoint to the underlying set functor CommRing ’ Set can be

’

described as the composite of adjoints in Exercise 1 and Exercise 2. In detail: if

S is a set, then the free commutative ring, which we will call Z[S] since it is, in

fact the ring of polynomials in S is gotten by ¬rst forming the free commutative

monoid generated by S and then the free abelian group generated by that. It is

still a monoid, since the distributive law of multiplication tells us how to multiply

sums of monomials. The general process by which two such free functors can be

composed was ¬rst studied by Jon Beck under the name “distributive laws” [Beck,

1969].

4. Let A: C ’ C — C be the diagonal functor. Find left and right adjoints to A.

’

Assume that C has whatever limits and colimits you need. These are examples

of Kan extensions along the (unique) functor 1 + 1 ’ 1.

’

5. Show that if two composable functors each have a left adjoint, then so does

their composite.

6. Show that the functor which takes a set to its set of nonempty ¬nite subsets

and a function to its direct image function is the left adjoint to the underlying

functor from the category of upper semilattices (see Exercise 14 of Section 1.2).

7. Find left and right adjoints for the functor which takes an R-module (any

¬xed ring R) to its underlying Abelian group.

64 1 Categories

8. (a) For a ¬xed group G, let G ’ Act denote the category of G-actions and

equivariant maps. Let U be the forgetful functor. Construct a left adjoint for U .

(Hint: it takes a set A to G — A.)

(b) What about a right adjoint?

9. (a) Show that the underlying set functor from T to Set has a left adjoint

op

which takes a set to that set regarded as a discrete topological space.

(b) Show that the underlying set functor in (a) also has a right adjoint.

10. De¬ne four functors π0 , U : Cat ’ Set and D, G: Set ’ Cat as follows:

’ ’

(i) For any category C , U C is the set of objects of C . For a functor F , U F is

what F does to objects.

(ii) For a category C , π0 (C ) is the set of connected components of C ”two

objects x and y are in the same component if and only if there is a ¬-

nite sequence x = x0 , x1 , . . . , xn = y of objects of C and a ¬nite sequence

a1 , . . . an’1 of arrows of C with for each i = 1, . . . , n’1, either ai : xi ’ xi+1

’

or, ai : xi+1 ’ xi . A functor F induces π0 F in the obvious way (it is easy

’

to see that a functor takes a component into a component).

(iii) For any set A, DA is the category whose set of objects is A and whose only

arrows are identity arrows (DA is the discrete category on A). DF for

a function F takes an object x to F (x) and is forced on arrows.

(iv) For a set A, GA is the category whose objects are the elements of A, with

exactly one arrow between any two elements. (It follows that every arrow

is an isomorphism. - i.e., GA is a groupoid). What G does to functions is

forced.

Prove that: π0 is left adjoint to D, D is left adjoint to U , and U is left adjoint

to G.

11. Show that the “underlying graph functor” U : Cat ’ Grph de¬ned in Sec-

’

tion 1.7 has a left adjoint. (Hint: If G is a graph, F G will have the same objects

as G, and nonidentity arrows will be “composable sequences” of arrows of G.)

12. Assume that L: C ’ D is left adjoint to R: D ’ C . Prove:

’ ’

(a) R is faithful if and only if the counit D is epic for every object D of D.

(Hint: The map which Yoneda gives from the natural transformation Hom(’D)

’ Hom(R(’), RD) ’ Hom(LR(’), D) must be the counit at D. Now reread

’ ’

the de¬nition of epimorphism in Section 1.4).

1.9 Adjoint functors 65

(b) R is full if and only if the counit is a split monic at every object of D.

(c) L is faithful if and only if the unit is monic for every object of C .

(d) L is full if and only if the unit is a split epic at every object of C .

(e) R is an equivalence of categories if and only if the unit and counit are

both natural isomorphisms.

(f ) If R is an equivalence of categories, then so is L and moreover then L is

also a right adjoint to R.

13. Show that if A is a category with ¬nite products and A is an object of A ,

then the functor from the slice category (see Section 1.1) A /A ’ A that sends

’

the object B ’ A to B”the so-called forgetful functor”has a right adjoint,

’

B ’ B — A ’ A.

’

14. Let Mon denote the category of monoids and homomorphisms and Cat the

category of categories and functors. De¬ne L: Mon ’ Cat as follows: For a

’

monoid M , the objects of LM are the elements of M . An arrow is a pair (k, m)

of elements of M ; it has domain m and codomain km. Composition is given by

the formula

(k , km) —¦ (k, m) = (k k, m)

If h: M ’ N is a homomorphism, Lh(k, m) = (hk, hm). Construct a left adjoint

’

for L.

15. (a) Show that if L: C ’ D is left adjoint to R: D ’ C with unit · and

’ ’

counit , then R —¦ ·R is the identity natural transformation on R and L —¦ L· is

the identity natural transformation on L.

(b) Show that if L: C ’ D and R: D ’ C are functors and ·: idC ’ R —¦ L

’ ’ ’

and : L —¦ R ’ idD are natural transformations satisfying the conclusion of (a),