ńņš. 7 |

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 |