<<

. 8
( 60 .)



>>

The subobject functor

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

<<

. 8
( 60 .)



>>