<<

. 7
( 60 .)



>>



is a full and faithful functor from C to Func(C op , Set).

Proof. It is easy to verify that the maps de¬ned in the Theorem are functors.
The fact that the ¬rst one is full and faithful follows from the Yoneda Lemma
with Hom(A, ’) in place of F . The other proof is dual.
The induced maps in the Theorem deserve to be spelled out. If f : S ’ ’
T , the natural transformation corresponding to f given by (i) has component
Hom(f, A): Hom(T, A) ’ Hom(S, A) at an object A of C ”this is composing by

T
f on the right. If x ∈ A, the action of Hom(f, A) “changes the parameter” in
A along f .
The other natural transformation corresponding to f is Hom(T, f ): Hom(T, A)
’ Hom(T, B); since the Yoneda embedding is faithful, we can say that f is

essentially the same as Hom(’, f ). If x is an element of A based on T , then
Hom(T, f )(x) = f —¦ x. Since “f is essentially the same as Hom(’, f )”, this
justi¬es the notation f (x) for f —¦ x introduced in Section 1.4.
The fact that the Yoneda embedding is full means that any natural transfor-
mation Hom(’, A) ’ Hom(’, B) determines a morphism f : A ’ B, namely
’ ’
the image of idA under the component of the transformation at A. Spelled out,
this says that if f is any function which assigns to every element x: T ’ A an

element f (x): T ’ B with the property that for all t: S ’ T , f (x —¦ t) = f (x) —¦ t
’ ’
(this is the “coherence condition” mentioned in Section 1.4) then f “is” (via the
Yoneda embedding) a morphism, also called f to conform to our conventions,
from A to B. One says such an arrow exists “by Yoneda”.
In the same vein, if g: 1 ’ A is a morphism of C , then for any object T , g

determines an element g( ) of A de¬ned on T by composition with the unique
element from T to 1, which we denote ( ). This notation captures the perception
that a global element depends on no arguments. We will extend the functional
notation to more than one variable in Section 1.7.
28 1 Categories
Universal elements

Another special case of the Yoneda Lemma occurs when one of the elements
of F de¬ned on Hom(A, ’) is a natural isomorphism. If β: Hom(A, ’) ’ F is ’
such a natural isomorphism, the (ordinary) element u ∈ F A corresponding to it
is called a universal element for F , and F is called a representable functor,
represented by A. It is not hard to see that if F is also represented by A , then
A and A are isomorphic objects of C . (See Exercise 4, which actually says more
than that.)
The following lemma gives a characterization of universal elements which in
many books is given as the de¬nition.
Lemma 3. Let F : C ’ Set be a functor. Then u ∈ F A is a universal element

for F if and only if for every object B of C and every element t ∈ F B there is
exactly one arrow g: A ’ B such that F g(u) = t.

Proof. If u is such a universal element corresponding to a natural isomorphism
β: Hom(A, ’) ’ F , and t ∈ F B, then the required arrow g is the element

’1
(β B)(t) in Hom(A, B). Conversely, if u ∈ F A satis¬es the conclusion of the
Lemma, then it corresponds to some natural transformation β: Hom(A, ’) ’ F’
by the Yoneda Lemma. It is routine to verify that the map which takes t ∈ F B
to the arrow g ∈ Hom(A, B) given by the assumption constitutes an inverse in
Func(C , Set) to βB.
In this book, the phrase “u ∈ F A is a universal element for F ” carries with
it the implication that u and A have the property of the lemma. (It is possible
that u is also an element of F B for some object B but not a universal element
in F B.)
As an example, let G be a free group on one generator g. Then g is the
“universal group element” in the sense that it is a universal element for the
underlying set functor U : Grp ’ Set (more precisely, it is a universal element

in U G). This translates into the statement that for any element x in any group
H there is a unique group homomorphism F : G ’ H taking g to x, which is

exactly the de¬nition of “free group on one generator g”.
Another example which will play an important role in this book concerns
the contravariant powerset functor P: Set ’ Set de¬ned in Section 1.2. It is

straightforward to verify that a universal element for P is the subset {1} of
the set {0, 1}; the function required by the Lemma for a subset B0 of a set
B is the characteristic function of B0 . (A universal element for a contravariant
functor, as here”meaning a universal element for P: Setop ’ Set”is often called

a “couniversal element”.)
1.6 Pullbacks 29
Exercises 1.5

1. Find a universal element for the functor

Hom(’, A) — Hom(’, B): Setop ’ Set


for any two sets A and B. (If h: U ’ V , this functor takes a pair (f, g) to

(h —¦ f, h —¦ g).)

2. (a) Show that an action of a group G on a set A is essentially the same thing
as a functor from G regarded as a category to Set.
(b) Show that such an action has a universal element if and only if for any
pair x and y of elements of A there is exactly one element g of G for which gx = y.

3. Are either of the covariant powerset functors de¬ned in Exercise 6 of Sec-
tion 1.2 representable?

4. Let F : C ’ Set be a functor and u ∈ F A, u ∈ F A be universal elements for

F . Show that there is a unique isomorphism φ: A ’ A such that F φ(u) = u .


5. Let U : Grp ’ Set be the underlying set functor, and F : Set ’ Grp the
’ ’
functor which takes a set A to the free group on A. Show that for any set A, the
covariant functor HomSet (A, U (’)) is represented by F A, and for any group G,
the contravariant functor HomGrp (F (’), G) is represented by U G.


1.6 Pullbacks
The set P of composable pairs of arrows used in Section 1.1 in the alternate
de¬nition of category is an example of a “¬bered product” or “pullback”. A
pullback is a special case of “limit”, which we treat in Section 1.7. In this section,
we discuss pullbacks in detail.
Let us consider the following diagram D in a category C .
B

g
(1)
c
EC
A
f
We would like to objectify the set {(x, y) | f (x) = g(y)} in C ; that is, ¬nd
an object of C whose elements are those pairs (x, y) with f (x) = g(y). Observe
30 1 Categories
that for a pair (x, y) to be in this set, x and y must be elements of A and B
respectively de¬ned over the same object T .
The set of composable pairs of arrows in a category (see Section 1.1) are a
special case in Set of this, with A = B being the set of arrows and f = d0 , g = d1 .
Thus we must consider commutative diagrams like
yE
T B

g
x (2)
c c
EC
A
f

In this situation, (T, x, y) is called a commutative cone over D based on
T , and the set of commutative cones over D based on T is denoted Cone(T, D) .
A commutative cone based on T over D may usefully be regarded as an element
of D de¬ned on T . In Section 1.7, we will see that a commutative cone is actually
an arrow in a certain category, so that this idea ¬ts with our usage of the word
“element”.
Our strategy will be to turn Cone(’, D) into a functor; then we will say that
an object represents (in an informal sense) elements of D, in other words pairs
(x, y) for which f (x) = g(y), if that object represents (in the precise technical
sense) the functor Cone(’, D).
We make will make Cone(’, D) into a contravariant functor to Set: If h: W
’ T is an arrow of C and (T, x, y) is a commutative cone over (1), then


Cone(h, D)(T, x, y) = (W, x —¦ h, y —¦ h)
which it is easy to see is a commutative cone over D based on W .
An element (P, p1 , p2 ) of D which is a universal element for Cone(’, D) (so
that Cone(’, D) is representable) is called the pullback or the ¬ber product
of the diagram D. The object P is often called the pullback, with p1 and p2
understood. As the reader can verify, this says that (P, p1 , p2 ) is a pullback if
p2 E
P B

p1 g (3)
c c
EC
A
f
1.6 Pullbacks 31
commutes and for any element of D based on T , there is a unique element of P
based on T which makes
T
r
ed rr
ry
ed
rr
ed
prE
ed‚ j
r
2
xe P B (4)
e
p1 g
e
e
ec
… c
EC
A
f
commute. Thus there is a bijection between the elements of the diagram D
de¬ned on T and the elements of the ¬ber product P de¬ned on T . When a
diagram like 4 has this property it is called a pullback diagram.
The Cone functor exists for any category, but a particular diagram of the
form 1 need not have a pullback.
Proposition 1. If Diagram 3 is a pullback diagram, then the cone in Diagram 2
is also a pullback of Diagram 1 if and only if the unique arrow from T to P making
everything in Diagram 4 commute is an isomorphism.
Proof. (This theorem actually follows from Exercise 4 of Section 1.5, but we
believe a direct proof is instructive.) Assume that (2) and (3) are both pullback
diagrams. Let u: T ’ P be the unique arrow given because 3 is a pullback

diagram, and let v: P ’ T be the unique arrow given because 2 is a pullback

diagram. Then both for g = u —¦ v: P ’ P and g = idP it is true that p1 —¦ g = p1

and p2 —¦ g = p2 . Therefore by the uniqueness part of the de¬nition of universal
element, u —¦ v = idP . Similarly, v —¦ u = idT , so that u is an isomorphism between
T and P making everything commute. The converse is easy.
The preceding argument is typical of many arguments making use of the
uniqueness part of the de¬nition of universal element. We will usually leave
arguments like this to the reader.
A consequence of Proposition 1 is that a pullback of a diagram in a category
is not determined uniquely but only up to a “unique isomorphism which makes
everything commute”. This is an instance of a general fact about constructions
de¬ned as universal elements which is made precise in Proposition 1 of Section 1.7.
32 1 Categories
Notation for pullbacks

We have de¬ned the pullback P of Diagram 1 so that it objecti¬es the set
{(x, y) | f (x) = g(y)}. This ¬ts nicely with the situation in Set, where one
pullback of (1) is the set {(x, y) | f (x) = g(y)} together with the projection
maps to A and B, and any other pullback is in one to one correspondence with
this one by a bijection which commutes with the projections. This suggest the
introduction of a setlike notation for pullbacks: We let [(x, y) | f (x) = g(y)]
denote a pullback of (1). In this notation, f (x) denotes f —¦ x and g(y) denotes g —¦ y
as in Section 1.4, and (x, y) denotes the unique element of P de¬ned on T which
exists by de¬nition of pullback. It follows that p1 (x, y) = x and p2 (x, y) = y,
where we write p1 (x, y) (not p1 ((x, y))) for p1 —¦ (x, y).
The idea is that square brackets around a set de¬nition denotes an object of
the category which represents the set of arrows listed in curly brackets”“repre-
sents” in the technical sense, so that the set in curly brackets has to be turned
into the object map of a set-valued functor. The square bracket notation is
ambiguous. Proposition 1 spells out the ambiguity precisely.
We could have de¬ned a commutative cone over (1) in terms of three arrows,
namely a cone (T, x, y, z) based on T would have x: T ’ A, y: T ’ B and z: T
’ ’
’ C such that f —¦ x = g —¦ y = z. Of course, z is redundant and in consequence

the Cone functor de¬ned this way would be naturally isomorphic to the Cone
functor de¬ned above, and so would have the same universal elements. (The
component of the natural isomorphism at T takes (T, x, y) to (T, x, y, f —¦ x)).
Thus the pullback of (1) also represents the set {(x, y, z) | f (x) = g(y) = z},
and so could be denoted [(x, y, z) | f (x) = g(y) = z]. Although this observation
is inconsequential here, it will become more signi¬cant when we discuss more
general constructions (limits) de¬ned by cones.
There is another way to construct a pullback in Set when the map g is monic.
In general, when g is monic, {(x, y) | f (x) = g(y)} ∼ {x | f (x) ∈ g(B)}, which
=
’1
in Set is often denoted f (B). In general, a pullback along a subobject can be
interpreted as an inverse image which as we will see is again a subobject.
The pullback Diagram 3 is often regarded as a sort of generalized inverse image
construction even when g is not monic. In this case, it is called the “pullback of
g along f ”. Thus when P is regarded as the ¬ber product, the notion of pullback
is symmetrical in A and B, but when it is regarded as the generalized inverse
image of B then the diagram is thought of as asymmetrical.
A common notation for the pullback of (1) re¬‚ecting the perception of a
pullback as ¬ber product is “A —C B”.
1.6 Pullbacks 33

<<

. 7
( 60 .)



>>