then L is left adjoint to R and · and are the unit and counit of the adjunction.

16. (a) Show that if L and R are as in (a) of Exercise 15 then for any objects A

of C and B of D and any arrow f : A ’ RB of C there is a unique arrow g: LA

’

’ B of D for which Rg —¦ ·A = f . (This generalizes a well-known property of

’

free groups).

(b) State a dual version of (a) using .

17. A full subcategory D of a category C is re¬‚ective if the inclusion has a left

adjoint, which is called the re¬‚ector.

(a) Show that D is a re¬‚ective subcategory of C if and only if for each object

A of C there is an object LA of D and an arrow e: A ’ LA with the property

’

66 1 Categories

that if f : A ’ B is any arrow with B an object of D then there is a unique

’

arrow h: LA ’ B for which f = h —¦ e.

’

(b) Show that if D is a re¬‚ective subcategory of C then the re¬‚ector takes

an object B of D to an object isomorphic to B.

(c) If D is a re¬‚ective subcategory of C with inclusion I and re¬‚ector L,

show that an object C of C is isomorphic to an object coming from D if and

only if for each object D of D the counit ILD ’ D induces Hom(D , D) ∼

’ =

Hom(ILD , D).

(d) Show that the category of Abelian groups is a re¬‚ective subcategory of

the category of groups.

(e) Show that the category of ¬nite sets is not a re¬‚ective subcategory of the

category of all sets.

18. Show that a functor R: C ’ Set being representable is equivalent to the

’

solution set condition being satis¬ed uniquely with a singleton solution set

19. Here is another way of organizing the proof of Freyd™s Adjoint Functor

Theorem.

(a) Show that U : D ’ C has an adjoint if and only if for each object C of

’

C , the comma category (C, U ) has an initial object.

(b) Show that if D has and U preserves limits, then (C, U ) is complete.

(Compare Exercise 7 of Section 1.7.)

(c) Show that the solution set condition is equivalent to (C, U ) having a weak

initial set, that is a small set of objects with the property that every object is the

codomain of at least one morphism whose domain lies in that set.

(d) Show that a category with products and a weak initial set has a weak

initial object.

(e) Show that if A is a weak initial object and E ’ A the simultaneous

’

equalizer of all the endomorphisms, then E is initial.

(f ) Deduce Freyd™s adjoint functor theorem (usually known as the G(eneral)

A(djoint) F(unctor) T(heorem) to distinguish it from the SAFT or Special Ad-

joint Functor Theorem which follows.)

20. A category is said to be well powered if every object has only a small set

of subobjects. A set {Qi } of objects of a category is said to be a cogenerating

set if for any pair of objects C and D of the category and any pair of distinct

morphisms f, a: C ’ D, there is at least one Qi and one morphism h: D ’ Qi

’ ’

with hf = hg.

1.10 Filtered colimits 67

(a) Show that a set {Qi } of objects of a complete category is a cogenerating

set if and only if every object has a monomorphism into some product of those

objects (allowing repetitions).

The Special Adjoint Functor Theorem states that a functor that preserves

limits and whose domain is well powered, complete and has a cogenerating set has

a left adjoint. Demonstrate this theorem by following the steps below. Assume

the hypotheses in each of the steps. The organization of this proof is due to G.

M. Kelly.

(b) Show that it is su¬cient to prove that a category satisfying the hypotheses

has a weak initial set. (See the preceding exercise.)

(c) Show that every object has a unique smallest subobject.

(d) Show that every object which its own smallest subobject can be embed-

ded into a product of members of the cogenerating set in which there are no

repetitions. (Hint: Consider a diagram

E

A Qi

T d T

d

d

d

‚

d

E

T Ti

A0 Q

in which the bottom right corner is an irredundant product, i.e., a product with

no repetitions.)

(e) Show that the set of all subobjects of irredundant products of members

of the cogenerating set forms a weak initial set.

(f ) Conclude the SAFT.

1.10 Filtered colimits

The path category of a graph

In a graph G , a path from a node i to a node j of length n is a sequence

(±1 , ±2 , . . . , ±n ) of (not necessarily distinct) arrows for which

(i) source(±1 ) = i,

(ii) target(±i’1 ) = source(±i ) for i = 2, . . . , n, and

68 1 Categories

(iii) target(±n ) = j.

By convention, for each node i there is a unique path of length 0 from i to i that

is denoted (). It is called the empty path at i. We will write ± = ±n —¦ · · · —¦ ±1 . If

also β = βm —¦· · · —¦β1 is a path from j ’ k, then we let β —¦± = βm —¦· · · —¦β1 —¦±n —¦· · · —¦±1 .

’

The empty path is an identity for this operation and it is clear that the paths

form a category, called the path category of G . We will make no use of this

category, however, but we do need the notion of path in the discussion of ¬ltered

colimits below.

Filtered colimits

Suppose D: I ’ C is a diagram. For a path ±: i ’ j of the form

’ ’

± ± ±

’1 ’2 ’n

i = i0 ’ ’ i1 ’ ’ · · · ’ ’ in = j

’ ’ ’

and a diagram D: I ’ C , de¬ne D± = D±n —¦ · · · —¦ D±2 —¦ D±1 . We also de¬ne

’

D on the empty path at i to be idDi . It is clear that if ±: i ’ j and β: j ’ k

’ ’

are paths, then D(β —¦ ±) = Dβ —¦ D±.

A diagram D: I ’ C is called ¬ltered if

’

(i) Given two objects i and j of I , there is an object k and paths ±: i ’ k

’

and β: j ’ k;

’

±

(ii) Given two paths i ’ ’ j there is an object k and a path γ: j ’ k such

’ ’

’’’

β

that Dγ —¦ D± = Dγ —¦ Dβ.

The slight awkwardness of this de¬nition is the price we must pay for using

index graphs instead of index categories.

A colimit taken over a ¬ltered diagram is called a ¬ltered colimit. The main

signi¬cance is that ¬ltered colimits commute with ¬nite limits in Set and many

other interesting categories.

The following theorem is stated as it is in case you know what a ¬nitary

equational theory is.

Theorem 1. For any equational theory Th, the underlying set functor on the

category of models preserves ¬ltered colimits.

Proof. We will prove this for the special case of abelian groups. The only property

of abelian groups used is that every operation is ¬nitary, that is a function of only

¬nitely many arguments. Suppose D: I ’ Ab is a ¬ltered diagram. Let U : Ab

’

1.10 Filtered colimits 69

’ Set be the underlying set functor. Form the disjoint union I∈Ob(I ) U Di. If

’

x is an element of U Di we will denote it by x, i to keep track of the disjoint

union. Now make the identi¬cation x, i = x , i if there is an object j ∈ I

and there are paths ±: i ’ j and ± : i ’ j such that U D±x = U D± x .

’ ’

This is an equivalence relation. It is obviously symmetric and re¬‚exive. If also

x , i = x , i , then there is a j ∈ I and β: i ’ j and β : i ’ j such that

’ ’

Dβx = Dβ x . There is a k ∈ I and paths γ: j ’ k and γ : j ’ k . Finally

’ ’

there is an l ∈ I and a path δ: k ’ l such that Dδ —¦ D(γ —¦ ± ) = Dδ —¦ D(γ —¦ β).

’

The diagram in question looks like:

Di

d

d D±

d

d

‚

Dj

d

d Dγ

D± d

d

‚

DδE

Dk Dl

Di

d

d Dβ Dγ

d

‚

d

Dj

Dβ

Di

Then

U D(δ —¦ γ —¦ ±)x = (U Dδ —¦ U Dγ —¦ U D±)x = (U Dδ —¦ U Dγ —¦ U D± )x

= (U Dδ —¦ U Dγ U Dβ)x = (U Dδ —¦ U Dγ U Dβ )x

—¦ —¦

= U D(δ —¦ γ β )x

—¦

Now, given two elements x, i and x , i , we add them by ¬nding a j ∈ I

and paths ±: i ’ j and ± : i ’ j. Then we de¬ne x, i + x i = U D±x +

’ ’

U D±x , j . The proofs that this does not depend on the choice of paths and gives

an associative addition are left to the reader. The 0 element is 0, i for any i.

Since all the D± are group homomorphisms, all the 0 elements are identi¬ed, so

this makes sense. Similarly, we can take ’ x, i = ’x, i . The associativity, the

70 1 Categories

fact that 0, i is a 0 element and that ’ x, i is the negative of x, i all have to

be veri¬ed. We leave these details to the reader as well. What we want to do

is show that the set C of these pairs with this notion of equality is the colimit

of U D and, when it is given the group structure described above, it is also the

colimit of D. We actually show the latter, since the argument for the former is a

proper subset.

First observe that there is a cocone u: D ’ A de¬ned by ux = x, i when

’

x ∈ Di. This is a group homomorphism since to form the sum x, i + x , i we

can take the empty path from i ’ i and then the sum is x + x , i . It is a cone

’

since for any ±: i ’ j in I , ux = x, i = D±x, j = u D±x . If f : D ’ A

’ ’

is any other cone, de¬ne v: C ’ A by v x, i = (f i)x. Suppose x, i = x , i .

’

There a j and paths ±: i ’ j and ± : i ’ j such that D±x = D± x . Then

’ ’

v x, i = f i x = f j —¦ D± x = f j —¦ d± x = v x , j

and so v is well de¬ned. Evidently, v —¦ u = f and v is the unique arrow with that

property. Till now, we have not used the group structure on A and this argument

shows that this is the colimit in Set. But A is an abelian group and the elements

of the cone are group homomorphisms. For x, i , x , i ∈ C, choose j and ±: i

’ j and ±: i ’ j. Then

’ ’

v( x, i + x , i ) = v(D±x + D± x ) = (f j)(D±x + D± x )

= (f j)(D±x) + (f j)(D± x ) = (f i)x + (f i )x

This shows that v is a group homomorphism and shows that u: D ’ C is the

’

colimit in Ab. But, as remarked, a subset of this argument shows that U u: U D

’ U C is the colimit in Set and so U preserves this colimit.

’

The following result is actually a special case of the fact that ¬ltered colimits

commute with all ¬nite limits.

Proposition 2. Suppose f : D ’ E is a natural transformation between two

’

¬ltered diagrams from I to the category of models such that f i: Di ’ Ei is

’

monomorphism for each i ∈ Ob(I ). Then the induced map colim D ’ colim E

’

is also monic.

Proof. Suppose x, i and x , i are two elements of colim D such that (f i)x, i =

(f i )x , i in colim E. Then there is a j and paths ±: i ’ j and ± : i ’ j such