. 4
( 60 .)


c c
(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

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

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
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
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
’ ’

f f
c c
commute. It is easy to verify that coordinatewise composition makes (F, G) a
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

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


. 4
( 60 .)