EB

B

k

(b) The twisted arrow category of C is de¬ned the same way as the arrow

category except that the direction of k is reversed.

3. (a) Show that h: f ’ g is an isomorphism in the category of objects of C

’

over A if and only if h is an isomorphism of C .

(b) Give an example of objects A, B and C in a category C and arrows f : B

’ A and g: C ’ A such that B and C are isomorphic in C but f and g are

’ ’

not isomorphic in C /A.

4. Describe the isomorphisms, initial objects, and terminal objects (if they exist)

in each of the categories in Exercise 2.

10 1 Categories

5. Describe the initial and terminal objects, if they exist, in a poset regarded as

a category.

6. Show that any two terminal objects in a category are isomorphic by a unique

isomorphism.

7. (a) Prove that for any category C and any arrows f and g of C such that

the target of g is isomorphic to the source of f , there is an arrow f which (i) is

isomorphic to f in Ar(C ) and (ii) has source the same as the target of g. (Ar(C )

is de¬ned in Exercise 2 above.)

(b) Use the fact given in (a) to describe a suitable de¬nition of domain, codo-

main and composition for a category with one object chosen for each isomorphism

class of objects of C and one arrow from each isomorphism class of objects of

Ar(C ). Such a category is called a skeleton of C .

8. A category is connected if it is possible to go from any object to any other

object of the category along a path of “composable” forward or backward arrows.

Make this de¬nition precise and prove that every category is a union of disjoint

connected subcategories in a unique way.

9. A preorder is a set with a re¬‚exive, transitive relation de¬ned on it. Explain

how to regard a preorder as a category with at most one arrow from any object

A to any object B.

10. (a) Describe the opposite of a group regarded as a category. Show that it is

isomorphic to, but not necessarily the same as, the original group.

(b) Do the same for a monoid, but show that the opposite need not be

isomorphic to the original monoid.

(c) Do the same as (b) for posets.

11. An arrow congruence on a category C is an equivalence relation E on the

arrows for which

(i) f Ef implies that f and f have the same domain and codomain.

(ii) If f Ef and gEg and f —¦ g is de¬ned, then (f —¦ g)E(f g ).

—¦

There are more general congruences in which objects are identi¬ed. These are

considerably more complicated since new composites are formed when the target

of one arrow gets identi¬ed with the source of another.

(a) Show that any relation R on the arrows of C generates a unique congru-

ence on C .

1.2 Functors 11

(b) Given a congruence E on C , de¬ne the quotient category C /E in the

obvious way (same objects as C ) and show that it is a category. This notation

con¬‚icts with the slice notation, but context should make it clear. In any case,

quotient categories are not formed very often.

(Thus any set of diagrams in C generate a congruence E on C with the

property that C /E is the largest quotient in which the diagrams commute.)

12. Show that in a category with an initial object 0 and a terminal object 1,

0 ∼ 1 if and only if there is a map 1 ’ 0.

’

=

1.2 Functors

Like every other kind of mathematical structured object, categories come equipped

with a notion of morphism. It is natural to de¬ne a morphism of categories to

be a map which takes objects to objects, arrows to arrows, and preserves source,

target, identities and composition.

If C and D are categories, a functor F : C ’ D is a map for which

’

1. if f : A ’ B is an arrow of C , then F f : F A ’ F B is an arrow of D;

’ ’

2. F (idA ) = idF A ; and

3. if g: B ’ C, then F (g —¦ f ) = F g —¦ F f .

’

If F : C ’ D is a functor, then F op : C op ’ D op is the functor which does

’ ’

the same thing as F to objects and arrows.

A functor F : C op ’ D is called a contravariant functor from C to D.

’

In this case, F goes from C to D op . For emphasis, a functor from C to D is

op

occasionally called a covariant functor.

F : C ’ D is faithful if it is injective when restricted to each homset, and it

’

is full if it is surjective on each homset, i.e., if for every pair of objects A and B,

every arrow in Hom(F A, F B) is F of some arrow in Hom(A, B). Some sources

use the phrase “fully faithful” to describe a functor which is full and faithful.

F preserves a property P that an arrow may have if F (f ) has property P

whenever f has. It re¬‚ects property P if f has the property whenever F (f ) has.

For example, any functor must preserve isomorphisms (Exercise 1), but a functor

need not re¬‚ect them.

Here are some examples of functors:

1. For any category C , there is an identity functor idC : C ’ C .

’

12 1 Categories

2. The categories Grp and T are typical of many categories considered in

op

mathematics in that their objects are sets with some sort of structure on

them and their arrows are functions which preserve that structure. For any

such category C , there is an underlying set functor U : C ’ Set which

’

assigns to each object its set of elements and to each arrow the function

associated to it. Such a functor is also called a forgetful functor, the

idea being that it forgets the structure on the set. Such functors are always

faithful and rarely full.

3. Many other mathematical constructions, such as the double dual functor

on vector spaces, the commutator subgroup of a group or the fundamental

group of a path connected space, are the object maps of functors (in the

latter case the domain is the category of pointed topological spaces and

base-point-preserving maps). There are, on the other hand, some canonical

constructions which do not extend to maps. Examples include the cen-

ter of a group or ring, and groups of automorphisms quite generally. See

Exercise 8 and Exercise 9.

4. For any set A, let F A denote the free group generated by A. The de¬n-

ing property of free groups allows you to conclude that if f : A ’ B is

’

any function, there is a unique homomorphism F f : F A ’ F B with the

’

property that F f —¦ i = j —¦ f , where i: A ’ F A and j: B ’ F B are the

’ ’

inclusions. It is an easy exercise to see that this makes F a functor from

Set to Grp. Analogous functors can be de¬ned for the category of monoids,

the category of Abelian groups, and the category of R-modules for any ring

R.

5. For a category C , HomC = Hom is a functor in each variable separately,

as follows: For ¬xed object A, Hom(A, f ): Hom(A, B) ’ Hom(A, C) is

’

de¬ned for each arrow f : B ’ C by requiring that Hom(A, f )(g) = f —¦ g

’

for g ∈ Hom(A, B); this makes Hom(A, ’): C ’ Set a functor. Similarly,

’

for a ¬xed object B, Hom(’, B) is a functor from C op to Set; Hom(h, B)

is composition with h on the right instead of on the left. Hom(A, ’) and

Hom(’, B) are the covariant and contravariant hom functors, respec-

tively. Hom(’, ’) is also a Set-valued functor, with domain C op — C . A

familiar example of a contravariant hom functor is the functor which takes

a vector space to the underlying set of its dual.

6. The powerset (set of subsets) of a set is the object map of an important

contravariant functor P from Set to Set which plays a central role in this

book. The map from PB to PA induced by a function f : A ’ B is the

’

1.2 Functors 13

inverse image map; precisely, if B0 ∈ PB, i.e. B0 ⊆ B, then

Pf (B0 ) = {x ∈ A | f (x) ∈ B0 }

The object function P can also be made into a covariant functor, in at least

two di¬erent ways (Exercise 6).

7. If G and H are groups considered as categories with a single object, then a

functor from G to H is exactly a group homomorphism.

8. If P and Q are posets, a functor from P to Q is exactly a nondecreasing

map. A contravariant functor is a nonincreasing map.

Isomorphism and equivalence of categories

The composite of functors is a functor, so the collection of categories and

functors is itself a category, denoted Cat. If C and D are categories and F : C

’ D is a functor which has an inverse G: D ’ C , so that it is an isomorphism

’ ’

in the category of categories, then naturally C and D are said to be isomorphic.

However, the notion of isomorphism does not capture the most useful sense

in which two categories can be said to be essentially the same; that is the notion

of equivalence. A functor F : C ’ D is said to be an equivalence if it is full

’

and faithful and has the property that for any object B of D there is an object

A of C for which F (A) is isomorphic to B. The de¬nition appears asymmetrical

but in fact given the axiom of choice if there is an equivalence from C to D then

there is an equivalence from D to C (Exercise 11).

The notion of equivalence captures the perception that, for example, for most

purposes you are not changing group theory if you want to work in a category of

groups which contains only a countable number (or ¬nite, or whatever) of copies

of each isomorphism type of groups and all the homomorphisms between them.

Statements in Section 1.1 like, “A group may be regarded as a category with

one object in which all arrows are isomorphisms” can be made precise using the

notion of equivalence: The category of groups and homomorphisms is equivalent

to the category of categories with exactly one object in which each arrow is an

isomorphism, and all functors between them. Any isomorphism between these

categories would seem to require an axiom of choice for proper classes.

Comma categories

Let A , C and D be categories and F : C ’ A , G: D ’ A be functors. From

’ ’

these ingredients we construct the comma category (F, G) which is a general-

ization of the slice A /A of a category over an object discussed in Section 1.1.

14 1 Categories

The objects of (F, G) are triples (C, f, D) with f : F C ’ GD an arrow of A and

’

C, D objects of C and D respectively. An arrow (h, k): (C, f, D) ’ (C , f , D )

’

consists of h: C ’ C and k: D ’ D making

’ ’

Fh

E

FC FC

f f

c c

E GD

GD

Gk

commute. It is easy to verify that coordinatewise composition makes (F, G) a

category.

When A is an object of A , we can consider it as a functor A: 1 ’ A . Then

’

the comma category (IdA , A) is just the slice A /A de¬ned in Section 1.1. The

category of arrows under an object is similarly a comma category.

Each comma category (F, G) is equipped with two projections p1 : (F, G) ’ ’

C projecting objects and arrows onto their ¬rst coordinates, and p2 : (F, G) ’ D

’

projecting objects onto their third coordinates and arrows onto their second.

Exercises 1.2

1. Show that functors preserve isomorphisms, but do not necessarily re¬‚ect them.

2. Use the concept of arrow category to describe a functor which takes a group

homomorphism to its kernel.

3. Show that the following de¬ne functors:

(a) the projection map from a product C — D of categories to one of them;

(b) for C a category and an object A of C , the constant map from a category

B to C which takes every object to A and every arrow to idA ;

(c) the forgetful functor from the category C /A of objects over A to C which

takes an object B ’ A to B and an arrow h: B ’ C over A to itself.

’ ’

4. Show that the functor P of Example 6 is faithful but not full and re¬‚ects

isomorphisms.

5. Give examples showing that functors need not preserve or re¬‚ect initial or

terminal objects.

1.2 Functors 15

6. Show that the map which takes a set to its powerset is the object map of at

least two covariant functors from Set to Set: If f : A ’ B, one functor takes a

’

subset A0 of A to its image f! (A0 ) = f (A0 ), and the other takes A0 to the set

f— (A0 ) = {y ∈ B | if f (x) = y then x ∈ A0 } = {y ∈ B | f ’1 (y) ⊆ A0 }

Show that f ’1 (B) ⊆ A if and only if B ⊆ f— (A) and that A ⊆ f ’1 (B) if and only

if f! (A) ⊆ B.

7. Show that the de¬nition given in Example 4 makes the free group construction

F a functor.

8. Show that there is no functor from Grp to Grp which takes each group to its

center. (Hint: Consider the group G consisting of all pairs (a, b) where a is any

integer and b is 0 or 1, with multiplication

(a, b)(c, d) = (a + (’1)b c, b + d)

the addition in the second coordinate being mod 2.

9. Show that there is no functor from Grp to Grp which takes each group to its