’ ’

A and y of B based on T there is a unique element (x, y) of A — B based on T

such that p1 (x, y) = x and p2 (x, y) = y. These arrows are conventionally called

the projections, even though they need not be epimorphisms. Conversely, any

element h of A — B based on T must be of the form (x, y) for some elements of A

and B respectively based on T : namely, x = p1 (h) and y = p2 (h). In other words,

there is a canonical bijection between Hom(T, A—B) and Hom(T, A)—Hom(T, B)

(this is merely a rewording of the statement that A — B represents {(x, y): x ∈

A, y ∈ B}).

Note that (x, x ) and (x , x) are distinct elements of A — A if x and x are

distinct, because p1 (x, x ) = x, whereas p1 (x , x) = x . In fact, (x, x ) = (p2 , p1 ) —¦

(x, x ).

1.7 Limits 39

If f : A ’ C and g: B ’ D, then we de¬ne

’ ’

f — g = (f —¦ p1 , g —¦ p2 ): A — B ’ C — D

’

Thus for elements x of A and y of B de¬ned on the same object, (f —g)(x, y) =

(f (x), g(y)).

It should be noted that the notation A — B carries with it the information

about the arrows p1 and p2 . Nevertheless, one often uses the notation A — B to

denote the object P ; the assumption then is that there is a well-understood pair

of arrows which make it the genuine product. We point out that in general there

may be no canonical choice of which object to take be X — Y , or which arrows as

projections. There is apparently such a canonical choice in Set but that requires

one to choose a canonical way of de¬ning ordered pairs.

In a poset regarded as a category, the product of two elements is their in¬mum,

if it exists. In a group regarded as a category, products don™t exist unless the

group has only one element. The direct product of two groups is the product in

Grp and the product of two topological spaces with the product topology is the

product in T There are similar constructions in a great many categories of sets

op.

with structure.

The product of any indexed collection of objects in a category is de¬ned analo-

gously as the limit of the diagram D: I ’ C where I is the index set considered

’

as the objects of a graph with no arrows and D is the indexing function. This

product is denoted i∈I Di, although explicit mention of the index set is often

omitted. Also, the index is often subscripted as Di if that is more convenient.

One particular case of a product is the product over the empty index set; this is

necessarily a terminal object (Exercise 1).

There is a general associative law for products which holds up to isomorphism;

for example, for any objects A, B and C, (A—B)—C is isomorphic to A—(B —C),

and both are isomorphic to A — B — C, meaning the product over a three-element

index set with D1 = A, D2 = B and D3 = C.

There is certainly no reason to expect two objects in an arbitrary category

to have a product. A category has products if any indexed set of objects in

the category has a product. It has ¬nite products if any ¬nite indexed set of

objects has a product. By an inductive argument (Exercise 2), it is su¬cient for

¬nite products to assume an empty product and that any pair of objects has a

product. Similar terminology is used for other types of limits; in particular, a

category C has ¬nite limits or is left exact if every diagram D: I ’ C in ’

which I is a ¬nite graph, has a limit. A functor is left exact if it preserves ¬nite

limits; it is continuous if it preserves limits of all small diagrams. A category has

designated ¬nite limits if it has the additional structure of an operation that

40 1 Categories

takes each ¬nite diagram to a speci¬c limit cone over that diagram. One de¬nes

categories with designated products, designated limits, designated pullbacks, and

so on, in the same manner.

Algebraic structures in a category

The concept of product allows us to de¬ne certain notions of abstract algebra

in a category. Thus a binary operation on an object A of a category is an arrow

m: A — A ’ A (so of course, the product must exist). For elements x, y of A

’

de¬ned on T , we write xy for m(x, y) just as in sets. Observe that the expression

xy is de¬ned only if x and y are elements of A de¬ned on the same object. We

will use in¬x notation for symbols for binary operations such as +.

The operation m is commutative if xy = yx for all elements x and y of A;

spelled out, m(x, y) = m(y, x) for all elements x and y of A de¬ned on the same

object. The operation is associative if (xy)z = m(m(x, y), z) = m(x, m(y, z)) =

x(yz) for all elements x, y, and z de¬ned on the same object.

Thus a group in a category is an object G of the category together with an

associative binary operation on G, a function i: G ’ G, and a global element

’

e of G with the properties that e()x = xe() = x and xi(x) = i(x)x = e for all

x ∈ G. (In notation such as “e()x”, the element () is assumed to have the same

domain as x.) Abelian groups, rings, R-modules, monoids, and so on can all be

de¬ned in this way.

Equalizers

The equalizer of two arrows f, g: A ’ B (such arrows are said to be paral-

’

lel) is the object [x ∈ A | f (x) = g(x)]. As such this does not describe a commu-

tative cone, but the equivalent expression [(x, y) | x ∈ A, y ∈ B, f (x) = g(x) = y]

does describe a commutative cone, so the equalizer of f and g is the limit of the

diagram

f

A’’B’

’’

’

g

We will also call it Eq(f, g). In Set, the equalizer of f and g is of course the

set {x ∈ A | f (x) = g(x)}. In Grp, the kernel of a homomorphism f : G ’ H is

’

the equalizer of f and the constant map at the group identity.

1.7 Limits 41

Equivalence relations and kernel pairs

In Set, an equivalence relation E on a set A gives rise to a quotient set A/E,

the set of equivalence classes. In this section, we will explore the two concepts

(equivalence relations and kernel pairs) in an arbitrary category. In exercises here

and in Section 1.8 we explore their connection with the concept of coequalizer,

which is de¬ned there. In a category C that has ¬nite limits, an equivalence

relation on an object A is a subobject (u, v): E ’ A — A which is re¬‚exive,

’

symmetric and transitive: for any elements x, y, z of A based on T , the following

must be true:

1. (x, x) ∈T E.

2. If (x, y) ∈T E then so is (y, x).

3. If (x, y) and (y, x) are both in E then so is (x, z).

These de¬nitions can be translated into statements about diagrams (see Ex-

ercise 19).

The two projections

E’ A

’

’’

of an equivalence relation E )’ A — A are also called the equivalence relation.

’

Exercise 18 describes conditions on a parallel pair of arrows which make it an

equivalence relation, thus giving a de¬nition which works in categories without

products.

Related to this is the concept of kernel pair. If f : A ’ B is any arrow of

’

C , a parallel pair of arrows h: K ’ A, k: K ’ A is a kernel pair for f if

’ ’

f —¦ h = f —¦ k and whenever s, t: L ’ A is a pair of arrows for which f —¦ s = f —¦ t,

’

then there is a unique arrow j: L ’ K for which s = h —¦ j and t = k —¦ j. K is the

’

pullback of f along itself and h and k are the projections (Exercise 20). Thus

K = [(x, x ) | f —¦ x = f —¦ x ]. In Set, an equivalence relation (u, v) is the kernel

pair of its class map.

Existence of limits

The existence of some limits sometimes implies the existence of others. We

state a theorem giving the most useful variations on this theme.

Proposition 2.

(a) In any category C , the following are equivalent:

(i) C has all ¬nite limits.

42 1 Categories

(ii) C has a terminal object, all equalizers of parallel pairs, and all binary

products.

(iii) C has a terminal object and all pullbacks.

(b) A category C has all limits if and only if it has all equalizers of parallel

pairs and all products.

Proof. For (a), that (i) implies (iii) is trivial, and that (iii) implies (ii) follows

from Exercise 4.

The construction that shows (ii) implies (i) and the construction for the hard

half of (b) are essentially the same.

With a terminal object and binary products, we get, by induction, all ¬nite

products. Given a diagram D: I ’ C , with I a non-empty ¬nite graph, we

’

let A = i∈ObI Di and B = ±∈ArI cod ±. We de¬ne two arrows f, g: A ’ B ’

by p± —¦ f = ± —¦ pdom ± and p± —¦ g = pcod ± . This means that the following diagrams

commute.

gE

fE

Di cod ± i∈ObI Di cod ±

i∈ObI ±∈ArI ±∈ArI

d

pdom ± p± pcod ±d p±

d

c c ‚©

d

E D cod ±

D dom ± D cod ±

±

h

If E ’ ’ Di is an equalizer of f and g, then f —¦ h = g —¦ h expresses the fact

’

that h: E ’ D is a cone, while the universal mapping property into the equalizer

’

expresses the universality of that cone. As for the empty cone, its limit is the

terminal object.

By suitable modi¬cations of this argument, we can show that a functor pre-

serves ¬nite limits if and only if it preserves binary products, the terminal object

and equalizers.

Preservation of limits

Let D: I ’ C be a diagram and F : C ’ B be a functor. Let d: lim D ’ D

’ ’ ’

be a universal element of D. We say that F preserves lim D if F d: F (lim D) ’’

F D is a universal element of F D. The following proposition gives an equivalent

condition for preserving a limit.

1.7 Limits 43

Proposition 3. F preserves the limit of D if and only if F D has a limit

d : lim F D ’ F D and there is an isomorphism g: F (lim D) ’ lim F D with

’ ’

the property that for any object T ,

F E Hom(F T, F (lim D))

Hom(T, lim D)

d

d Hom(F T, g)

d

d

‚

Hom(T, A) Hom(F T, F d) Hom(F T, lim F D)

Hom(F T, d )

c c

©

E Cone(F T, F D)

Cone(T, D)

F

commutes.

The proof is trivial, but we include this diagram because it is analogous to a

later diagram (Diagram (3), Section 5.3) which is not so trivial.

Requiring that lim F D ∼ F (lim D) is not enough for preservation of limits

=

(see Exercise 16).

Given any arbitrary class of diagrams each of which has a limit in C , the

functor F preserves that class of limits if it preserves the limit of each diagram

in that class. We say, for example, that F preserves all limits (respectively

all ¬nite limits) if it preserves the limit of every diagram (respectively every

¬nite diagram). F preserves products (respectively ¬nite products) if F preserves

the limit of every discrete diagram (respectively every ¬nite discrete diagram).

To preserve ¬nite products it is su¬cient to preserve terminal objects and each

product of two objects.

A functor which preserves ¬nite limits is called left exact. This coincides

with the concept with the same name when the functor goes from a category of

R-modules to Ab.

A functor F : C ’ B creates limits of a given type if whenever D: I ’ C

’ ’

is a diagram of that type and d: lim F D ’ F D is a universal element of F D,

’

then there is a unique element u: X ’ D for which F u = d and moreover u is a

’

universal element of D. The underlying set functor from Grp to Set creates limits.

For example, that it creates products is another way of stating the familiar fact

that given two groups G and H there is a unique group structure on G—H (really

on U G — U H) making it the product in Grp.

F re¬‚ects limits of a given type if whenever D: I ’ C is a diagram of that

’

type, d: lim F D ’ F D is a universal element of F D and c is a cone to D for

’

which F c = d, then c is a universal element of D.

44 1 Categories

Exercises 1.7

1. Show that an object T is the terminal object if and only if it is the product

of the empty set of objects.

2. (a) Let A, B and C be objects in a category. Show how (A — B) — C) and

A — (B — C) can both be regarded as the product of A, B and C (by ¬nding

appropriate projection maps), so that they are isomorphic.

(b) Let C be category with an empty product and with the property that

any two objects have a product. Show that C has all ¬nite products.

(c) If you really care, state and prove a general associative law saying that

any way of meaningfully parenthesizing a sequence of objects of a category with

products gives a product which is isomorphic to that given by any other way of

parenthesizing the same sequence.

3. Show that in a category with a terminal object 1, the product A — 1 exists

for any object A and is (up to isomorphism) just A itself equipped with the

projections id: A ’ A and (): A ’ 1.

’ ’

4. Prove that in a category with ¬nite products, the equalizer of