. 14
( 60 .)


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
(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
A Qi
T d T

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:
d D±


  d Dγ
  D± d

Dk Dl

d Dβ 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δ —¦ 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


. 14
( 60 .)