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}.

d0

If this kernel pair is K(f ) ’ ’ A, then let g: A ’ B be the coequalizer of d0

’’ ’

’’

’’

d1

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

A—A A

f —1 f

c c

EB

B—A p1

is a pullback. Similarly, 1 — f : B — A ’ B — B and hence f — f : A — A ’ B — B

’ ’

e0

is a weakly regular epimorphism. Let K(h) ’ ’ A be the kernel pair of g. The

’’

’’

’’

e1

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 c

E E B—B E A —A

A—A g—g

h—h

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

EB

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

T E

q2 p2

c c

EA

E

p1

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

e¬ective.

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

’ ’ ’

0

d

A . Then there is a pair of arrows B ’ ’ B whose coequalizer is f . Then we

’’

’’

’’

d1

have the diagram

d0

’ ’ [b: B ’ A] ’f’ [b : B ’ A]

’’

0 1

[b —¦ d = b —¦ d : B ’ A] ’ ’

’ ’ ’ ’

’’

1

d

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

d0

’ ’ [b: B ’ A] ’f’ [b : B ’ A]

’’

[b : B ’ A] ’ ’

’ ’ ’ ’

’’

1

d

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

g

f

have [b: B ’ A] ’ ’ [b : B ’ A] ← ’ [c , C ] and if

’ ’ ’ ’

gE

C B

f

f

c c

EB

C g

is a pullback, then it is immediate that for c = c —¦ f = b —¦ g —¦ f = b —¦ f —¦ g = b —¦ g

the square

gE

[c: C ’ A]

’ [b: B ’ A]

’

f

f

c c

E [b : B ’ A]

[c : C ’ A]

’ ’

g

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

pair.)

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)

’