. 11
( 60 .)


categories of modules, etc., the regular epics are characterized as the surjective
homomorphisms and these are closed in this way under pulling back. However,
many familiar categories are not regular. For example neither the category of
topological spaces and continuous maps, nor the category of posets and order
preserving maps, is regular. If you know what an equational theory is, it is useful
to know that the category of models of any equational theory is always regular
(and exact, see below for the de¬nition).
Proposition 1. In a regular category, every arrow f can be written as f = m —¦ e
where m is a monomorphism and e is a regular epimorphism.
Proof. The obvious way to proceed is to begin with an arrow f : A ’ A and form

the kernel pair of f , which can be described symbolically as {(a, b) | f a = f b}.
If this kernel pair is K(f ) ’ ’ A, then let g: A ’ B be the coequalizer of d0
’’ ’
and d . Since f —¦ d = f —¦ d1 , the universal mapping property of coequalizers
1 0

implies there is a unique h: B ’ A such that h —¦ g = f . Now g is a regular

epimorphism by de¬nition. If you try this construction in the category of sets
or groups or, . . . , you will discover that h is always monic and then f = h —¦
g is the required factorization. There are, however, categories in which such
an h is not always monic. We will now show that in a regular category, it
is. Actually, a bit less than regularity su¬ces. It is su¬cient that a pullback
of a regular epimorphism be an epimorphism. Call an arrow a weakly regular
epimorphism if it is gotten as a composite of arrows, each of which is gotten
by pulling back a regular epimorphism. Since a pullback stacked on top of a
pullback is a pullback, it follows that weakly regular epimorphisms are both
closed under pullback (Exercise 8) and under composition and since a pullback
of a regular epimorphism is an epimorphism, every weakly regular epimorphism
is an epimorphism. Next note that since A ’’ B is a regular epimorphism,

f — 1: A — A ’ B — A is a weakly regular epimorphism since

p1 E

f —1 f
c c
B—A p1
is a pullback. Similarly, 1 — f : B — A ’ B — B and hence f — f : A — A ’ B — B
’ ’
is a weakly regular epimorphism. Let K(h) ’ ’ A be the kernel pair of g. The
1.8 Colimits 51
fact that h —¦ g —¦ d0 = f —¦ d0 = f —¦ d1 = h —¦ g —¦ d1 , together with the universal mapping
property of K(h) implies the existence of an arrow k: K(f ) ’ K(h) such that

the left hand square in the diagram
k E K(h) EA
K(f )

(d0 , d1 ) (e0 , e1 ) (1, 1)
c c
E E B—B E A —A
A—A g—g
commutes. The right hand square and the outer squares are pullbacks by def-
inition”they have the universal mapping properties of the kernel pairs. By a
standard property of pullbacks, the left hand square is also a pullback. But g — g
is a weakly regular epimorphism and hence so is k. Now in the square
k E K(h)
K(f )

d0 d1 e0e1
cc cc
A g
we have e0 —¦ k = g —¦ d0 = g —¦ d1 = e1 —¦ k and k is epic and therefore e0 = e1 . But
that means that h is monic, which ¬nishes the argument.

Equivalence relations and exact categories

Let A be a category with ¬nite limits. If A is an object, a subobject (d0 , d1 ): E
’ A — A is called an equivalence relation if it is

ER“1. re¬‚exive: there is an arrow r: a ’ E such that d0 —¦ r = d1 —¦ r = id;

ER“2. symmetric: there is an arrow s: E ’ E such that s—¦d0 = d1 and s—¦d1 = d0 ;

ER“3. transitive: if
q1 E

q2 p2
c c
is a pullback, there is an arrow t: T ’ E such that p1 —¦ t = p1 —¦ q1 and

p2 —¦ t = p2 —¦ q2 .
52 1 Categories
The interpretation of the last point is that E ⊆ A — A, so is a set of ordered
pairs (a1 , a2 ); T ⊆ E — E, so T is a set of ordered 4-tuples (a1 , a2 , a3 , a4 ) such that
(a1 , a2 ) ∈ E and (a3 , a4 ) ∈ E and the condition p1 —¦ q2 = p2 —¦ q1 simply expresses
a3 = a4 . Then the condition p1 —¦ t = p1 —¦ q1 means that t(a1 , a2 , a3 , a4 ) has ¬rst
coordinate a1 and p2 —¦ t = p2 —¦ q2 means that the second coordinate is a4 . So taken
all together, this says that when (a1 , a2 ) ∈ E, (a3 , a4 ) ∈ E and a2 = a3 , then
(a1 , a4 ) ∈ E, which is just transitivity in the usual sense.
If f : A ’ A is an arrow, then the kernel pair of f is an equivalence relation.

It is internally the relation a1 ∼ a2 if and only if f a1 = f a2 . We say that an
equivalence relation is e¬ective if it is the kernel pair of some arrow. Another
term for e¬ective equivalence relation is congruence.
A category is called exact if it is regular and if every equivalence relation is
Proposition 2. Suppose A is a regular, respectively exact, category. Then for
any object A the slice A /A is regular, respectively exact.

Proof. Let us write [b: B ’ A] for an object of A /A. Suppose f : [b: B ’ A]
’ ’
’ [b : B ’ A] is an arrow such that f : B ’ B is a regular epimorphism in
’ ’ ’
A . Then there is a pair of arrows B ’ ’ B whose coequalizer is f . Then we
have the diagram

’ ’ [b: B ’ A] ’f’ [b : B ’ A]
0 1
[b —¦ d = b —¦ d : B ’ A] ’ ’
’ ’ ’ ’
which is a coequalizer in A /A so that f is a regular epimorphism there. Con-
versely, suppose that f : [b: B ’ A] ’ [b : B ’ A] is a regular epimorphism in
’ ’ ’
A /A. Then we have a coequalizer

’ ’ [b: B ’ A] ’f’ [b : B ’ A]
[b : B ’ A] ’ ’
’ ’ ’ ’
Given g: B ’ C such that g —¦ d0 = g —¦ d1 , it is easy to see that we have a morphism

(g, b): [b: B ’ A] ’ [p2 , C — A]. Moreover,
’ ’

(g, b) —¦ d0 = (g —¦ d0 , b —¦ d0 ) = (g —¦ d1 , b ) = (g —¦ d1 , b —¦ d1 ) = (g, b) —¦ d1

so that there is a unique (h, k): [b : B ’ A] ’ [p2 : C — A ’ A] with (h, k) —¦ f =
’ ’ ’
(g, b). This implies that h —¦ f = g and k —¦ f = b. Thus h: B ’ C satis¬es

h —¦ f = g. If h were a di¬erent map for which h —¦ f = g, then (h , k) would be a
1.8 Colimits 53
second map for which (h , k) —¦ f = (g, b), contradicting uniqueness. Thus far we
have shown that f is a regular epic in A if and only if it is so in A /A. If we
have [b: B ’ A] ’ ’ [b : B ’ A] ← ’ [c , C ] and if
’ ’ ’ ’

c c
C g
is a pullback, then it is immediate that for c = c —¦ f = b —¦ g —¦ f = b —¦ f —¦ g = b —¦ g
the square
[c: C ’ A]
’ [b: B ’ A]

c c
E [b : B ’ A]
[c : C ’ A]
’ ’
is a pullback in A . If f is regular epic in A /A it is so in A ; hence f is regular
epic in A and therefore is so in A /A. This proves it for regular categories.
For exact categories, the argument is similar. The previous discussion amounts
to showing that pullbacks and coequalizers are the same in A and A /A. As a
matter of fact, the full story is that all colimits are the same. Not all limits are;
however all pullbacks are and that is all that is used in the de¬nition of exact
category. For example, the terminal object in A /A is [id: A ’ A] and that is

not the terminal object of A (unless A = 1, in which case A /A is equivalent to
A ). See Exercise 6 below.

Exercises 1,8

1. Given two arrows f : A ’ C and g: B ’ D, then there is a unique arrow
’ ’
f + g: A + B ’ C + D for which (f + g) —¦ i1 = i1 —¦ f and similarly for the second

index. Write a formula for f + g in terms of pointed brackets. (Compare the
de¬nition of f — g in Section 1.7.)

2. Let G be a group with subgroup K (not necessarily normal in G). Describe
the coequalizer of the inclusion of K in G and the constant map taking everything
in K to the identity.

3. Show that coequalizers of any two parallel arrows exist in Set and Grp.
54 1 Categories
4. (Coequalizers can be big). Let 1 denote that category with one object and
one arrow, and 2 the category with two objects and exactly one identity arrow,
going from one object to the other. There are exactly two functors from 1 to
2. Show that their coequalizer in the category of categories and functors is the
monoid (N, +) regarded as a category with one object.

5. (a) Show that a coequalizer of two parallel arrows is an epimorphism.
(b) Show that the converse of (a) is true in Set and Grp, but not in general.

6. Prove:
(a) If an equivalence relation is e¬ective and has a coequalizer then it is the
kernel pair of its coequalizer.
(b) If an epimorphism is regular and has a kernel pair then it is the coequalizer
of its kernel pair. (Warning: a parallel pair it coequalizcs need not be its kernel

7. Let C be a small category. Show that any functor F : C op ’ Set is a colimit

of representable functors. (Hint: The required graph I is constructed as follows.
An object of I is a pair (C, c) where c ∈ F C. Thus the set of objects of I is the
disjoint union of all the individual sets F C over all the objects of C . A morphism
in I from (C, c) to (C , c ) is a morphism f : C ’ C such that F f (c ) = c.

The diagram D: I ’ Func(C , Set) is de¬ned by D(C, c) = Hom(’, C) and

Df = Hom(’, f ). Of course we have cheated a bit in calling the morphisms f as
they must also be indexed by the names of their domain and codomain.)

8. Prove the following laws of exponents for the element notation introduced in
Section 1.5:
(a) For all objects T1 and T2 , ∈T1 +T2 = ∈T1 — ∈T2 (an element of A de¬ned on
T1 + T2 is the same as a pair of elements of A, one de¬ned on T1 , and the other
on T2 ).
(b) For all objects A1 and A2 , ∈A1 —A2 = ∈A1 — ∈A2 .

1.9 Adjoint functors
Adjunction of group underlying function

Let A be a set and G be a group. We have noted that for any function from A
to G, in other words for any element of HomSet (A, U G), there is a unique group
1.9 Adjoint functors 55
homomorphism from the free group F A with basis A to G which extends the
given function. This is thus a bijection

HomGrp (F A, G) ’ HomSet (A, U G)


. 11
( 60 .)