In this section, we will turn the subobject construction into a contravariant

functor, by using the inverse image construction described above. To do this, we

need to know ¬rst that the inverse image of a monomorphism is a monomorphism:

Lemma 2. In any category C , in a pullback diagram (3), if g is monic then so

is p1 .

Proof. Consider the diagram below, in which the square is a pullback.

T

d

ddy

xd d

dd‚

d

‚ p2 E

P B (5)

p1 g

c c

EC

A

f

Then P = [(x, y) | f x = gy]. To show that p1 is monic is the same as showing

that if (x, y) ∈T P and (x, y ) ∈T P then y = y . But if (x, y) and (x, y ) are in

P , then g(y) = f (x) = g(y ), so y = y since g is monic.

To turn the subobject construction into a functor, we need more than that

the pullback of monics is monic. We must know that the pullback of a subobject

is a well-de¬ned subobject. In more detail, for A in C , Sub A will be the set

of subobjects of A. If f : B ’ A, then for a subobject represented by a monic

’

g: U ’ A, Sub(f )(g) will be the pullback of g along f . To check that Sub(f ) is

’

well-de¬ned, we need:

Theorem 3. If g: U )’ A and h: V )’ A determine the same subobject, then

’ ’

the pullbacks of g and h along f : B ’ A represent the same subobjects of B.

’

Proof. This follows because the pullback of g is [y | f (y) ∈P U ] and the pullback

A

P

of h is [y | f (y) ∈A V ], which has to be the same since by de¬nition a subobject

is entirely determined by its elements.

The veri¬cation that Sub(f ) is a functor is straightforward and is omitted.

34 1 Categories

Exercises 1.6

1. Show how to describe the kernel of a group homomorphism f : G ’ H as the

’

pullback of f along the map which takes the trivial group to the identity of H.

2. Give an example of a pullback of an epimorphism which is not an epimorphism.

3. Prove that an arrow f : A ’ B is monic if and only if the diagram

’

idA E

A A

f

idA

c c

EB

A

f

is a pullback.

4. (a) Suppose that

B

g

c

EC

A

f

is a diagram in Set with g an inclusion. Construct a pullback of the diagram as

a ¬ber product and as an inverse image of A along f , and describe the canonical

isomorphism between them.

(b) Suppose that g is injective, but not necessarily an inclusion. Find two

ways of constructing the pullback in this case, and ¬nd the isomorphism between

them.

(c) Suppose f and g are both injective. Construct the pullback of Diagram 2

in four di¬erent ways: (i) ¬ber product, (ii) inverse image of the image of g along

f , (iii) inverse image of the image of f along g, (iv) and the intersection of the

images of f and g. Find all the canonical isomorphisms.

(d) Investigate which of the constructions in (c) coincide when one or both

of f and g are inclusions.

5. When g is monic in diagram (1), rede¬ne “Cone” so that

(a) Cone(T, D) = {(x, z) | z ∈ B and f (x) = z}, or equivalently

(b) Cone(T, D) = {x | f (x) ∈ B}.

1.7 Limits 35

Show that each de¬nition gives a functor naturally isomorphic to the Cone

functor originally de¬ned.

6. Identify pullbacks in a poset regarded as a category. Apply this to the powerset

of a set, ordered by inclusion.

7. For two subobjects g: U ’ A and h: V ’ A, say that U ¤ V (or g ¤ h) if

’ ’

g factors through h. Show that this makes the set of subobjects of A a partially

ordered set with a maximum element.

8. In a diagram

EB EC

A

c c c

EE EF

D

(a) Show that if both small squares are pullbacks, so is the outer square.

(b) Show that if the outer square and right hand square are pullbacks, so is

the left hand square.

1.7 Limits

Graphs

A limit is the categorical way of de¬ning an object by means of equations

between elements of given objects. The concept of pullback as described in Sec-

tion 1.6 is a special case of limit, but su¬ciently complicated to be characteristic

of the general idea. To give the general de¬nition, we need a special notion of

“graph”. What we call a graph here is what a graph theorist would probably call

a “directed multigraph with loops”.

Formally, a graph G consists of two sets, a set O of objects and a set A of

arrows, and two functions d0 , d1 : A ’ O. Thus a graph is a “category without

’

composition” and we will use some of the same terminology as for categories: O

is the set of objects (or sometimes nodes) and A is the set of arrows of the

graph; if f is an arrow, d0 (f ) is the source of f and d1 (f ) is the target of f .

A homomorphism F : G ’ H from a graph G to a graph H is a function

’

taking objects to objects and arrows to arrows and preserving source and target;

in other words, if f : A ’ B in G , then F (f ): F (A) ’ F (B) in H .

’ ’

It is clear that every category C has an underlying graph which we denote

|C |; the objects, arrows, source and target maps of |C | are just those of C .

36 1 Categories

Moreover, any functor F : C ’ D induces a graph homomorphism |F |: |C | ’

’ ’

|D|. It is easy to see that this gives an underlying graph functor from the

category of categories and functors to the category of graphs and homomorphisms.

Diagrams

A diagram in a category C (or in a graph G ”the de¬nition is the same) is

a graph homomorphism D: I ’ |C | for some graph I . I is the index graph

’

of the diagram. Such a diagram is called a diagram of type I . For example,

a diagram of the form of 1 of Section 1.6 (which we used to de¬ne pullbacks) is

a diagram of type I where I is the graph

1’ 2← 3

’ ’

D is called a ¬nite diagram if the index category has only a ¬nite number

of nodes and arrows.

We will write D: I ’ C instead of D: I ’ |C |; this conforms to standard

’ ’

notation.

Observe that any object A of C is the image of a constant graph homomor-

phism K: I ’ C and so can be regarded as a degenerate diagram of type I .

’

If D and E are two diagrams of type I in a category C , a natural transfor-

mation »: D ’ E is de¬ned in exactly the same way as a natural transformation

’

of functors (which does not involve the composition of arrows in the domain cat-

egory anyway); namely, » is a family of arrows

»i: D(i) ’ E(i)

’

of C , one for each object i of I , for which

»i E(i)

E

D(i)

D(e) E(e) (1)

c c

E E(j)

D(j)

»j

commutes for each arrow e: i ’ j of I .

’

Commutative cones and limits

A commutative cone with vertex W over a diagram D: I ’ C is a natural

’

transformation ± from the constant functor with value W on I to D. We will

1.7 Limits 37

refer to it as the “cone ±: W ’ D”. This amounts to giving a compatible family

’

{±i} of elements of the vertices D(i) based on W . This commutative cone ± is

an element (in the category of diagrams of type I ) of the diagram D based on

the constant diagram W . The individual elements ±i (elements in C ) are called

the components of the element ±.

Thus to specify a commutative cone with vertex W , one must give for each

object i of I an element ±i of D(i) based on W (that is what makes it a cone)

in such a way that if e: i ’ j is an arrow of I , then D(e)(±i) = ±j (that makes

’

it commutative). This says that the following diagram must commute for all e: i

’ j.

’

W

d

±i d ±j (2)

d

©

d

‚

E D(j)

D(i)

D(e)

Note that in Section 1.6 our de¬nition of commutative cone for pullbacks

does not ¬t our present de¬nition, since we give no arrow to C in Diagram 2.

Of course, this is only a technicality, since there is an implied arrow to C which

makes it a commutative cone. This is why we gave an alternative, but equivalent

construction in terms of three arrows in Section 1.6.

Just as in the case of pullbacks, an arrow W ’ W de¬nes a commutative

’

cone over D with vertex W by composition, thus making Cone(’, D): C ’ Set ’

a contravariant functor. (Cone(W, D) is the set of commutative cones with vertex

W .) Then a limit of D, denoted lim D, is a universal element for Cone(’, D).

Any two limits for D are isomorphic via a unique isomorphism which makes

everything commute. This is stated precisely by the following proposition, whose

proof is left as an exercise.

Proposition 1. Suppose D: I ’ C is a diagram in a category C and ±: W

’

’ D and β: V ’ D are both limits of D. Then there is a unique isomorphism

’ ’

u: V ’ W such that for every object i of I , ±i —¦ u = βi.

’

The limit of a diagram D objecti¬es the set

{x | x(i) ∈ D(i) and for all e: i ’ j, D(e)(x(i)) = x(j)}

’

and so will be denoted

[x | x(i) ∈ D(i) and for all e: i ’ j, D(e)(x(i)) = x(j)]

’

As in the case of pullbacks, implied arrows will often be omitted from the

description. In particular, when y ∈T B and g: A ’ B is a monomorphism we

’

38 1 Categories

will often write “y ∈ A” or if necessary ∃x(g(x) = y) when it is necessary to

specify g.

By taking limits of di¬erent types of diagrams one obtains many well known

constructions in various categories. We can recover subobjects, for example, by

noting that the limit of the diagram g: A ’ B is the commutative cone with

’

vertex A and edges idA and g. Thus the description of this limit when g is monic

is [(x, y) | gx = y] = [y | y ∈ A], which is essentially the same as the subobject

determined by g since a subobject is determined entirely by its elements. In

other words, the monomorphisms which could be this limit are precisely those

equivalent to (in the same subobject as) g in the sense of Section 1.6.

A category C is complete if every diagram in the category has a limit. It is

¬nitely complete if every ¬nite diagram has a limit. Set, Grp and T are all

op

complete.

Products

A discrete graph is a graph with no arrows. If the set {1, 2} is regarded as a

discrete graph I , then a diagram of type I in a category C is simply an ordered

pair of objects of C . A commutative cone over the diagram (A, B) based on T

is simply a pair (x, y) of elements of A and B. Commutativity in this case is a

vacuous condition.

Thus a limit of this diagram represents the set {(x, y) | x ∈ A, y ∈ B} and is

called the product of A and B. It is denoted A — B = [(x, y) | x ∈ A, y ∈ B].

The object B — A = [(y, x) | y ∈ B, x ∈ A] is di¬erently de¬ned, but it is

straightforward to prove that it must be isomorphic to A — B.

It follows from the de¬nition that A — B is an object P together with two