Category Theory Lecture Notes MAT434
Category Theory Lecture Notes MAT434
Lecture Notes
Preface
This series of lecture notes has been prepared for aiding students who took the BRAC University
course Category Theory (MAT434) in Summer 2023 semester. These notes were typeset under
the supervision of mathematician Dr. Syed Hasibul Hassan Chowdhury. The main goal of this
typeset is to have an organized digital version of the notes, which is easier to share and handle. If you
see any mistakes or typos, please send me an email at atonuroychowdhury@[Link]
References:
• Category Theory, by Steve Awodey.
ii
Contents
Preface ii
1 Categories 5
1.1 Definition of a Category . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Examples of Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Functor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Construction on Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Free Categories 15
2.1 Free Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Free Category . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Abstract Characterizations 21
3.1 Epis and Monos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Sections and Retractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Initial and Terminal Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Generalized Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Hom-sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.7 Associativity of Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.8 Product and Terminal Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 Duality 54
4.1 Duality Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 Coproducts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Equalizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.4 Coequalizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Product and Coproduct of an Arbitrary Family of Objects . . . . . . . . . . . . . . . . . 72
8 Exponentials 132
8.1 Exponential in a Category . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.2 Cartesian Closed Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
9 Naturality 139
9.1 The Category of Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3
Contents 4
4
1 Categories
§1.1 Definition of a Category
Category theory arises from the idea of a system of “functions” among some objects.
f
A B
g
g◦f
C
A category consists of objects A, B, C, . . . and arrows f : A → B, g : B → C, . . . that are closed
under composition and satisfy certain conditions typical of composition of functions. Before formally
defining what a category is, let us begin our discussion with the setting where the objects are sets and
arrows are functions between sets.
Let f be a function from a set A to another set B. This is mathematically expressed as f : A → B.
Explicitly, it refers to the fact that f is defined for all of A, and all the values of f are contained in B.
In other words, range (f ) ⊆ B.
Now suppose we have another function g : B → C. Then there is a unique function g ◦ f : A → C,
given by
(g ◦ f ) (a) = g (f (a)) , for a ∈ A. (1.1)
This unique function is called the composite of g and f , or g after f .
f
A B
g
g◦f
C
Now, this operation ◦ of composition of functions is associative. In other words, the two arrows
from A to D in the following diagram are the same:
(h ◦ g) ◦ f
h◦g
f g h
A B C D
g◦f
h ◦ (g ◦ f )
(h ◦ g) ◦ f = h ◦ (g ◦ f ) , (1.2)
from A to D as demanded by the associativity law. Using the definition of composition of functions,
one verifies that this is indeed the case:
((h ◦ g) ◦ f ) (a) = (h ◦ g) (f (a)) = h (g (f (a))) ,
(h ◦ (g ◦ f )) (a) = h ((g ◦ f ) (a)) = h (g (f (a))) .
Therefore, (h ◦ g) ◦ f = h ◦ (g ◦ f ).
5
1 Categories 6
Finally, note that for every set A, there is an identity function 1A : A → A given by
1A (a) = a. (1.3)
These identity functions act as units for composition, i.e. given f : A → B, we have
We have the following abstract version of sets and functions between sets called a category.
• Arrows: f, g, h, . . .. Given two objects A and B, the set of arrows from A to B is denoted
by HomC (A, B).
• For each arrow f , there are given objects dom (f ) , cod (f ) called the domain and codomain
of f . We write f : A → B to indicate that A = dom (f ) and B = cod (f ).
• Given arrows f : A → B and g : B → C, i.e. with cod (f ) = dom (g), there is a unique
arrow g ◦ f : A → C, i.e. g ◦ f ∈ HomC (A, C) called the composite of f and g. This fact
can be rephrased as the following: given A, B, C ∈ Ob (C), there is a function
• For each A ∈ Ob (C), there exists an unique arrow 1A ∈ HomC (A, A).
• Associativity: For any f ∈ HomC (A, B), g ∈ HomC (B, C), h ∈ HomC (C, D) with
A, B, C, D ∈ Ob (C),
(h ◦ g) ◦ f = h ◦ (g ◦ f ) , (1.6)
f ◦ 1A = 1B ◦f = f. (1.7)
6
1 Categories 7
Definition 1.2. A partially ordered set or poset is a set A equipped with a binary relation (a
subset of A × A) a ≤A b (in other words, (a, b) ∈ R ⊂ A × A) such that the following conditions
hold for all a, b, c ∈ A:
(i) Reflexivity: a ≤A a.
Remark 1.2. The antisymmetry condition tells us that if both a ≤A b and b ≤A a hold, then a
and b cannot be distinct. Contrapositively, for distinct a and b in A, not both a ≤A b and b ≤A a
hold true. Also, note that if (A, ≤A ) is a partially ordered set, there can be elements a, b ∈ A
such that neither (a, b) nor (b, a) is in R. If it happens that given any a, b ∈ A, either (a, b) or
(b, a) is in R, i.e. either a ≤A b or b ≤A a, then we call A a totally ordered set.
Example 1.1. (R, ≤), the set of real numbers with the usual ordering ≤ is a totally ordered set.
Now we define an arrow from a poset (A, ≤A ) to another poset (B, ≤B ) to be a function m : A → B
that is monotone, in the sense that for all a, a0 ∈ A,
whenever a ≤A a0 , one has m (a) ≤B m a0 .
We need to verify that under this definition of arrows, we have a category. First of all, we must have
1A : A → A, defined by 1A (a) = a for each a ∈ A, to be monotone. Indeed, if a ≤ a0 in A, then we
automatically have 1A (a) ≤ 1A (a0 ). Therefore, 1A is monotone.
7
1 Categories 8
Given monotone functions f : A → B bewteen posets (A, ≤A ) and (B, ≤B ), and g : B → C bewteen
posets (B, ≤B ) and (C, ≤C ), we need to verify that the composition g ◦ f : A → C is also monotone.
Indeed, given a ≤A a0 , since f is monotone, we have
f (a) ≤B f a0 . (1.8)
Since g is monotone, this gives us
g (f (a)) ≤C g f a0 . (1.9)
In other words, (g ◦ f ) (a) ≤C (g ◦ f ) (a0 )
given a ≤A a0 .
Therefore, g ◦ f : A → C is monotone.
The category thus formed is called the category of posets and monotone functions, and is denoted
by Pos.
Finite Categories
A finite category consists of finitely many objects and finitely many arrows between them.
• The category 1 looks as follows:
? ∗
It has two objects ? and ∗, their identity arrows, and exactly one arrow ? → ∗.
• The category 3 looks as follows:
? ∗
It has three objects ?, ∗, •, their respective identity arrows, and the other arrows are ? → ∗,
∗ → •, and ? → • (which is the composition of the previous two arrows).
• The category 0 looks as follows:
§1.3 Functor
Definition 1.3 (Functor). A functor F : C → D between categories C and D is an assignment of
Ob (C) to Ob (D) and a mapping of arrows in C to arrows in D, i.e. for any A, B ∈ Ob (C), a
mapping
HomC (A, B) → HomD (F (A) , F (B)) ,
where F (A) , F (B) ∈ Ob (D) are the assigned objects of D under F . In other words, for given
A, B ∈ Ob (C) and an arrow f : A → B, one has F (A) , F (B) ∈ Ob (D) and an arrow F (f ) :
F (A) → F (B) such that the following hold:
(b) F (g ◦ f ) = F (g) ◦ F (f ).
8
1 Categories 9
In other words, F preserves domains and codomains, identity arrows and composition.
f
C A B
g
g◦f
F C
F (f )
D F (A) F (B)
F (g)
F (g◦f )=F (g)◦F (f )
F (C)
Now, one can see that functors compose in the expected way and that every category C has a distin-
guished functor called the identity functor 1C : C → C. Thus we have a category, namely Cat, the
category of all categories and functors between them.
Preorder
A preorder is a set P equipped with a binary relation ≤ that is both reflexive and transitive: a ≤ a;
and if a ≤ b and b ≤ c, then a ≤ c for any a, b, c ∈ P . Any preorder (P, ≤) can be regarded as a
category by taking the objects of the category to be the elements of P and taking a unique arrow
Remark 1.3. Reflexivity and transitivity property ensures that the preorder (P, ≤) is indeed a
category. Note that the above condition implies that there is at most one arrow from an object of
(P, ≤) to another. In the other direction, any category with at most one arrow from an object to
another determines a preorder simply by defininig a binary relation ≤ on the objects by (1.10).
Remark 1.4 (On the similarities between a poset and a preorder). A poset (P, ≤) is evidently
a preorder with the additional condition of antisymmetry. Hence, a poset is also a category.
Examples of poset include the power set P (X) of a given set X under the usual subset relation:
U ⊆ V between the subsets U, V of X.
There can be preorders that are not posets. For instance, (Z, |) is a preorder on the set of
integers, where “|” is the usual divides binary relation: given a, b ∈ Z, we have a | b (read a
divides b) if and only if b = ca for some c ∈ Z. It is clearly reflexive and transitive. Note that
a | b and b | a imply a = ±b which is not the same as a = b. Hence, “|” is not antisymmetric.
Therefore, (Z, |) is a preorder that is not a poset.
§1.4 Monoid
Definition 1.4 (Monoid). A monoid is a set M equipped with a binary operation · : M ×M → M
and a distinguished “unit” element u ∈ M such that for each x, y, z ∈ M ,
x · (y · z) = (x · y) · z and u · x = x · u = x. (1.11)
Equivalently, a monoid is a category with just one object. The arrows of the category are the elements
of the monoid. In particular, the identity arrow on the object is the unit element u. Composition of
arrows is the binary operation x · y of the monoid.
9
1 Categories 10
For example, N (we are adopting the convention that 0 ∈ N), Q, R with addition and 0 as the unit
element. Also, N, Q, R with multiplication and 1 as unit are monoids. For any set X, the set of
functions from X to itself, written as
HomSets (X, X) ,
is a monoid under the operation of composition. Here Sets is the category of sets and functions
between sets. More generally, for any object C ∈ Ob (C) in a category C, the set of arrows from C to
itself, written as
HomC (C, C) ,
is a monoid under the composition of arrows in C.
Since monoids are structured sets (sets equipped with a binary operation fulfilling associativity, uni-
tality etc.), there is a category Mon whose objects are monoids and arrows are functions that preserve
the monoid structure, namely monoid homomorphisms. In detail, a monoid homomorphism from
a monoid (M, ·M ) to a monoid (N, ·N ) is a function f : M → N such that for all m, n ∈ M ,
§1.4.i Isomorphisms
Definition 1.5. In any category C, an arrow f : A → B is called an isomorphism if there is an
arrow g : B → A such that
g ◦ f = 1A and f ◦ g = 1B . (1.13)
ge ◦ f = 1A and f ◦ ge = 1B . (1.14)
Then we have
g = g ◦ 1B = g ◦ (f ◦ ge) = (g ◦ f ) ◦ ge = 1A ◦ge = ge. (1.15)
Hence, if an arrow g : B → A exists satisfying (1.13), then it is unique. Such unique arrow g : B → A
is called the inverse of f : A → B, and we write g = f −1 . When such an arrow f : A → B exists, we
say that A is isomorphic to B, written A =∼ B.
Definition 1.6 (Group). A group G is a monoid with an inverse g −1 for every element g ∈ G.
Thus G is a category with one object in which every arrow is an isomorphism.
The natural numbers N do not form a group either under addition or multiplication. But the integers
Z form a group under addition. So do the positive rationals Q+ under multiplication. For any set X,
we have the group Aut (X) of all the automorphisms of X, i.e. isomorphisms f : X → X. A group
of permutations is a subgroup G ⊆ Aut (X) for some X. Thus the set G must satisfy the following:
2. If g, g 0 ∈ G, then g ◦ g 0 ∈ G.
3. If g ∈ G, g −1 ∈ G.
10
1 Categories 11
Sketch of proof. First, define the Cayley representation G of G to be the following group of permuta-
tions on a set: the set is G itself, and for each g ∈ G, one has the permutation g : G → G defined
as
g (h) = g · h for each h ∈ G. (1.16)
Indeed, g has an inverse g −1 = g −1 :
g −1 (h) = g −1 h. (1.17)
One, thus, verifies that g : G → G is indeed an isomorphism, and hence a permutation on G.
Now define homomorphisms i : G → G by i (g) = g, and j : G → G by j (g) = g (u) = g, with u
being the identity element of the group G.
Observe that i ◦ j = 1G and j ◦ i = 1G . Indeed, for g ∈ G and g ∈ G,
(j ◦ i) (g) = j (i (g)) = j (g) = g,
(i ◦ j) (g) = i (j (g)) = i (g) = g,
establishing that i : G → G is an isomorphism. ■
Remark 1.5. There are two different types of isomorphisms involved in this proof. For each
g ∈ G, one defines an isomorphism g : G → G. This is an isomorphism in the category Sets.
Later, we defined an isomorphism i : G → G, which is an isomorphism in the categorty Groups
of groups and group homomorphisms.
Remark 1.6. The group G is the group of permutations (automorphisms) on the group G which
is a subgroup of the automorphism group on G itself. This subgroup has the same unit element
of that of the automorphism group on G, i.e. 1G , the identity function on the group G. Note
that this is also the unit of the group G which is not the same as 1G . This identity function 1G
on G was used to establish the required isomorphism in Cayleys theorem.
Cayley’s theorem can be generalized to prove that any category not “too big” (which has the collection
of objects to be a set) is isomorphic to a category in which the objects are sets and the arrows are
functions between those sets. In other words, any not “too big” category is isomorphic to a subcategory
of Sets.
Sketch of proof. Define the Cayley representation C of C to be the following concrete category (i.e. a
category where objects are sets and arrows are functions between them):
• Objects: objects are sets of the form
C = {f : X → C} = {f ∈ HomC (X, C) | X ∈ Ob (C)} . (1.18)
In other words, the object C is the set of functions whose codomains are C.
• Arrows: arrows are functions
g:C→D (1.19)
for g : C → D in C, defined for any f : X → C in C by g (f ) = g ◦ f .
X
g(f )=g◦f
f
C g D
11
1 Categories 12
Then we define a functor F : C → C that takes the object C ∈ Ob (C) to the object C ∈ Ob C , and
takes the arrow g : C → D in C to the arrow g : C → D in C. In other words,
This is a functor since F (1C ) = 1C and F (g ◦ h) = F (g) ◦ F (h) for composable arrows g, h in C.
functor G : C → C that takes the object C to the codomains
We then define another of the functions
that are in C, i.e. G C = C, and takes the arrow g : C → D to the arrow g 1G (C ) = g (1C ) =
g ◦ 1C = g : C → D in C. In other words,
G C = C and G (g) = g. (1.21)
This is a functor since G 1C = 1C and G g ◦ h = G (g) ◦ G h for composable arrows g, h in C.
Then one can verify that
G ◦ F = 1C and F ◦ G = 1C . (1.22)
Therefore, C and C are isomorphic. ■
f f0 g g0
1C C C0 C 00 D D0 D00
f 0 ◦f g 0 ◦g
Then in C × D, we have
(f,g) (f 0 ,g 0 )
1(C,D) =(1C ,1D ) (C, D) (C 0 , D0 ) (C 00 , D00 )
Similarly,
π2 (C, D) = D, π2 (f, g) = g. (1.25)
12
1 Categories 13
[Link] opposite category C op has objects that are in a one-to-one correspondence with the objects of C.
Let C ∗ ∈ Ob (C op ) be the object in C op that corresponds to C ∈ Ob (C). Then an arrow f : C → D
in C corresponds to an arrow f ∗ : D∗ → C ∗ . With this notation, one can define composition and
units in C op in terms of the corresponding operations in C, namely
1C ∗ = (1C )∗ . (1.26)
For f : C → D, g : D → E in C, we have f ∗ : D∗ → C ∗ and g ∗ : E ∗ → D∗ in C op . Then their
composition is defined as
f ∗ ◦ g ∗ = (g ◦ f )∗ . (1.27)
1C ∗ =(1C )∗
f g Duality f∗ g∗
1C C D E C∗ D∗ E∗
g◦f f ∗ ◦g ∗ =(g◦f )∗
f f0
C
Now suppose f, g, h ∈ Ob C/C and a ∈ HomC/C (f, g), b ∈ HomC/C (g, h). Then there are objects
X, X 0 , X 00 ∈ Ob (C) such that the two triangles in the following diagram commute:
b◦a
X a X0 b
X 00
g
f h
C
In other words, g ◦ a = f and h ◦ b = g, so that one obtains
f = g ◦ a = (h ◦ b) ◦ a = h ◦ (b ◦ a) . (1.28)
Therefore, we have the following commutative diagram:
X b◦a
X 00
f h
C
Hence, b ◦ a ∈ HomC/C (f, h), using the definition of arrows in C/C. For a given f ∈ Ob (C/C), 1f
is precisely the identity arrow on dom (f ) in the category C, which is evident from the following
commutative diagram:
1dom(f )
dom (f ) dom (f )
f f
C
If g : C → D is any arrow in C, then there is a functor called the composition functor:
g∗ : C/C → C/D,
defined on Ob (C/C) as
g∗ (f ) = g ◦ f. (1.29)
13
1 Categories 14
X
g◦f
f
C g D
Commutativity of the above diagram dictates that g ◦ f ∈ Ob (C/D). Now suppose f, f 0 ∈ Ob (C/C),
and consider a ∈ HomC/C (f, f 0 ) so that the following diagram commutes:
X a
X0
f0 g◦f 0
f
g◦f
C g D
0
g ◦ f = g ◦ f0 ◦ a = g ◦ f ◦ a, (1.30)
so the diagram indeed commutes. So we have the following commutative diagram:
X a
X0
g◦f g◦f 0
D
The commutativity of this diagram dictates that g∗ (a) = a. In fact, the whole construction above
is a functor C/(−) : C → Cat.
C Cat
C/(−)
g g∗
C D C/C C/D
[Link] coslice category C/C of a category C under an object C ∈ Ob (C) has as objects all arrows f
of C such that dom (f ) = C. An arrow in HomC/C (f, f 0 ) is an arrow h ∈ HomC (X, X 0 ) (where
X = cod (X) and X 0 = cod (f 0 )) such that the diagram below commutes:
C
f f0
X h
X0
In other words,
h ◦ f = f 0. (1.31)
Question. How can the coslice category be defined in terms of the slice category and the opposite
construction?
Example 1.2. The category Sets∗ of pointed sets consists of sets A with a distinguished element
a ∈ A, and arrows f : (A, a) → (B, b) are functions f : A → B that preserves the distinguished
elements f (a) = b. Now, Sets∗ is isomorphic to the coslice categroy 1/Sets of sets under any
singleton 1 = {?}.
Sets∗ ∼
= 1/Sets. (1.32)
Indeed, functions a : 1 → A are uniquely determined by a (?) = a ∈ A, and are objects in 1/Sets.
Now we define a functor F : Sets∗ → 1/Sets by
F (A, a) = a and F (f ) = f. (1.33)
Then we define G : 1/Sets → Sets∗ by
G (a) = (A, a (∗)) and G (f ) = f. (1.34)
One can easily verify that G and F are functors, and
G ◦ F = 1Sets∗ and F ◦ G = 11/Sets . (1.35)
Therefore, 1/Sets and Sets∗ are isomorphic categories.
14
2 Free Categories
§2.1 Free Monoid
Start with an “alphabet” A of “letters” a, b, c, . . ., i.e. a set
A = {a, b, c, . . . } . (2.1)
We write “-” for empty word. The Kleene closure of A is defined to be the set
Define a binary operation ∗ on A∗ by w ∗ w0 = ww0 for words w, w0 ∈ A∗ . Thus, the binary operation
∗ on A∗ is just concatenation. The operation can easily be seen to be associative, and the empty word
“-” is a unit. Therefore, A∗ is a monoid– called the free monoid on the set A.
The number of letters in a word is called its length. The elements a ∈ A can be regarded as
words of length 1. One has a function i : A → A∗ defined by i (a) = a, and called the “ insertion
of generators”. The elements of A generate the free monoid, in the sense that every w ∈ A∗ can be
written as a ∗ products of elements of A, i.e.,
w = a1 ∗ a2 ∗ · · · ∗ an ,
for some a1 , . . . , an ∈ A.
A monoid M is freely generated by a subset A of M , if the following conditions hold:
m = a1 ·M a2 ·M · · · ·M an , where ai ∈ A.
a1 ·M · · · ·M an = a01 ·M · · · ·M a0k ,
The second condition of the definition of a free monoid is made more precise in the following way:
First, every monoid N has an underlying set |N |, and every monoid homomorphism f : N → M
has an underlying function |f | : |N | → |M |. This way, one has a functor Mon → Sets. This functor
is called the forgetful functor.
The free monoid M (A) on a set A is by definition “the” monoid with the following universal mapping
property or UMP:
15
2 Free Categories 16
f
in Mon : M (A) N
|f |
in Sets : |M (A)| |N |
i
f
A
i is called the insertion of generators.
Proposition 2.1
A∗ has the UMP of the free monoid on A.
Proof. Given any monoid N and any function f : A → |N |, define f : A∗ → N by f (-) = uN , and
i
f
A
This proves the existence of f : A∗ → N with the required universal mapping property. Let us
now prove the uniqueness. Suppose there is another monoid homomorphism g : A∗ → N so that
g (a) = f (a), which in turn will give us the commutative diagram exhibiting UMP. Therefore, for all
a1 , . . . , an ∈ A,
g (a1 a2 · · · an ) = g (a1 ∗ a2 ∗ · · · ∗ an )
= g (a1 ) ·N · · · ·N g (an )
= f (a1 ) ·N · · · ·N f (an )
= f (a1 a2 · · · an ) .
Proposition 2.2
Given monoids M and N with functions i : A → |M | and j : A → |N |, each with the UMP of the
16
2 Free Categories 17
∼
=
free monoid on A, there is a unique monoid isomorphism h : M −
→ N such that
|j |
in Sets : |M | |N |
i
j
A
From i : A → |M | and the UMP of N , one has i : N → M with i ◦ j = i.
i
in Mon : N M
|i|
in Sets : |N | |M |
j
i
A
Combining these two, we get the following commutative diagram:
i◦j
in Mon : M N M
j i
|j | |i|
in Sets : |M | |N | |M |
j
i i
A
From i : A → |M | and the UMP of M , we have the existence of a unique homomorphism f : M → M
such that |f | ◦ i = i. From the above commutative diagram, we get that f = i ◦ j satisfies |f | ◦ i = i.
Furthermore, f = 1M : M → M also satisfies |f | ◦ i = i. Therefore,
i ◦ j = 1M . (2.5)
In light of Proposition 2.1 and Proposition 2.2, we can say that if M (A) has the UMP of a free monoid
on A, then M (A) is isomorphic to A∗ .
17
2 Free Categories 18
z
A B
x y
u
C D
Definition 2.1. A (directed) graph consists of two sets: a set E of edges, and a set V of vertices,
and two functions s : E → V (called source) adn t : E → V (called target). We denote a directed
graph G by a quadruple (V, E, s, t). A path in a graph G is a finite sequence of edges e1 , . . . , en
such that t (ei ) = s (ei+1 ) for each i = 1, . . . , n − 1.
Put dom (en · · · e1 ) = s (e1 ) and cod (en · · · e1 ) = t (en ), and define composition by concatenation:
z◦x
y◦u
x y
C(G) C A z B D
y◦u◦x u
u◦x
V f0
V0 V f0
V0
Remark 2.2. Note that if G has only one vertex, then C (G) is just the free monoid on the set of
edges of G. If, on the other hand, G has only vertices with no edges, then C (G) is the discrete
category on the set of vertices of G.
18
2 Free Categories 19
Let us now see that C (G) has a UMP (universal mapping property). Define a “forgetful functor”
U : Cat → Graphs in the following way: the underlying graph of a (small) category has the collection
of arrows as the set of edges E and the collection of objects as the set of vertices V , with s = dom
and t = cod.
Also, observe that we can describe a category C with a diagram as below:
cod
◦
C2 C1 i C0 ,
dom
where C0 is the collection of objects of C1 , C1 is the collection of arrows, i is the identity arrow
operation, and C2 is the collection
F2 F1 F0
cod
◦
D2 D1 i D0 ,
dom
where F2 (f, g) = (F1 (f ) , F1 (g)). Commutativity of the first square tells us that
F1 (g ◦ f ) = F1 (g) ◦ F1 (f ) . (2.8)
Commutativity of the second square is reminiscent of graph homomorphism if one removes the identity
arrow operation. Note that the underlying graph of a category C can be depicted as
cod
C1 C0 .
dom
And functors (arrows of Cat) under U are sent to graph homomorphisms (arrows of Graphs), i.e.
cod
◦
C2 C1 i C0
dom
F2 F1 F0
cod
◦
D2 D1 i D0 ,
dom
is sent to
19
2 Free Categories 20
cod
C1 C0
dom
F1 F0
cod
D1 D0
dom
under U. Given a category C, its underlying graph is denoted by |C| = U (C), where U is the forgetful
functor U : Cat → Graphs. The free category C (G) on a graph G has the following universal
mapping property (UMP).
h
in Cat : C (G) D
|h|
in Graphs : |C (G)| |D|
i
h
The free category on a graph with just one vertex is just a free monoid on the set oof edges. The free
category on a graph with two vertices and one edge between them is the finite category 2. On the
other hand, the free category on a graph of the form
e
A B
f
has (in addition to the identity arrows) the infinitely many arrows:
20
3 Abstract Characterizations
§3.1 Epis and Monos
In Sets, a function f : A → B is called
Proposition 3.1
A function f : A → B between sets is a monomorphism if and only if it is injective.
Proof. (⇒) Suppose f : A ↣ B. We need to show that f is injective. Suppose f (a) = f (a0 ) for some
a, a0 ∈ A. Consider functions g, h : {∗} → A as g (∗) = a and h (∗) = a0 . Then
(f ◦ g) (∗) = f (g (∗)) = f (a) = f a0 = f (h (∗)) = (f ◦ h) (∗) . (3.1)
Proposition 3.2
A function f : A → B between sets is an epimorphism if and only if it is surjective.
Proof. (⇒) Suppose f : A ↠ B. We need to show that f is surjective. We construct two functions
g1 , g2 : B → {0, 1} as follows:
(
0 if b ∈ im f
g1 (b) = 0 and g2 (b) = (3.3)
1 otherwise.
21
3 Abstract Characterizations 22
f g1
A B {0, 1}
g2
Since f is surjective, for any b ∈ B, there exists a ∈ A such that f (a) = b. Then we have
So g1 (b) = g2 (b), and this is true for any b ∈ B. Therefore, g1 = g2 and hence f is an epimorphism. ■
Monomorphisms are often obbreviated as monos or monic, epimorphisms are often obbreviated as epis
or epic.
Proposition 3.3
A monoid homomorphism h : M → N is monic if and only if the underlying function |h| : |M | →
|N | is monic (i.e. injective by Proposition 3.1).
Proof. (⇒) Suppose h is monic. We need to show that |h| is injective. Let |h| (m1 ) = |h| (m2 ) for
m1 , m2 ∈ |M |. Take two functions x, y : 1 → |M |, where 1 = {∗} is any singleton set, defined by
x (∗) = m1 and y (∗) = m2 . Let M (1) be the free monoid generated by 1. By the UMP of a free
monoid, there are unique monoid homomorphisms x : M (1) → M and y : M (1) → M such that the
following diagrams commute:
|x| |y|
|M (1)| |M | |M (1)| |M |
i x i y
1 1
In other words, |x| ◦ i = x and |y| ◦ i = y. Furthermore, by the UMP of M (1) for the functions
|h| ◦ x, |h| ◦ y : 1 → N , there are unique monoid homomorphisms f : M (1) → N and g : M (1) → N
such that the following diagrams commute:
|f | |g|
|M (1)| |N | |M (1)| |N |
i |h|◦x i |h|◦y
1 1
But since the following diagrams commute,
|h|◦|x|=|h◦x| |h|◦|y|=|h◦y|
|M (1)| |M | |N | |M (1)| |M | |N |
|x| |h| |y| |h|
i x i y
1 |h|◦x
1 |h|◦y
22
3 Abstract Characterizations 23
f = h ◦ x and g = h ◦ y. (3.6)
Since |h| is monic, we must have |f | = |g|. Therefore, f = g, and hence h : M → N is monic. ■
Example 3.1. In the category Mon of monoids and monoid homomorphisms, there is a monic
homomorphism N ↣ Z, where N = (N, +, 0) is the additive monoid of natural numbers, and Z =
(Z, +, 0) is the additive monoid of integers. This map given by the inclusion N ⊂ Z of sets is monic in
Mon, by Proposition 3.3, since it is an injective homomorphism. We shall now show that this is also
epic in Mon.
f
i
N Z M
g
Given any monoid M = (M, ∗, u), with the underlying set M , let f, g : Z → M be monoid homomor-
phisms such that f ◦ i = g ◦ i. To prove that i is epic, we need to show that f = g.
Since i : N → Z is the inclusion, f ◦ i = g ◦ i gives us that f N = g N , i.e. f (n) = g (n) for each
n ∈ N. We need to show that f (−n) = g (−n).
Proposition 3.4
Every isomorphism is both monic and epic.
23
3 Abstract Characterizations 24
x m
A B C
y
m◦e=1C
e
e◦m=1B f
B m C C
g
Remark 3.1. In Sets, the converse of Proposition 3.4 also holds: every monic and epic is an
isomorphism. But this is not true, in general. The counterexample is provided in the context of
the category Mon in Example 3.1. There we saw that the inclusion homomorphism i : (N, +, 0) →
(Z, +, 0) is both monic and epic. But this arrow in Mon is not an iso, i.e. its inverse does not
exist. In particular, there does not exist an arrow j : Z → N such that i ◦ j = 1Z and j ◦ i = 1N .
Proposition 3.5
With regard to a commutative triangle,
f
A B
g
h
C
in any category C,
(b) if h is monic, so is f ;
(c) if h is epic, so is g;
Proof. (a) Suppose f and g are isos. Then there are arrows f −1 : B → A and g −1 : C → B such that
f ◦ f −1 = 1A , f −1 ◦ f = 1B , g ◦ g −1 = 1C , g −1 ◦ g = 1B . Since the triangle above is commutative,
h = g ◦ f . We define k : C → A as k = f −1 ◦ g −1 . Then
h ◦ k = (g ◦ f ) ◦ f −1 ◦ g −1 = g ◦ 1A ◦g −1 = 1C . (3.13)
k ◦ h = f −1 ◦ g −1 ◦ (g ◦ f ) = f −1 ◦ 1B ◦f = 1A . (3.14)
Therefore, h is an isomorphism, and k = h−1 .
Suppose f and g are monos. We want to show that h : A → C is monic. Suppose there are arrows
x, y : X ⇒ A such that h ◦ x = h ◦ y.
24
3 Abstract Characterizations 25
B
f g
x
X A h=g◦f
C
y
h ◦ x = h ◦ y =⇒ (g ◦ f ) ◦ x = (g ◦ f ) ◦ y =⇒ g ◦ (f ◦ x) = g ◦ (f ◦ y) . (3.15)
Since g is monic, we must have f ◦ x = f ◦ y. Again, since f is monic, we must have x = y. So
h ◦ x = h ◦ y implies x = y. Therefore, h is monic.
Suppose f and g are epis. We want to show that h : A → C is epic. Suppose there are arrows
x, y : C ⇒ Y such that x ◦ h = y ◦ h.
B
f g
x
A h=g◦f
C Y
y
x ◦ h = y ◦ h =⇒ x ◦ (g ◦ f ) = y ◦ x ◦ (g ◦ f ) =⇒ (x ◦ g) ◦ f = (y ◦ g) ◦ f. (3.16)
Since f is epic, we must have x ◦ g = y ◦ g. Again, since g is epic, we must have x = y. So
x ◦ h = y ◦ h implies x = y. Therefore, h is epic.
(b) We need to show that f : A → B is monic. Suppose there are arrows x, y : X ⇒ A such that
f ◦ x = f ◦ y.
B
f g
x
X A h=g◦f
C
y
f ◦ x = f ◦ y =⇒ g ◦ f ◦ x = g ◦ f ◦ y =⇒ h ◦ x = h ◦ y. (3.17)
Since h is monic, h ◦ x = h ◦ y implies x = y. Therefore, since f ◦ x = f ◦ y forces x = y, f is
monic.
(c) We need to show that g : B → C is epic. Suppose there are arrows x, y : C ⇒ Y such that
x ◦ g = y ◦ g.
B
f g
x
A h=g◦f
C Y
y
x ◦ g = y ◦ g =⇒ x ◦ g ◦ f = y ◦ g ◦ f =⇒ x ◦ h = y ◦ h. (3.18)
Since h is epic, x ◦ h = y ◦ h implies x = y. Therefore, since x ◦ g = y ◦ g forces x = y, g is epic.
■
25
3 Abstract Characterizations 26
g
h
C
If h is monic, then so is f as proven in Proposition 3.5. However, h being monic does not
necessarily imply g is monic. Similarly, h being epic also does not imply f is epic. The following
is such an example.
Example 3.2. Let us consider the category Sets. Take A = C = {0} and B = {0, 1}. Define
f : A → B by f (0) = 0, and g : B → C by g (x) = 0 for x ∈ {0, 1}.
Then g ◦ f : A → C is
(g ◦ f ) (0) = g (0) = 0. (3.19)
So h = g ◦ f is an isomorphism. In particular, h is monic. However, g : B → C is not monic (i.e.
injective since we are in Sets) because g (0) = g (1). Similarly, h is epic as well, but f is not.
f ◦ x = f ◦ y =⇒ g ◦ (f ◦ x) = g ◦ (f ◦ y)
=⇒ (g ◦ f ) ◦ x = (g ◦ f ) ◦ y
=⇒ 1A ◦x = 1A ◦y
=⇒ x = y. (3.20)
p ◦ g = q ◦ g =⇒ (p ◦ g) ◦ f = (q ◦ g) ◦ f
=⇒ p ◦ (g ◦ f ) = q ◦ (g ◦ f )
=⇒ p ◦ 1A = q ◦ 1A
=⇒ p = q. (3.21)
Therefore, g : B → A is epic.
Definition 3.2. A split mono is an arrow with a left inverse. A split epi is an arrow with a
right inverse. Given arrows e : X → A and s : A → X with e ◦ s = 1A , the arrow s is called a
section or splitting of e, and e is called a retraction of s. The object A is called a retract of
X. Therefore, section is monic and retraction is epic.
26
3 Abstract Characterizations 27
Remark 3.3. Since functors preserve identities, they also preserve split epis and split monos.
Functors do not preserve epi, in general. Counterexample is the forgetful functor U : Mon → Sets,
which does not preserve the epi i : N → Z, i.e. U (i) : N → Z is not an epi in Sets as it’s not
surjective.
In Sets, every mono splits except those of the form ∅ ↣ A. The condition that every epi splits is the
categorical version of the axiom of choice. Let us see this fact in detail. Consider an epi e : E ↠ X.
We then have the following family of nonempty sets
Each Ex is nonempty since e is surjective. Now, for each x ∈ X, one chooses an element s (x) from
Ex ⊂ E, and thus define the function s : X → E. By construction, e (s (x)) = x for each x ∈ X, i.e.
e ◦ s = 1X . One, thus finds that the choice function s : X → E associated with the family (Ex )x∈X is
exactly a splitting of e.
Let us do the reverse construction now. Given a family of nonempty subsets (Ex )x∈X , take
[
E = {(x, y) | x ∈ X, y ∈ Ex } = ({x} × Ex ) , (3.22)
x∈X
and define the epi e : E ↠ X by (x, y) 7→ x. A splitting s : X → E hence determines a choice function
for the family (Ex )x∈X ,
Remark 3.4. A notion related to the existence of “choice function” is that of being projective.
An object P is said to be projective if for any e : E ↠ X and arrow f : P → X, there is
some (not necessarily unique) arrow f : P → E such that e ◦ f = f , as indicated in the following
commutative diagram:
E
f
e
P f
X
E
s
e
P 1P
P
27
3 Abstract Characterizations 28
Proposition 3.6
Initial and terminal objects are unique up to isomorphism.
Proof. Suppose both 0 and 00 are initial objects in some category C. Since 0 is initial, there is a unique
arrow u : 0 → 00 . Again, since 00 is initial, there is a unique arrow v : 00 → 0. Then we can form the
composition v ◦ u : 0 → 0. But since 0 is an initial object, there is a unique arrow 0 → 0, which has
to be the identity arrow 10 . Therefore, v ◦ u = 10 .
0 u
00
u◦v=100
v
v◦u=10
0 u
00
Similarly, u ◦ v : 00 → 00 is an arrow from 00 to itself. But since 00 is an initial object, there is a
unique arrow 00 → 00 , which has to be the identity arrow 100 . Therefore, u ◦ v = 100 . So 0 and 00 are
isomorphic via a unique isomorphism u : 0 → 00 .
Let 1 and 10 be terminal objects of C. Since 10 is terminal, there is a unique arrow u : 1 → 10 . Again,
since 1 is terminal, there is a unique arrow v : 10 → 1. Then we can form the composition v ◦ u : 1 → 1.
But since 1 is a terminal object, there is a unique arrow 1 → 1, which has to be the identity arrow 11 .
Therefore, v ◦ u = 11 .
1 u
10
u◦v=110
v
v◦u=11
1 u
10
Similarly, u ◦ v : 10 → 10 is an arrow from 10 to itself. But since 10 is a terminal object, there is a
unique arrow 10 → 10 , which has to be the identity arrow 110 . Therefore, u ◦ v = 110 . So 1 and 10 are
isomorphic via a unique isomorphism u : 1 → 10 . ■
Example 3.3. 1. In Sets, the empty set ∅ is initial, and sny singleton set is terminal. Indeed, for
any set B, there is a unique function from ∅ to B, called the empty function. When B = ∅, the
empty function from ∅ to ∅ is the required identity arrow on the object ∅ ∈ Ob (Sets).
There is also a unique function from any set B to a singleton set {∗}, f : B → {∗}, given by f (b) = ∗
for every b ∈ B. It is unique in the sense that there can’t be any other function from the same set
B to the singleton set {∗}. In other words, HomSets (B, {∗}) for a given set B ∈ Ob (Sets) is a
singleton set.
2. In VectK , the category of vector spaces over the field K and linear transformations, the 0-
dimensional vector space {0} consisting of the zero-vector (additive identity) only is both the initial
and terminal objects.
Given a K-vector space V , there is only one linear transformation from {0} to V , namely the one
that takes 0 to 0V , the additive identity of the K-vector space V . Also, given a K-vector space V ,
there is only one linear transformation from V to {0} that takes all of V to 0. In other words, for
a given V ∈ Ob (VectK ), both HomVectK ({0} , V ) and HomVectK (V, {0}) are singleton sets.
28
3 Abstract Characterizations 29
Definition 3.4 (Boolean algebra). A Boolean algebra is a poset (B, ⩽) together with distin-
guished elements 0, 1, binary operations a ∨ b (read a join b) and a ∧ b (read a meet b) and a
unary operation ¬b (read b complement) such that the following conditions are satisfied for all
a, b, c ∈ B:
1. 0 ⩽ a and a ⩽ 1.
4. a ⩽ ¬b if and only if a ∧ b = 0.
5. ¬ (¬a) = a.
A typical example of a Boolean algebra is the power set P (X) of a set X, ordered by inclusion
A ⊆ B, with the distinguished elements 0 = ∅ and 1 = X. The binary operations join and meet are
given by union and intersection of subsets, respectively, and the unary operation complementation is
¬A = X \ A.
The union and intersection of sets satisfy A ∩ B ⊆ A ⊆ A ∪ B and A ∩ B ⊆ B ⊆ A ∪ B. The same
is satisfied in any Boolean algebra.
Proposition 3.7
In a Boolean algebra B, a ∧ b ⩽ a ⩽ a ∨ b and a ∧ b ⩽ b ⩽ a ∨ b for any a, b ∈ B.
Proof. Since (B, ⩽) is a poset, by the reflexivity property, a ∨ b ⩽ a ∨ b. Then using property 2 from
the definition of Boolean algebra, we get
a ⩽ a ∨ b and b ⩽ a ∨ b. (3.23)
Again, a ∧ b ⩽ a ∧ b by reflexivity. Then using property 3 from the definition of Boolean algebra, we
get
a ∧ b ⩽ a and a ∧ b ⩽ b. (3.24)
Therefore, combining (3.23) and (3.24), we get a ∧ b ⩽ a ⩽ a ∨ b and a ∧ b ⩽ b ⩽ a ∨ b. ■
A special case of Boolean algebras is the 2-element Boolean algebra 2 = {0, 1}, considered as P ({∗}),
the power set pf the singleton set {∗} which consists of only the empty set ∅ and {∗}.
The category of Boolean algebras is denoted by BA, where objects are Boolean algebras and arrows
are Boolean homomorphisms, that is functions h : B → B 0 that, in addition to being monotone, satisfy
• h (0B ) = 0B 0 , h (1B ) = 1B 0 ;
• h (a ∨B b) = h (a) ∨B 0 h (b);
• h (a ∧B b) = h (a) ∧B 0 h (b);
• h (¬B a) = ¬B 0 h (a),
for any a, b ∈ B. In this category, 2 is the initial object. There is this 1-element Boolean algebra
1 = {0}, which is regarded as the power set of ∅, i.e. 1 ≡ P (∅) = {∅}. In this situation, the
distinguished elements 0 and 1 conicide. 1 acts as the terminal object of BA. In other words, given
a Boolean algebra B, there is exactly one boolean homomorphism from h : 2 → B, given by
h (0) = 0B and h (1) = 1B .
Furthermore, there is exactly one boolean homomorphism f : B → 1 given by
f (b) = 0
for any b ∈ B.
29
3 Abstract Characterizations 30
Definition 3.5 (Filter). A filter in a Boolean algebra B is a nonempty subset F ⊆ B that is closed
upward and under meets, i.e.
• a ∈ F and a ⩽ b implies b ∈ F ,
• a, b ∈ F implies a ∧ b ∈ F .
Definition 3.6 (Ultrafilter). A filter F is called maximal if F ⊂ F 0 implies F 0 = B, i.e. the only
strictly larger filter is the “improper” filter B itself. A maximal filter is called an ultrafilter.
One can easily verify that a filter F is an ultrafilter if and only if for every element b ∈ B, either b ∈ F
or ¬b ∈ F and not both.
Theorem 3.8
In a Boolean algebra B, a filter F is an ultrafilter if and only if for every element b ∈ B, either
b ∈ F or ¬b ∈ F and not both.
Proof. (⇒) Suppose F ⊂ B is an ultrafilter. If both b and ¬b are in F , then so is their meet b ∧ ¬b.
But we have
b ⩽ b = ¬ (¬b) . (3.25)
Then using property 4 from the definition of Boolean algebra, we get
b ∧ ¬b = 0. (3.26)
So 0 ∈ F . But 0 ⩽ a for each a ∈ B. This gives us that a ∈ F for any a ∈ B, i.e. F = B, which
contradicts with F being an ultrafilter. Therefore, both b and ¬b cannot be in F . Assume for the
sake of contradiction that neither b nor ¬b is in F , i.e. b 6∈ F and ¬b 6∈ F . Consider the following set:
u ∧ b ⩽ v ⩽ w. (3.28)
So u ∧ b ⩽ w, so w ∈ G.
(u1 ∧ u2 ) ∧ b ⩽ u1 ∧ b ⩽ v1 . (3.30)
Similarly,
(u1 ∧ u2 ) ∧ b ⩽ u2 ∧ b ⩽ v2 . (3.31)
Again, using property 3 from the definition of Boolean algebra, we get
(u1 ∧ u2 ) ∧ b ⩽ v1 ∧ v2 . (3.32)
30
3 Abstract Characterizations 31
u ∧ b ⩽ u. (3.33)
u∧b⩽b (3.34)
gives us that b ∈ F , since F is closed upward. Thus we arrive at a contradiction assuming neither b
not ¬b is in F . So exactly one of b or ¬b must be in F .
(⇐) Suppose F is a filter such that for every element b ∈ B, either b ∈ F or ¬b ∈ F and not both.
Let F 0 be another filter strictly containing F , i.e. F ⊂ F 0 . Take an element a ∈ F 0 \ F . a 6∈ F , so
¬a ∈ F . Then
¬a ∈ F ⊂ F 0 =⇒ ¬a ∈ F 0 .
Therefore, both a and ¬a are in F 0 . Since F 0 is a filter, a ∧ ¬a ∈ F 0 . By (3.26), a ∧ ¬a = 0 ∈ F 0 . But
0 ⩽ c for each c ∈ B. This gives us that c ∈ F 0 for any c ∈ B, i.e. F 0 = B. Therefore, any strictly
larger filter than F must be the whole B. So F is an ultrafilter. ■
X∼
= HomSets (1, X) . (3.35)
x (0) = 0V .
Given two K-vector spaces V and W , and two linear transformations f, g : V → W , we always have
f ◦ x = g ◦ x, since
No matter how different f and g are, composing them with x yields the same arrow. This is not what
we want. Ideally, we want generalized elements to have the following property:
The motivation for requiring this condition comes from sets and functions. We call two functions
f, g : X → Y the same if and only if f (x) = g (x) for every x ∈ X.
31
3 Abstract Characterizations 32
For this, we draw motivations from the proof of Generalized Cayley’s Theorem. In the sketch
of the proof, we showed that a “not too big” category is isomorphic to a concrete category (i.e. a
category where objects are sets and arrows are functions between them). We’ve seen that under the
isomorphism, the object C of the “not too big” category C corresponds to the set of arrows whose
codomains are C. Keeping this in mind, we define the generalized elements of C to be the arrows
whose codomainds are C.
Definition 3.7 (Generalized Element). Let C be a category, and A ∈ Ob (C). The arrows whose
codomains are A are called generalized elements of A. In other words, any arbitrary arrow
f : X → A (with arbitrary domain X) is a generalized element of A.
Then these generalized elements satisfy the required property that f = g if and only if f ◦ x = g ◦ x
for every generalized element x of dom f (= dom g). Let f, g : A → B be two arrows. If f = g, then
obviously f ◦ x = g ◦ x. Conversely, suppose f ◦ x = g ◦ x for every generalized element x of A. Then
if we choose x = 1A (which is an arrow with codomain A, so it’s a generalized element of A), we get
f ◦ 1A = g ◦ 1A =⇒ f = g. (3.36)
§3.5 Products
Let us begin by considering products of sets. Given sets A and B, the cartesian product of A and B
is the set of ordered pairs
A × B = {(a, b) | a ∈ A, b ∈ B} .
Observe that there are 2 coordinate projections
π1 π2
A A×B B
with π1 (a, b) = a and π2 (a, b) = b. Indeed, given any element c ∈ A × B, one has c = (π1 c, π2 c). This
situation is captured by the following commutative diagram:
1
a b
(a,b)
A π1 A×B π2 B
Definition 3.8 (Product). In any category C, a product diagram for the objects A and B consists
of an object P and arrows
p1 p2
A P B
32
3 Abstract Characterizations 33
x1 x2
A X B
there exists a unique morphism u : X → P such that the following diagram commutes:
X
x1 x2
∃! u
p1 p2
A P B
i.e. x1 = p1 ◦ u and x2 = p2 ◦ u.
Proposition 3.9
Products are unique up to isomorphism.
q1 q2
A Q B
p1 j p2
P
Then we have
p1 = q1 ◦ i = p1 ◦ (j ◦ i) and p2 = q2 ◦ i = p2 ◦ (j ◦ i) . (3.37)
Since P is a product, there is a unique f : P → P such that the following diagram commutes:
P
p1 p2
f
A p1 P p2 B
f = 1P makes this diagram commutative, since p1 = p1 ◦ 1P and p2 = p2 ◦ 1P . Therefore, the
uniqueness of f guarantees that f = 1P . Furthermore, (3.37) tells us that f = j ◦ i also makes the
above diagram commutative. Therefore,
f = 1P = j ◦ i. (3.38)
33
3 Abstract Characterizations 34
Q
q1 q2
j
p1 p2
A P B
q1 i q2
Q
we have
q1 = p1 ◦ j = q1 ◦ (i ◦ j) and q2 = p2 ◦ i = q2 ◦ (i ◦ j) . (3.39)
Since Q is a product, there is a unique g : Q → Q such that the following diagram commutes:
Q
q1 q2
g
A q1 Q q2 B
g = 1Q makes this diagram commutative, since q1 = q1 ◦ 1Q and q2 = q2 ◦ 1Q . Therefore, the
uniqueness of g guarantees that g = 1Q . Furthermore, (3.39) tells us that g = i ◦ j also makes the
above diagram commutative. Therefore,
g = 1Q = i ◦ j. (3.40)
there is a unique arrow u : X → A×B such that xi = pi ◦u for i = 1, 2. We denote u = hx1 , x2 i. Hence,
p1 ◦ hx1 , x2 i = x1 and p2 ◦ hx1 , x2 i = x2 . Now, however, a pair of objects may have different products
in a category C. For example, given a product A × B, p1 , p2 and an isomorphism h : A × B → Q, one
finds that Q, p1 ◦ h−1 , p2 ◦ h−1 is also a product of A and B.
u
x1 x2
Q e
u
p1 ◦h−1 p2 ◦h−1
h−1
A p1 A×B p2 B
x x
Now, given a diagram A 1
X 2
e : X → A × B such that p1 ◦ u
B , there exists unique u e = x1
e e −1
and p2 ◦ u = x2 . Define u : X → Q as u = h ◦ u. Then h ◦ u = u. So
e
e = p1 ◦ h−1 ◦ u and x2 = p2 ◦ u
x1 = p 1 ◦ u e = p2 ◦ h−1 ◦ u,
34
3 Abstract Characterizations 35
e = h−1 ◦ v =⇒ v = h ◦ u
u e = u.
So u is unique. This proves that Q, p1 ◦h−1 , p2 ◦h−1 fulfills the universal property of a product diagram.
Example 3.4. 1. Products of “structured sets” like monoids or groups can often be constructed as
products of the underlying sets with componentwise operations: if G and H are groups, then G × H
can be constructed by taking the underlying set of G × H to be the set {hg, hi | g ∈ G, h ∈ H} and
define the binary operation in G × H by
hg, hi ∗G×H g 0 , h0 = g ∗G g 0 , h ∗H h0 ,
where the group G is given by the triple (G, ∗G , uG ) and the group H is given by the triple (H, ∗H , uH ).
The unit of G × H is given by
uG×H = huG , uH i .
The inverse of hg, hi in G × H is D E
hg, hi−1 = g −1 , h−1 .
hg, hi 7→ g (or h) .
[Link] (P, ⩽) be a poset and consider a product p × q of elements p, q ∈ P . We must have projections
p × q → p and p × q → q. In a poset, these arrows indicate
p × q ⩽ p and p × q ⩽ q
Remark 3.5. Note that the projection arrows p1 : A × B → A and p2 : A × B → B need not be
epic. In Sets, let A be a non-empty set. Consider the product of ∅ and A. Then the projection
p2 : ∅ × A → A
is not surjective, since the domain is empty set but the codomain is nonempty. Therefore, the
projection p2 is not an epimorphism in Sets.
Recall that O (X × Y ) is generated by basic open sets of the form U × V , where U ∈ O (X) and
V ∈ O (Y ), so that every W ∈ O (X × Y ) is a union of such basic open sets. We have the following
observations:
35
3 Abstract Characterizations 36
p−1
1 (U ) = U × Y ∈ O (X × Y ) ,
p−1
2 (V ) = X × V ∈ O (X × Y ) .
f −1 (U × V ) = f −1 ((U × Y ) ∩ (X × V ))
= f −1 (U × Y ) ∩ f −1 (X × V )
= f −1 p−1
1 (U ) ∩ f
−1
p−1
2 (V )
Both f1−1 (U ) and f2−1 (V ) are open in Z since f1 , f2 are continuous. Hence, f is continuous.
B q1 B × B0 q2 B0
f × f 0 = f ◦ p1 , f 0 ◦ p2 . (3.43)
36
3 Abstract Characterizations 37
In other words, f × f 0 is the unique arrow from A × A0 to B × B 0 which makes the above diagram
(3.42) commutative. One can, therefore, construct a functor × : C × C → C 1 as follows:
× A, A0 = A × A0 and × f, f 0 = f × f 0 . (3.44)
Let us now verify that × is indeed a functor. For an object (A, A0 ) in C × C, let 1(A,A0 ) = (1A , 1A0 ) be
its identity arrow. We need to show that × 1(A,A0 ) = 1A × 1A0 = 1A×A0 .
p1 p2
A A × A0 A0
A p1 A × A0 p2 A0
1A × 1A0 is the unique arrow A × A0 → A × A0 that makes this diagram commute. If we choose 1A×A0
in place of 1A × 1A0 , then also the diagram commutes:
p1 p2
A A × A0 A0
A p1 A × A0 p2 A0
since
p1 ◦ 1A×A0 = p1 = 1A ◦p1 and p2 ◦ 1A×A0 = p2 = 1A0 ◦p2 .
Therefore, by the uniqueness, 1A × 1A0 = 1A×A0 . Hence,
× 1(A,A0 ) = × (1A , 1A0 ) = 1A × 1A0 = 1A×A0 . (3.45)
Let (f, f 0 ) : (A, A0 ) → (B, B 0 ) and (g, g 0 ) : (B, B 0 ) → (C, C 0 ) be arrows in C × C. Then (g, g 0 ) ◦ (f, f 0 ) =
(g ◦ f, g 0 ◦ f 0 ). Consider the following diagram:
p1 p2
A A × A0 A0
f ◦p1 f 0 ◦p2
f f ×f 0 f0
q1 q2
B B × B0 B0
g◦q1 g 0 ◦q2
g g×g 0 g0
C r1 C × C0 r2 C0
In this diagram, f × f 0 : A × A0 → B × B 0 and g × g 0 are the unique maps such that the diagram
above commutes. In other words,
q1 ◦ (f × f 0 ) = f ◦ p1 , q2 ◦ f × f 0 = f 0 ◦ p2 , and (3.46)
0 0 0
r1 ◦ (g × g ) = g ◦ q1 , r2 ◦ g × g = g ◦ q2 . (3.47)
1
C × C is the product category as discussed in Section 1.5. An object in C × C is of the form (A, A0 ) with A, A0 ∈ Ob (C).
Given arrows f : A → B and f 0 : A0 → B 0 in C, one has (f, f 0 ) : (A, A0 ) → (B, B 0 ) as an arrow in C × C between
objects (A, A0 ) and (B, B 0 ).
37
3 Abstract Characterizations 38
p1 p2
A A × A0 A0
C r1 C × C0 r2 C0
In other words,
r1 ◦ (g ◦ f ) × (g 0 ◦ f 0 ) = g ◦ f ◦ p1 and r2 ◦ (g ◦ f ) × (g 0 ◦ f 0 ) = g 0 ◦ f 0 ◦ p2 . (3.48)
r1 ◦ (g × g 0 ) ◦ (f × f 0 ) = g ◦ q1 ◦ (f × f 0 ) = g ◦ f ◦ p1 , (3.49)
0 0 0 0 0 0
r2 ◦ (g × g ) ◦ (f × f ) = g ◦ q2 ◦ (f × f ) = g ◦ f ◦ p2 . (3.50)
p1 p2
A A × A0 A0
C r1 C × C0 r2 C0
Proposition 3.10
Given arrows f : X → A and g : X → B, one forms hf, gi : X → A × B. Then for any arrow
x : Y → X,
hf, gi ◦ x = hf ◦ x, g ◦ xi .
hf ◦x,g◦xi
f ◦x g◦x
X
f g
hf,gi
A π1 A×B π2 B
π1 ◦ hf ◦ x, g ◦ xi = f ◦ x and π2 ◦ hf ◦ x, g ◦ xi = g ◦ x.
hf, gi ◦ x = hf ◦ x, g ◦ xi . (3.54)
38
3 Abstract Characterizations 39
§3.6 Hom-sets
We are dealing with locally small categories, where given any pair of objects A and B, the collection
HomC (A, B) of all the arrows from A to B forms a set. We call such a set of arrows Hom-set. Now,
fix A ∈ Ob (C) once and for all. Then we consider a functor HomC (A, −) : C → Sets as follows:
C Sets
C HomC (A, C)
HomC (A, −)
g HomC (A,g)
D HomC (A, D)
with the function HomC (A, g) : HomC (A, C) → HomC (A, D) defined by
HomC (A, g) (f ) = g ◦ f,
for each f ∈ HomC (A, C). HomC (A, −) is called the representable functor of A. Let us now show
that HomC (A, 1X ) = 1HomC (A,X) .
C Sets
X HomC (A, X)
HomC (A, −)
1X HomC (A,1X )
X HomC (A, X)
for any x ∈ HomC (A, X). Therefore, HomC (A, 1X ) = 1HomC (A,X) .
Now, take two composable arrows g : Y → Z and f : X → Y in C. We want to show that
HomC (A, g ◦ f ) = HomC (A, g) ◦ HomC (A, f ) : HomC (A, X) → HomC (A, Z) .
We will now present an alternative characterization of product using Hom-sets. For any object P ,
a pair of arrows p1 : P → A and p2 : P → B determine an element (p1 , p2 ) of the set
39
3 Abstract Characterizations 40
X
x1 =p1 ◦x x2 =p2 ◦x
x
A p1 P p2 B
ϑX ≡ (HomC (X, p1 ) , HomC (X, p2 )) : HomC (X, P ) → HomC (X, A) × HomC (X, B) .
In other words,
ϑ (x) = (p1 ◦ x, p2 ◦ x) = (x1 , x2 ) . (3.58)
Proposition 3.11
p1 p2
A diagram of the form A P B is a product diagram if and only if for every object
X, the canonical function ϑX defined by (3.58) is an isomorphism,
∼
=
ϑX : HomC (X, P ) −
→ HomC (X, A) × HomC (X, B) .
Proof. (⇒) Suppose P is a product. Then given any object X of C and a pair of arrows x1 : X → A
and x2 : X → B, there is a unique arrow x : X → P such that the following diagram commutes:
X
x1 x2
x
A p1 P p2 B
In other words, p1 ◦ x = x1 and p2 ◦ x = x2 . Therefore, for any object X, and x1 ∈ HomC (X, A),
x2 ∈ HomC (X, B), there is a unique x ∈ HomC (X, P ) which makes the above diagram commutative.
We, therefore, have a function
defined by
℘X (x1 , x2 ) = x, (3.59)
where x is the unique arrow from X to P such that p1 ◦ x = x1 and p2 ◦ x = x2 . In particular,
℘X (p1 ◦ x, p2 ◦ x) = x. (3.60)
Therefore,
ϑX ◦ ℘X = 1HomC (X,A)×HomC (X,B) and ℘X ◦ ϑX = 1HomC (X,P ) . (3.61)
Therefore, ϑX is an isomorphism for any object X.
40
3 Abstract Characterizations 41
is an isomorphism. Given any x1 ∈ HomC (X, A) and x2 ∈ HomC (X, B), since ϑX is an isomorphism
(i.e. a bijection since we are in Sets), there exists a unique x ∈ HomC (X, P ) such that ϑX (x) =
(x1 , x2 ). Using (3.58), we get
A p1 P p2 B
Therefore, P is a product of A and B. ■
Definition 3.9. Let C and D be categories with binary products. A functor F : C → D is said to
preserve binary products if it takes every product diagram
p1 p2
A A×B B in C
to a product diagram
F (p1 ) F (p2 )
F (A) F (A × B) F (B) in D.
is an isomorphism. Note that hF (p1 ) , F (p2 )i is the unique arrow from F (A × B) to F (A) × F (B)
such that the diagram below commutes:
F (A × B)
F (p1 ) F (p2 )
hF (p1 ),F (p2 )i
Therefore, if C and D are categories with binary products, then a functor F : C → D preserves binary
products if and only if F (A × B) ∼ = F (A) × F (B) in D for any A, B ∈ Ob (C). For example, the
forgetful functor U : Mon → Sets preserves binary products.
Corollary 3.12
For any object X in a category C with products, the covariant representable functor
preserves products.
41
3 Abstract Characterizations 42
Proof. For A, B ∈ Ob (C), Proposition 3.11 says that there is a canonical isomorphism
HomC (X, A × B) ∼
= HomC (X, A) × HomC (X, B) ,
HomC (X, −) (A × B) ∼
= HomC (X, −) (A) × HomC (X, −) (B) . (3.63)
p2 ◦r1 r2
f
B q1 B×C q2 C
In other words,
q1 ◦ f = p2 ◦ r1 , (3.64)
q2 ◦ f = r2 . (3.65)
(A × B) × C
p1 ◦r1 g
f
A s1 A × (B × C) s2 B×C
42
3 Abstract Characterizations 43
In other words,
s1 ◦ g = p1 ◦ r1 , (3.66)
s2 ◦ g = f. (3.67)
s1 q1 ◦s2
h
A p1 A×B p2 B
In other words,
p1 ◦ h = s1 , (3.68)
p2 ◦ h = q1 ◦ s2 . (3.69)
Given h : A×(B × C) → A×B and q2 ◦s2 : A×(B × C) → c, there exists a unique i : A×(B × C) →
(A × B) × C such that the following diagram commutes:
A × (B × C)
h q2 ◦s2
i
A×B r1 (A × B) × C r2 C
In other words,
r1 ◦ i = h, (3.70)
r2 ◦ i = q2 ◦ s2 . (3.71)
A × (B × C)
q1 ◦s2 q1 ◦s2
s2 s2 ◦g◦i
B q1 B×C q2 C
43
3 Abstract Characterizations 44
q1 ◦ s2 ◦ g ◦ i = q1 ◦ f ◦ i = p2 ◦ r1 ◦ i = p2 ◦ h = q1 ◦ s2 . (3.72)
q2 ◦ s2 ◦ g ◦ i = q2 ◦ f ◦ i = r2 ◦ i = q2 ◦ s2 . (3.73)
So there are two arrows s2 , s2 ◦ g ◦ i : A × (B × C) → B × C and both of them makes the above
diagram commute. Therefore, by the universal property of the product B × C,
s2 = s2 ◦ g ◦ i. (3.74)
1A×(B×C)
s1 s2
g◦i
A s1 A × (B × C) s2 B×C
s1 ◦ g ◦ i = p1 ◦ r1 ◦ i = p1 ◦ h = s1 = s1 ◦ 1A×(B×C) . (3.75)
g ◦ i = 1A×(B×C) . (3.77)
(A × B) × C
p1 ◦r1 p2 ◦r1
r1 r1 ◦i◦g
A p1 A×B p2 B
p1 ◦ r1 ◦ i ◦ g = p1 ◦ h ◦ g = s1 ◦ g = p1 ◦ r1 . (3.78)
p2 ◦ r1 ◦ i ◦ g = p2 ◦ h ◦ g = q1 ◦ s2 ◦ g = q1 ◦ f = p2 ◦ r1 . (3.79)
So there are two arrows r1 , r1 ◦ i ◦ g : (A × B) × C → A × B and both of them makes the above diagram
commute. Therefore, by the universal property of the product A × B,
r1 = r1 ◦ i ◦ g. (3.80)
44
3 Abstract Characterizations 45
(A × B) × C
1(A×B)×C
r1 r2
i◦g
A×B r1 (A × B) × C r2 C
From (3.80),
r1 ◦ i ◦ g = r1 = r1 ◦ 1(A×B)×C . (3.81)
Also, (3.71), (3.67) and (3.65) gives us
r2 ◦ i ◦ g = q2 ◦ s2 ◦ g = q2 ◦ f = r2 = r2 ◦ 1(A×B)×C . (3.82)
So there are two arrows 1(A×B)×C , i ◦ g : (A × B) × C → (A × B) × C and both of them makes the
above diagram commute. Therefore, by the universal property of the product (A × B) × C,
i ◦ g = 1(A×B)×C . (3.83)
Furthermore, this isomorphism is “natural”. To make this notion precise, we need to define what a
natural transformation is.
Definition 3.10 (Natural Transformation). Let F and G be two functors between the categories C
and D. Then a natural transformation η : F ⇒ G is a family of arrows in D that satisfies the
following requirements:
2. Components must be such that for every arrow f : X → Y in C, one must have ηY ◦ F (f ) =
G (f ) ◦ ηX . In other words, the diagram below commutes:
F (f )
F (X) F (Y )
ηX ηY
G(X) G(Y )
G(f )
C η D
If for every object X ∈ Ob (C), the arrow ηX : F (X) → G (X) is an isomorphism in D, then
η : F ⇒ G is said to be a natural isomorphism. Two functors F and G between two categories are
called naturally isomorphic if there exists a natural isomorphism between them.
∼
=
When we say the isomorphism g : (A × B) × C − → A × (B × C) is natural, we mean that there
∼
=
is a natural isomorphism whose components are precisely these isomorphisms g : (A × B) × C − →
A × (B × C). To prove it, let us first define the product of three categories.
45
3 Abstract Characterizations 46
• The objects of C × D × E are ordered triples (C, D, E), where C ∈ Ob (C), D ∈ Ob (E),
E ∈ Ob (E).
1(C,D,E) = (1C , 1D , 1E ) .
One can easily verify that C × D × E is indeed a category. Now, suppose C is a category with products.
Then we define two functors from C × C × C to C.
F : C × C × C → C,
(A, B, C) 7→ (A × B) × C, (3.84)
(f, g, h) 7→ (f × g) × h.
G : C × C × C → C,
(A, B, C) 7→ A × (B × C) , (3.85)
(f, g, h) 7→ f × (g × h) .
One can easily check that F and G are functors. Now we define the natural transformation α as
follows:
F
C×C×C α C
Theorem 3.14
α defined as above is a natural isomorphism.
Proof. The components of α are isomorphisms. So n order to prove that α is a natural isomorphism,
we need to show the commutativity of the following square given an arrow (a, b, c) : (A, B, C) →
(A0 , B 0 , C 0 ) in C × C × C.
46
3 Abstract Characterizations 47
α(A,B,C)
(A × B) × C A × (B × C)
(a×b)×c a×(b×c)
(A0 × B 0 ) × C 0 α(A0 ,B 0 ,C 0 ) A0 × (B 0 × C 0 )
→ C 0.
r c
(A × B) × C −→
2
C−
Then there is a unique arrow u : (A × B) × C → B 0 × C 0 such that the following diagram commutes:
(A × B) × C
B0 B0 × C 0 C0
q10 q20
In other words,
q10 ◦ u = b ◦ p2 ◦ r1 , (3.87)
q10 ◦ u = c ◦ r2 (3.88)
(A × B) × C
A0 A0 × (B 0 × C 0 ) B0 × C 0
s01 s02
In other words,
s01 ◦ v = a ◦ p1 ◦ r1 , (3.90)
s02 ◦ v = hb ◦ p2 ◦ r1 , c ◦ r2 i . (3.91)
47
3 Abstract Characterizations 48
Now we claim that choosing v = [a × (b × c)] ◦ α(A,B,C) makes the above diagram commutative. The
uniqueness of v would then imply that v is precisely [a × (b × c)] ◦ α(A,B,C) .
a × (b × c) is the unique arrow A × (B × C) → A0 × (B 0 × C 0 ) such that the following diagram
commutes:
s1 s2
A A × (B × C) B×C
a a×(b×c) b×c
A0 A0 × (B 0 × C 0 ) B0 × C 0
s01 s02
So
s01 ◦ [a × (b × c)] ◦ α(A,B,C) = a ◦ s1 ◦ α(A,B,C) . (3.92)
α(A,B,C) is nothing but the isomorphism g in the proof of Theorem 3.13. So using (3.66), we get
s1 ◦ α(A,B,C) = p1 ◦ r1 . Therefore,
Furthermore,
s02 ◦ [a × (b × c)] ◦ α(A,B,C) = (b × c) ◦ s2 ◦ α(A,B,C) . (3.94)
Using (3.67), we get we get
s2 ◦ α(A,B,C) = f = hp2 ◦ r1 , r2 i . (3.95)
Now, consider the following commutative diagram:
(A × B) × C
p2 ◦r1 r2
f
q1 q2
B B×C C
b b×c c
B0 B0 × C 0 C0
q10 q20
f is the unique arrow that makes the upper triangles commute, and b × c is the unique arrow that
makes the lower squares commute. Therefore,
q10 ◦ (b × c) ◦ f = b ◦ q1 ◦ f = b ◦ p2 ◦ r1 , (3.96)
q20 ◦ (b × c) ◦ f = c ◦ q2 ◦ f = c ◦ r2 . (3.97)
(b × c) ◦ f = hb ◦ p2 ◦ r1 , c ◦ r2 i . (3.98)
Now we claim that v = α(A0 ,B 0 ,C 0 ) ◦ [(a × b) × c] also makes (3.89) commutative. The uniqueness of
v would then imply that v is precisely α(A0 ,B 0 ,C 0 ) ◦ [(a × b) × c].
48
3 Abstract Characterizations 49
Now, (a × b) × c is the unique arrow (A × B) → C → (A0 × B 0 ) → C 0 such the the following diagram
commutes:
r1 r2
A×B (A × B) × C C
a×b (a×b)×c c
A0 × B 0 (A0 × B 0 ) × C 0 C0
r10 r20
Therefore,
r10 ◦ [(a × b) × c] = (a × b) ◦ r1 . (3.104)
Furthermore, a × b is the unique arrow such that the following diagram commutes:
p1 p2
A A×B B
a a×b b
A0 A0 × B 0 B0
p01 p02
So
p01 ◦ (a × b) ◦ r1 = a ◦ p1 ◦ r1 . (3.105)
Combining (3.103), (3.104), (3.105), we get
Furthermore,
a×b (a×b)×c c
r10
A0 × B 0 (A0 × B 0 ) × C 0 C0
r20
p02 ◦r10
p02 f0
r20
B0 B0 × C 0 C0
q10 q20
(a × b) × c is the unique arrow that makes the upper squares commute. f 0 = hp02 ◦ r10 , r20 i is the
unique arrow that makes the lower triangles commute. Therefore,
49
3 Abstract Characterizations 50
f 0 ◦ [(a × b) × c] = hb ◦ p2 ◦ r1 , c ◦ r2 i . (3.110)
(a×b)×c a×(b×c)
(A0 × B 0 ) × C 0 α(A0 ,B 0 ,C 0 ) A0 × (B 0 × C 0 )
X p1 X ×1 p2 1
In other words,
p1 ◦ h1X , ui = 1X and p2 ◦ h1X , ui = u. (3.114)
We claim that p1 : X × 1 → X is an isomorphism, with inverse h1X , ui. Clearly, we have p1 ◦ h1X , ui =
1X . We need to show that h1X , ui ◦ p1 = 1X×1 .
p2 ◦ h1X , ui ◦ p1 is an arrow from X × 1 to 1. Since 1 is a terminal object, there is exactly one arrow
from X × 1 to 1. So p2 ◦ h1X , ui ◦ p1 = p2 . Therefore,
50
3 Abstract Characterizations 51
X ×1 X ×1
p1 p2 p1 p2
h1X ,ui◦p1 1X×1
X p1 X ×1 p2 1 X p1 X ×1 p2 1
Therefore, by the universal property of products, we must have h1X , ui ◦ p1 = 1X×1 . Therefore,
p1 : X × 1 → X is an isomorphism, with inverse h1X , ui : X → X × 1, i.e. X × 1 ∼
= X. ■
However, the converse of Proposition 3.15 is not, in general, true. If A is an object in a category C
with products such that X × A ∼
= A for every object X ∈ Ob (C), then A need not be a terminal object.
The following is a counterexample.
Example 3.5. Let ZN denote the set of all integer sequences, which is an object of the category
Groups. Let us consider the subcategory C of Groups consisting of only one object ZN , and all the
arrows from ZN to itself in Groups (often refered to as the full subcategory of Groups, with the
object ZN ). Then in this category C,
ZN × ZN = ZN .
The product diagram is as follows:
π1 π2
ZN ZN ZN
π1 (a0 , a1 , a2 , a3 , a4 , . . .) = (a1 , a3 , a5 , · · · ) ,
π2 (a0 , a1 , a2 , a3 , a4 , · · · ) = (a0 , a2 , a4 , a6 , · · · ) .
This is easily seen to satisfy the UMP of product. Now, in the category C, there is only one object.
So X × A ∼= A for every object X ∈ Ob (C) is clearly satisfied. But ZN is not a terminal object in this
category, since there are more than one arrows from ZN to itself in C.
The isomorphism we showed in Proposition 3.15 is not just any isomorphism. This isomorphism is
actually “natural”, meaning there is a natural isomorphism whose components are the isomorphisms
we saw in Proposition 3.15.
×(−,1)
C η C
1C
ηX =p1 ηX 0 =p01
X f
X0
But this square obviously commutes, since f × 11 is the unique arrow X × 1 → X 0 × 1 such that the
following diagram commutes:
51
3 Abstract Characterizations 52
p1 p2
X X ×1 1
f f ×11 11
X0 X0 × 1 1
p01 p02
The naturality square is precisely the left hand square of this diagram. So naturality holds. Therefore,
the isomorphism X × 1 ∼ = X is natural.
Now, the converse of Proposition 3.15 holds if we further assume that the isomorphism is natu-
ral.
Theorem 3.16
Let C be a category with products, and A ∈ Ob (C) such that η : × (−, A) ⇒ 1C is a natural
isomorphism. Then A is a terminal object of C.
C α C
1C
−1
αX =p1 ◦ηX
−1
αX 0 =p01 ◦ηX 0
(3.118)
X g X0
g g×1A 1A
X0 X0 × A A
p01 p02
In particular,
g ◦ p1 = p01 ◦ (g × 1A ) . (3.119)
The naturality of η guarantees the commutativity of the following square:
g×1A
X ×A X0 × A
ηX ηX 0
X g X0
52
3 Abstract Characterizations 53
In other words,
ηX 0 ◦ (g × 1A ) = g ◦ ηX . (3.120)
−1 −1
Composing by ηX 0 on the left, and ηX on the right, we get
−1 −1
(g × 1A ) ◦ ηX = ηX 0 ◦ g. (3.121)
So (3.118) commutes, and hence α : 1C → 1C is a natural transformation. Therefore, for any arrow
u : X → X, by the naturality of α, the following diagram commutes:
u
X X
−1 −1
αX =p1 ◦ηX αX =p1 ◦ηX
X u X
In other words, for any u : X → X,
−1 −1
p1 ◦ ηX ◦ u = u ◦ p1 ◦ ηX . (3.123)
In order to prove that A is a terminal object, we need to show that there exists a unique arrow
−1
X → A. Clearly, there is an arrow X → A; for instance p2 ◦ ηX : X → A. We now need to show that
the arrow X → A is unique. Let f be any arrow X → A.
X
1X f
h1X ,f i
X p1 X ×A p2 A
f = p2 ◦ h1X , f i = p2 ◦ p−1
1 . (3.126)
53
4 Duality
§4.1 Duality Principle
The Elementary Theory of an Abstract Category (ETAC) consists of certain statements which
involves letters A, B, C, . . . for objects and f, g, h, . . . for arrows. For example, the statement f : A → B
can be phrased as “A is the domain of f , and B is the codomain of f .” A sentence is a statement with
all variables quantified (quantifiers are “for all A”, “for all f ”, “there exists an A”, “there exists an f ”
etc.), and none being free. For example,
For all f , there exists A and B such that f : A → B
is a sentence. Axioms of ETAC are examples of sentences that are true in every category.
To each category C, we also associate the opposite category C op . The objects of C op are the same
as those of C, i.e. given A ∈ Ob (C), one also has A ∈ Ob (C op ).
Ob (C) = Ob (C op ) .
The arrows of C op are arrows f op in the reverse direction, and hence are in 1-1 correspondence
f 7→ f op
with the arrows f of C. In other words, if f : A → B is an arrow in C, then the corresponding arrow
in C op is given by f op : B → A so that
dom (f op ) = cod (f ) and cod (f op ) = dom (f ) .
Now, given arrows
f g
A B C
g◦f
in C, one has
f op g op
A B C
f op ◦g op =(g◦f )op
Now, the dual of any statement Σ of ETAC is formed by making the following replacements through-
out in Σ: “domain” by “codomain”, “codomain” by “domain”, “h is the composite of f with g” by “h
is the composite of g with f ”. As a result, arrows and composites are reversed in the dual statement
Σ∗ . While forming the dual sentence, logic / quantifiers (and, or, for all, there exists etc.) remain
unchanged. Some examples of statements Σ and their dual statements Σ∗ are listed below:
Statement Σ Dual Statement Σ∗
f :A→B f :B→A
A = dom (f ) A = cod (f )
i = 1A i = 1A
h=g◦f h=f ◦g
T is a terminal object T is an initial object
A sentence Σ is true in C op if and only if its dual statement Σ∗ is true in C (arrows in C op are read
without the op prefix).
54
4 Duality 55
Remark 4.1. Note that the dual of the dual is the original statement (Σ∗∗ = Σ). There could be
broadly two types of statements or sentences. A statement can be consequences of the axioms of
ETAC, for example, “a terminal object of a category, if it exists, is unique up to isomorphism.”
The other type of statements do not follow from the axioms of ETAC. For example, “a = dom f ”,
or h = g ◦ f . For the latter type of statements Σ in C, the dual statements Σ∗ refer to opposite
category C op . For the former type of statements, i.e. for the statements that are consequences
of the axioms of ETAC, Σ and its dual Σ∗ refer to the category C. This fact is captured by the
duality principle.
Duality Principle:
If a statement Σ of ETAC is a consequence of the axioms, so is the dual statement Σ∗ .
For example, take Σ to be “a terminal object, if it exists, is unique up to isomorphism.” We have the
dual Σ∗ that reads “an initial object, if it exists, is unique up to isomorphism.” This dual statement
Σ∗ applies to the same category C.
§4.2 Coproducts
q1 q2
Definition 4.1. A diagram A Q B is called a coproduct of A and B if for any
z1 z2
object Z and A Z B , there is a unique arrow u : Q → Z such that the following
diagram commutes:
Z
z1 z2
∃! u
A q1 Q q2 B
i.e. u ◦ q1 = z1 and u ◦ q2 = z2 .
1i 2 i
We usually write A A+B B for the coproduct, and [f, g] for the uniquely determined
arrow [f, g] : A + B → Z as in the following diagram:
Z
f g
[f,g]
A i1
A+B i2
B
55
4 Duality 56
Example 4.1. In Sets, the coproduct A + B of two sets is their disjoint union which can be con-
streucted as
with evident coproduct injections i1 (a) = (a, 1) and i2 (b) = (b, 2). Given any functions f : A → Z
and g : B → Z,
Z
f g
[f,g]
A i1
A+B i2
B
Uniqueness of [f, g] defined in (4.3) follows by noting that if for h : A + B → Z the above diagram
commutes, then one must have h ◦ i1 = f and h ◦ i2 = g. This leads to
Therefore, h (x, δ) = [f, g] (x, δ), for any (x, δ) ∈ A + B. So [f, g] = h proving the uniqueness of [f, g].
Proposition 4.1
Coproducts are unique up to isomorphism.
We don’t need to prove it again. We can just use the fact that products are unique up to isomorphism
(Proposition 3.9), and then invoke duality principle.
Theorem 4.2
Coproducts are associative up to isomorphism, i.e. if A, B, and C are objects in a category with
coproducts, then (A + B) + C ∼= A + (B + C).
Example 4.2. If M (A) and M (B) are free monoids on sets A and B, then in the category Mon, we
can construct their coproduct as
M (A) + M (B) ∼
= M (A + B) .
56
4 Duality 57
In other words, the coproduct of the free monoids on A and B is the free monoid on the coproduct
A + B of A and B in Sets.
We shall prove that M (A + B) satisfies the UMP of coproduct of M (A) and M (B). Let U : Mon →
Sets be the forgetful functor, and let
ηA : A → U (M (A)) ,
ηB : B → U (M (B)) ,
ηA+B : A + B → U (M (A + B))
be the coproduct diagram for A and B. Consider the following diagram in Sets:
U (j1 ) U (j2 )
U(M (A)) U(M (A + B)) U(M (B))
ηA ηA+B ηB
A i1
A+B i2
B
Given the monoid M (A + B) and the function ηA+B ◦ i1 : A → U (M (A + B)), by the UMP of free
monoid on the set A, there is a unique monoid homomorphism j1 : M (A) → M (A + B) such that
Similarly, using the UMP of free monoid on the set B and the function ηA+B ◦i2 : B → U (M (A + B)),
there is a unique monoid homomorphism j2 : M (B) → M (A + B) such that
In other words, the diagram above commutes in Sets. We now claim that
j1 j2
M (A) M (A + B) M (B)
is a coproduct diagram. Let N be any monoid and let f : M (A) → N and g : M (B) → N be monoid
homomorphisms.
U(N )
U (f ) U (g)
ηA ηB
A i1
A+B i2
B
Since A + B is the coproduct of A and B in Sets, there exists a unique h : A + B → U (N ) such that
57
4 Duality 58
U(N )
U (f ) U (g)
U (j1 ) U (j2 )
U(M (A)) U(M (A + B)) U(M (B))
ηA h ηA+B ηB
A i1
A+B i2
B
Now, given the monoid N and the function h : A + B → U (N ), by the UMP of free monoid on the
set A + B, there exists a unique monoid homomorphism h : M (A + B) → N such that
h = U h ◦ ηA+B . (4.11)
ηA+B
h
A+B
So we get the following diagram:
U(N )
U (f ) U (g)
U (h)
U (j1 ) U (j2 )
U(M (A)) U(M (A + B)) U(M (B))
ηA h ηA+B ηB
A i1
A+B i2
B
58
4 Duality 59
In other words, there is a unique monoid homomorphism u : M (A) → N such that the following
diagram commutes:
U (u)
U(M (A)) U(N )
ηA
U (h)◦ηA+B ◦i1
But from (4.12) and (4.13), we get that taking u = f and u = h◦j1 makes the above diagram commute.
Therefore, we must have
f = h ◦ j1 . (4.15)
Similarly,
g = h ◦ j2 . (4.16)
Therefore, given the following diagram commutes:
N
f g
h
M (A) j1
M (A + B) j2
M (B)
Furthermore, we need to show that h is unique. Suppose there exists another monoid homomorphism
v : M (A + B) → N such that f = v ◦ j1 and g = v ◦ j2 . Then using (4.8), we get
59
4 Duality 60
A + B = M (|A| + |B|) / ∼ .
Here, |A| + |B| is the disjoint union of the underlying sets |A| and |B| of the monoids A and B,
respectively. One then forms the free monoid M (|A| + |B|) on the set |A| + |B|, which is the collection
of words over |A| + |B|. Now given two words v, w ∈ M (|A| + |B|), one declares them to be equivalent
as follows:
· · · xuA y · · · ∼ · · · xy · · · ,
· · · xuB y · · · ∼ · · · xy · · · ,
(4.21)
· · · a ·A a0 · · · ∼ · · · aa0 · · · ,
· · · b ·B b0 · · · ∼ · · · bb0 · · · .
One, thus, forms quotient of the free monoid M (|A| + |B|) subjected to the equivalence relation ∼
provided in (4.21). Two equivalence classes [x . . . y] , [x0 . . . y 0 ] ∈ M (|A| + |B|) / ∼ have the straight-
forward multiplication:
[x . . . y] · x0 . . . y 0 = x . . . yx0 . . . y 0 . (4.22)
The unit in M (|A| + |B|) / ∼ is the equivalence class [-] consisting of the empty word. Clearly,
The collection of all the equivalence classes thus formed is defined as the coproduct of A and B:
which can easily be verified to be monoid homomorphism. The UMP of A + B should ensure the
existence of a unique monoid homomorphism [f, g] : A + B → N for a given monoid N and monoid
homomorphisms f : A → N and g : B → N such that the following diagram commutes:
N
f g
[f,g]
A iA
A+B iB
B
Let us now construct [f, g]. From the given monoid homomorphisms f : A → N and g : B → N , one
obtains the functions |f | : |A| → |N | and |g| : |B| → |N |. Now, using the UMP of the coproduct
|A| + |B|, one knows that there exists a unique function h = [|f | , |g|] : |A| + |B| → |N | such that the
following diagram commutes:
|N |
|f | |g|
h
|A| i1
|A| + |B| i2
|B|
where i1 : |A| → |A| + |B| and i2 : |B| → |A| + |B| are coproduct injections of the coproduct |A| + |B|
in Sets. Now, consider the free monoid M (|A| + |B|) on the set |A| + |B|. Invoking the UMP of free
monoid, given the monoid N and the function h : |A| + |B| → |N |, there exists a unique monoid
homomorphism h : M (|A| + |B|) → N such that the following diagram commutes in Sets:
60
4 Duality 61
h
|M (|A| + |B|)| |N |
i
h
|A| + |B|
where i : |A| + |B| → |M (|A| + |B|)| is the insertion of generators. We now need to verify that h
“respects the equivalence relation ∼”, i.e. v ∼ w implies h (v) = h (w).
Given a ∈ A,
h (a) = h (i1 (a)) = f (a) . (4.25)
Since i (a) = a, so
h (a) = h (i (a)) = h (a) = f (a) . (4.26)
Similarly, for b ∈ B,
h (b) = g (b) . (4.27)
So h (uA ) = h (uB ) = uN . As a result,
Similarly,
Since f is a homomorphism,
h · · · a ·A a0 · · · = · · · h a ·A a0 · · · = · · · f a ·A a0 · · ·
= · · · f (a) f a0 · · · = · · · h (a) h a0 · · ·
= h · · · aa0 · · · .
e : M (|A| + |B|) / ∼→
Therefore, v ∼ w implies h (v) = h (w). So we have a monoid homomorphism h
N defined by
e [w] = h (w) .
h (4.28)
This is well-defined since h is constant on the equivalence classes. Therefore, the following diagram
commutes:
π
M (|A| + |B|) M (|A| + |B|)/sim
eh
h
N
e : M (|A| + |B|) / ∼→ N is our desired [f, g]. Indeed,
Now, this h
e ◦ iA (a) = h
h e ([a]) = h (a) = f (a) . (4.29)
e ◦ iB (b) = h
h e ([b]) = h (b) = g (b) . (4.30)
e ◦ iA = f and h
Therefore, h e ◦ iB = g. In other words, the following diagram commutes:
61
4 Duality 62
N
f g
eh
A iA
M (|A| + |B|) / ∼ iB
B
and similarly,
e ([b]) = g (b) = (u ◦ iB ) (b) = u ([b]) ,
h (4.32)
for any a ∈ A and b ∈ B. So u agrees with he on the equivalence classes of elements of A and B. Since
any element of M (|A| + |B|) / ∼ can be written as a finite product of equivalence classes of elements of
A and B, we can conclude that u and he agrees everywhere in M (|A| + |B|) / ∼. Therefore, h e is indeed
e e
the unique arrow in Mon such that h ◦ iA = f and h ◦ iB = g. Therefore, M (|A| + |B|) / ∼= A + B,
and he = [f, g].
Abuse of Notation. In Example 4.3, we did not distinguish between a ∈ |A| and (a, 1) ∈ |A| + |B|;
and between b ∈ B and (b, 2) ∈ |A| + |B|. This can be justified by assuming without loss of generality
that |A| and |B| are disjoint. Indeed, if they are not disjoint, we can just replace them by |A| × {1}
and |B| × {2}.
Example 4.4. Coproduct in groups is called the free product. Suppose A and B are groups. The
free product A ∗ B consists of words of the form
a1 b1 a2 b2 · · · ,
are both words in A ∗ B, but they are unequal highlighting the non-abelian nature of the free product
of A ∗ B, even when A and B are both abelian groups. When A and B are both abelian groups, one
defines their direct sum as the quotient
A ⊕ B = A ∗ B/ ∼,
On the RHS, all the ai ’s are flushed to the left. Now, since A and B are both abelian, so is A ⊕ B:
(a1 + a2 + · · · + an + · · · , b1 + b2 + · · · + bn + · · · ) =≡ (a, b)
62
4 Duality 63
f g
Given any group homomorphisms A −
→X← − B for any abelian group X, we construct [f, g] : A + B →
X as follows:
[f, g] (a, b) = f (a) +X g (b) . (4.35)
Then,
Therefore, [f, g] ◦ iA = f and [f, g] ◦ iB = g. In other words, the following diagram commutes:
X
f g
[f,g]
A iA
A+B iB
B
Furthermore, [f, g] is the unique homomorphism A + B → X such that the diagram above commutes.
If there exists another homomorphism h : A + B → X such that h ◦ iA = f and h ◦ iB = g, then for
any a ∈ A and b ∈ B,
Therefore,
h (a, b) = h (a, 0B ) + h (0A , b) = f (a) + g (b) = [f, g] (a, b) . (4.36)
So [f, g] = h, and hence [f, g] is unique. Therefore, A + B is indeed the coproduct of A and B.
We have just seen that |A + B| = |A × B| for A, B abelian groups. In fact, a stronger result holds
in the category Ab of abelian groups.
Proposition 4.3
In the category Ab of abelian groups, there is a canonical isomorphism between the binary
∼ A × B.
product and coproduct, i.e. A + B =
Proof. The goal is to define an arrow ϑ : A + B → A × B. In order to do so, one needs first an arrow
A → A × B (which is determined by an arrow A → A and an arrow A → B) and another arrow
B → A × B (which is determined by an arrow B → A and an arrow B → B). Therefore, we need 4
arrows altogether, which we choose as follows:
1A : A → A , 0B : A → B , 0A : B → A , 1B : B → B,
where 0B : A → B maps all of A to the identity 0B ∈ B, and 0A : B → A maps all of B to the identity
0A ∈ A.
A B
1A 0B 0A 1B
h1A ,0B i h0A ,1B i
A p1 A×B p2 B A p1 A×B p2 B
A×B
A iA
A+B iB
B
63
4 Duality 64
§4.3 Equalizers
f
Definition 4.2 (Equalizer). In any category C, given parallel arrows A B , an equalizer
g
of f and g consists of an object E and an arrow e : E → A universal such that f ◦ e = g ◦ e, i.e.
the following diagram commutes:
f
e
E A B
g
∃! u z
So (z1 (α) , z2 (α)) = z (α) ∈ S 1 for every α ∈ Z. Therefore, there is a factorization z = i ◦ z through
some z : Z → S 1 . z is nothing but restricting the codomain of z : Z → R to S 1 . Then the following
diagram commutes:
64
4 Duality 65
f
e
S1 R2 R
g
z z
Since the inclusion i is monic, such z : Z → S 1 is unique. Hence, the unit sphere S 1 along with the
inclusion i : S 1 ,→ R2 is indeed the equalizer of f and g in Top.
Example 4.6. Similarly, in Sets, given any functions f, g : A → B, their equalizer is the inclusion of
the following subset
E = {x ∈ A | f (x) = g (x)} (4.41)
into A. Then
f
e
E A B
g
is a commutative diagram. Furthermore, given any set Z and a function z : Z → A such that
f ◦ z = g ◦ z, we have
f (z (α)) = g (z (α)) ,
for any α ∈ Z. So z (α) ∈ E. So we can define a function z : Z → E by just restricting the codomain
of z, then the following diagram commutes:
f
e
E A B
g
z z
Z
Furthermore, z is unique since the inclusion E ,→ A is injective. Therefore, e : E ,→ A is the equalizer
of f and g.
Furthermore, every subset U ⊆ A is of this “equational form”, i.e. every subset is an equalizer for
some pair of functions. Let us undertake this canonical construction. First, let us put
2 = {0, 1} ,
thinking of it as the set of “truth values” (or the 2-element Boolean algebra). Then consider the
characteristic function χU : A → 2 defined by
(
1 if x ∈ U,
χU (x) = (4.42)
0 if x ∈
/ U.
As a result,
U = {x ∈ A | χU (x) = 1} .
We can also define a constant functin > : A → 2 that takes all of A to 1 ∈ 2, i.e.
i >
U A 2
χU
65
4 Duality 66
Now one can easily verify that the inclusion i : Vϕ ,→ A is an equalizer of the parallel arrows
>
A 2 , i.e. one can verify that the following diagram is commutative:
ϕ
i >
Vϕ A 2
ϕ
ϑ (U ) = χU , (4.45)
Example 4.7. Let G and H be two groups with h : G → H being a group homomorphism. The
kernel of h is the subgroup of G defined by
Ker h = {g ∈ G | h (z) = eH } ,
where eH is the identity element of the group H. Then ι : Ker h ,→ G is an equalizer of h and u,
where u : G → H is the trivial group homomorphism, i.e. the homomorphism that maps all of G to
the identity element eH of H.
ι h
Ker h = {g ∈ G | h(g) = eH } G H
u
66
4 Duality 67
ι h
Ker h G H
u
u
a
A
Then for any x ∈ A, h (a (x)) = u (a (x)) = eH , so a (x) ∈ Ker h. So we can define a homomorphism
u : A → Ker h, which is formed by restricting the codomain of a to Ker h. For this u, we have
ι ◦ u = a.
Furthermore, u is unique since the inclusion ι : Ker h → G is monic. Therefore, ι : Ker h → G is an
equalizer of h, u : G → H.
Proposition 4.4
In any category, if e : E → A is an equalizer of some pair of arrows, then e is monic.
x y
z
Z
We want to show that x = y. Put z = e ◦ x = e ◦ y. Then
f ◦ z = f ◦ e ◦ x = g ◦ e ◦ x = g ◦ z. (4.49)
Then from the definition of equalizer, there is a unique arrow u : Z → E such that e ◦ u = z. But
z = e ◦ x = e ◦ y. Therefore, from the uniqueness of u, we have
u = x = y. (4.50)
Therefore, e : E → A is monic. ■
Proposition 4.5
Equalizers are unique up to isomorphism. In other words, if e1 : E1 → A and e2 : E2 → A are
equalizers of parallel arrows f, g : A → B, then there is an isomorphism i : E1 → E2 such that
e1 = e2 ◦ i and e2 = e1 ◦ i−1 .
j e2
E2
In other words,
e1 ◦ j = e2 . (4.51)
Similarly, since E2 is an equalizer, by the UMP of equalizer, there exists a unique arrow i : E1 → E2
such that the following diagram commutes:
67
4 Duality 68
e2 f
E2 A B
g
i e1
E1
In other words,
e2 ◦ i = e1 . (4.52)
We claim that this i : E1 → E2 is our desired isomorphism with inverse j : E2 → E1 . From (4.51) and
(4.52), we get e1 = e2 ◦ i = e1 ◦ j ◦ i. So we have the following commutative diagram:
e1 f
E1 A B
g
j◦i 1E2
e1
E1
Since e1 : E1 → A is an equalizer, and f ◦ e1 = g ◦ e1 , there exists a unique arrow u : E1 → E1 such
that e1 ◦ u = e1 . But the above diagram shows that there are two such arrows E1 → E1 , j ◦ i and 1E1 .
Therefore, by the uniqueness, we must have
j ◦ i = 1E1 . (4.53)
Similarly, again using (4.51) and (4.52), we get e2 = e1 ◦ j = e2 ◦ i ◦ j. So we have the following
commutative diagram:
e2 f
E2 A B
g
i◦j 1E2
e2
E2
Since e2 : E2 → A is an equalizer, and f ◦ e2 = g ◦ e2 , there exists a unique arrow v : E2 → E2 such
that e2 ◦ v = e2 . But the above diagram shows that there are two such arrows E2 → E2 , i ◦ j and 1E2 .
Therefore, by the uniqueness, we must have
i ◦ j = 1E2 . (4.54)
Combining (4.53) and (4.54), we conclude that i : E1 → E2 is an isomorphism and j = i−1 . Further-
more, e1 = e2 ◦ i and e2 = e1 ◦ j = e1 ◦ i−1 . ■
§4.4 Coequalizer
Definition 4.3 (Coequalizer). For any parallel arrows f, g : A → B in a category C, a coequalizer
consists of an object Q and an arrow q : B → Q, universal with the property q ◦ f = q ◦ g as
depicted in the following diagram:
f q
A B Q
g
z ∃! u
68
4 Duality 69
That is, given any object Z and arrow z : B → Z with z ◦ f = z ◦ g, then there exists a unique
u : Q → Z such that u ◦ q = z.
Consider the statement given in Proposition 4.4: “if e : E → A is an equalizer of some pair of arrows,
then e is monic.” This statement follows from the axioms of ETAC, and hence its dual is also a valid
statement in the same category:
Proposition 4.6
In any category, if q : B → Q is a coequalizer of some pair of arrows, then q is epic.
The statement of Proposition 4.5 —equalizers are unique up to isomorphism— also follows from the
axioms of ETAC. So its dual also holds in the same category.
Proposition 4.7
Coqualizers are unique up to isomorphism. In other words, if q1 : B → Q1 and q2 : B → Q2 are
equalizers of parallel arrows f, g : A → B, then there is an isomorphism i : Q1 → Q2 such that
q2 = i ◦ q1 and q1 = i−1 ◦ q2 .
Example 4.8. Let R ⊆ X × X be an equivalence relation on a set X, and consider the diagram
r1
R X
r2
where the ri ’s are the two projections of the inclusion i : R ,→ X × X, i.e. r1 = π1 ◦ i and r2 = π2 ◦ i,
with π1 , π2 : X × X → X are defined as
R
r1 r2
i
X π2 X ×X π1 X
Let X/R be the set of all the equivalence classes of X under the equivalence relation R. The quotient
projection π : X → X/R is defined by x 7→ [x]. Then for (x1 , x2 ) ∈ R, we have
Since (x1 , x2 ) ∈ R, they belong to the same equivalence class, so [x1 ] = [x2 ]. Therefore,
π ◦ r1 = π ◦ r2 . (4.55)
f
f
Z
f ◦ r1 = f ◦ r2 means that for any (x1 , x2 ) ∈ R,
(f ◦ r1 ) (x1 , x2 ) = (f ◦ r2 ) (x1 , x2 )
=⇒ f (r1 (x1 , x2 )) = f (r2 (x1 , x2 ))
=⇒ f (x1 ) = f (x2 ) . (4.56)
69
4 Duality 70
In other words, f “respects the equivalence relation R” in the sense that f is constant on the equivalence
classes. So we can define a function f : X/R → Z by
This is well-defined since f is constant on the equivalence classes. Therefore, we have f (π (x)) = f (x),
i.e.
f ◦ π = f. (4.58)
Furthermore, f is unique since π is surjective.
r1 π
R X X/R
r2
∃! f
f
Example 4.9. Let α, β : A → B be two parallel arrows in Sets. Let R be the minimal equivalence
relation on B containing all the elements of the form (α (a) , β (a)) for all a ∈ A. In other words,
R is the intersection of all the equivalence relations on B containing all the elements of the form
(α (a) , β (a)).
\
R= {E | E ⊆ B × B is an equivalence relation, and (α (a) , β (a)) ∈ E for all a ∈ A} .
Then we form the set of equivalence classes of B under this equivalence relation R. The set of
equivalence classes is B/R. Then we claim that the coequalizer of α, β : A → B is
γ : B → B/R,
the canonical quotient map that takes each b ∈ B to its equivalence class [b] ∈ B/R.
α γ
A B B/R
β
ϕ ψ
Indeed, γ ◦ α = γ ◦ β, since for each a ∈ A, we have (α (a) , β (a)) ∈ R. Therefore, [α (a)] = [β (a)]. In
other words,
(γ ◦ α) (a) = (γ ◦ β) (a) ,
for each a ∈ A. Therefore,
γ ◦ α = γ ◦ β. (4.59)
Now, suppose there is another arrow ϕ : B → C satisfying ϕ◦α = ϕ◦β. We define another equivalence
relation R0 on B as follows:
(b1 , b2 ) ∈ R0 ⇐⇒ ϕ (b1 ) = ϕ (b2 ) . (4.60)
Then for each a ∈ A, we have
70
4 Duality 71
Therefore, (α (a) , β (a)) ∈ R0 for each a ∈ A. Then by the minimality of R, we must have R ⊆ R0 . In
other words, if (b1 , b2 ) ∈ R, or equivalently [b1 ] = [b2 ] in B/R, then ϕ (b1 ) = ϕ (b2 ). So we can define
a well-defined function ψ : B/R → C by
Then we have
ϕ (b) = ψ (γ (b)) = (ψ ◦ γ) (b) ,
for each b ∈ B. Therefore,
ϕ = ψ ◦ γ.
Furthermore, this ψ is unique. Indeed, if there exists another ψ 0 : B/R → C satisfying ϕ = ψ 0 ◦ γ,
then we must have
ϕ (b) = ψ 0 ◦ γ (b) = ψ 0 (γ (b)) = ψ 0 ([b]) ,
for each b ∈ B. Therefore, ψ 0 = ψ, so ψ : B/R → C is unique. Hence, γ : B → B/R is a coequalizer
of α, β : A → B in Sets.
Example 4.10. Let f, g : X → Y be given arrows in Top. Then f, g : X → Y are continuous maps
between the topological spaces X and Y , whose underlying sets are |X| and |Y |, respectively. Then
|f | , |g| : |X| → |Y | are parallel arrows in Sets. As above, we can form the coequalizer of |f | and |g|
in Sets. Let |q| : |Y | → |Q| be the coequalizer of |f | and |g| in Sets. Then we topologize the set |Q|
as follows:
V ⊆ |Q| is open ⇐⇒ |q|−1 (V ) ⊆ |Y | is open. (4.62)
Let us verify that this indeed forms a topology:
Since U1 , U2 are open, |q|−1 (U1 ) , |q|−1 (U2 ) are also open in Y . Therefore, as an intersection of
finitely many open sets, |q|−1 (U1 ∩ U2 ) is also open in Y . Hence, U1 ∩ U2 is open in |Q|.
Let Q be the topological space whose underlying set is |Q|, and the topology is defined as in (4.62).
Then the function q : Y → Q is continuous, since the preimage of every open set in Q is also open in
Y . We claim that q : Y → Q is a coequalizer of f, g : X → Y .
f q
X Y Q
g
z u
71
4 Duality 72
Now suppose there is another continuous map z : Y → Z such that z ◦f = z ◦g. Then |z|◦|f | = |z|◦|g|
in Sets. Since |q| is a coequalizer of |f | , |g| : |X| → |Y |, there is a unique function |u| : |Q| → |Z|
such that |u| ◦ |q| = |z|. Now we need to show that |u| defines a continuous map u : Q → Z. Let
U ⊆ |Z| be open. We need to show that |u|−1 (U ) is open in Q.
|q|−1 |u|−1 (U ) = |z|−1 (U ) . (4.66)
Then |z|−1 (U ) is open in Y since z is continuous. Therefore, |q|−1 |u|−1 (U ) is open in Y . Then by
(4.62), |u|−1 (U ) is open in Q. Hence, u is open.
Therefore, there exists a unique continuous map u : Q → Z such that u ◦ q = z. So q : Y → Q is
indeed a coequalizer of f, g : X → Y in Top.
A1 A2 A3 ∃! u ··· An
x2
x3
x1 xn
X
In other words, there exists a unique u : X → P such that each of the following triangles commute:
πi
Ai P
u
xi
X
If such an object P exists, it is unique up to isomorphism. So we write the product of A1 , . . . , An as
A1 × · · · × An .
If the category admits binary products, then it also admits any finite product. One can easily show
that
(. . . ((A1 × A2 ) × A3 ) × . . .) × An
satisfies the UMP of the product A1 × · · · × An .
In the similar spirit, we can actually define the product of an arbitrary family of objects. Let
(Aα )α∈I be a collection of objects indexed by the index set I. An object P with arrows πα : P → Aα
for α ∈ I is called a product of (Aα )α∈I if the following UMP is satisfied: given any object X and
arrows xα : X → Aα for α ∈ I, there exists a unique arrow u : X → P such that xα = πα ◦ u for
all α ∈ I. In other words, there exists a unique u : X → P such that each of the following triangles
commute, for each α ∈ I:
72
4 Duality 73
πα
Aα P
u
xα
If such an object P exists, it is unique up to isomorphism. So we write the product of (Aα )α∈I as
Y
Aα .
α∈I
Now, this index set I can be any set, even the empty set. If I = ∅, we call the product an empty
product. The empty product is actually the terminal object of the category. The terminal object
1 satisfies the UMP of the product of and I-indexed family of objects, when I = ∅. The UMP of
product is:
When I is the empty set, there aren’t any objects, and hence there aren’t any projection arrows πα .
So the UMP becomes:
Given any object X and arrows xα : X → Aα (there are no Aα ’s, so this is satisfied
vacuously), there exists a unique arrow u : X → P such that xα = πα ◦ u (there are no
xα ’s, so this commutativity is also satisfied vacuously) for all α ∈ I.
This is precisely the definition of the terminal object. Therefore, the product of an empty collection
of objects is the terminal object of the category. It is also called the nullary product.
We can reverse the arrows in the above definitions, and form the coproduct of a finite, or arbitrary,
or even empty collection of objects. Given objects A1 , A2 , A3 , . . . , An , an object P with arrows ij :
Aj → Q for j = 1, 2, . . . , n is called a coproduct of A1 , A2 , A3 , . . . , An if the following UMP is satisfied:
given any object X and arrows xj : Aj → X for j = 1, 2, . . . , n, there exists a unique arrow u : Q → X
such that u ◦ ij = xj for all j = 1, 2, . . . , n.
Q
i1 in
i3
i2
A1 A2 A3 u ··· An
x1 x2
x3
xn
X
In other words, there exists a unique u : X → P such that each of the following triangles commute:
ij
Aj P
u
xj
73
4 Duality 74
A1 + A2 + · · · + An .
If the category admits binary coproducts, then it also admits any finite product. One can easily show
that
(. . . ((A1 + A2 ) + A3 ) + · · · + . . .) + An
satisfies the UMP of the coproduct A1 + · · · + An .
In the similar spirit, we can actually define the coproduct of an arbitrary family of objects. Let
(Aα )α∈I be a collection of objects indexed by the index set I. An object Q with arrows iα : Aα → Q
for α ∈ I is called a coproduct of (Aα )α∈I if the following UMP is satisfied: given any object X and
arrows xα : Aα → X for α ∈ I, there exists a unique arrow u : Q → X such that xα = u ◦ πα for
all α ∈ I. In other words, there exists a unique u : P → X such that each of the following triangles
commute, for each α ∈ I:
iα
Aα P
u
xα
If such an object P exists, it is unique up to isomorphism. So we write the product of (Aα )α∈I as
a
Aα .
α∈I
Now, this index set I can be any set, even the empty set. If I = ∅, we call the coproduct an empty
coproduct. By duality principle, the empty coproduct is the initial object.
74
5 Groups and Categories
§5.1 Groups in a Category
A group arises as ab abstraction of the automorphisms of an object. Recall the definition of a concrete
category where the objects are some “structured” sets, and the arrows are “structure preserving” maps.
In a specific and concrete case, a group G may thus consist of certain arrows for a given object X in
a category C:
G ⊆ HomC (X, X) .
One requires all these arrows to be isomorphisms. But the abstract group concept can also be described
directly as an object in a category, equipped with a certain structure.
Definition 5.1. Let C be a category admitting binary products and a final object 1. A group in
C consists of objects and arrows as given below
m i
G×G G G
1
satisfying the following conditions:
I
(G × G) × G ∼
=
G × (G × G)
m×1G 1G ×m
m m
hu!,1G i
G G×G
1G (5.3)
h1G ,u!i m
G×G m G
75
5 Groups and Categories 76
So
m ◦ hu!, 1G i = 1G = m ◦ h1G , u!i . (5.4)
3. i : G → G is an inverse with respect to m, i.e. the both squares of the following diagram
commute:
h1G ,1G i h1G ,1G i
G×G G G×G
1G ×i u! i×1G (5.5)
G×G m G m G×G
In other words,
These commutative diagrams don’t seem to manifest the usual group axioms (associativity, unit ele-
ment, inverse), but they actually do! Let us see them in action.
1. Associativity: When G is a (structured) set and x, y, z are arbitrary elements of the underlying
set, then the commutativity of (5.1) yields:
which is precisely the associativity equation of the binary operation ∗ (here we have written
m (a, b) = a ∗ b).
2. Unit element: When G is a (structured) set, the terminal object 1 is a singleton set. So
! u
u! : G −
→1−
→ G is a constant function. Let e = u! (x). Then the commutativity of (5.3) yields:
This suggests that when G is a (structured) set, the element e = u! (x) is the unit of the binary
operation ∗.
Since e = u! (x) is the identity of the binary operation ∗, this equation suggests that i (x) is the
inverse element of x.
76
5 Groups and Categories 77
h×h
G×G H ×H
mG mH (5.7)
G h
H
In other words,
h ◦ mG = mH ◦ (h × h) . (5.8)
h
G H
uG (5.9)
uH
In other words,
h ◦ uG = uH . (5.10)
h
G H
iG iH (5.11)
G h
H
In other words,
h ◦ iG = iH ◦ h. (5.12)
This definition of homomorphism complies with the usual definition of homomorphism we see while
studying group theory. Suppose G and H are now (structured) sets, and take any x, y ∈ G. Commu-
tativity of (5.7) implies
When G and H are (structured) sets, the terminal object 1 is a singleton set {∗}. Commutativity of
(5.9) gives us
(h ◦ uG ) (∗) = uH (∗)
=⇒ h (eG ) = eH ,
77
5 Groups and Categories 78
With the evident identities u, inverses i and multiplications m we thus have a category of groups
in C, denoted by
Group (C) .
With this construction,
• A Lie group is a group in the category Man of smooth manifolds and smooth maps.
Example 5.1. In this example, we focus on Group (Groups). So it refers to the diagram
m i
G×G G G
1
in the category of groups subjected to the properties mentioned earlier. The terminal object 1 ∈
Ob (Groups) is the trivial group consisting of the identity element only. Here, G itself is a group. Let
us denote the group operation on G by ◦G . ◦G induces ◦G×G on G × G in the following way:
Write 1◦ for the unit of G with respect to ◦G , and 1? for the unit of G wirh respect to ?, i.e.
g ◦G 1◦ = g = 1◦ ◦G g and g ? 1? = g = 1? ? g. (5.15)
1. 1◦ = 1? ,
2. ◦ = ?,
78
5 Groups and Categories 79
Therefore, · is commutative. ■
Corollary 5.2
The groups in the category Groups are exactly the abelian groups.
Proof. In Proposition 5.1, we have shown that a group in the category Groups of groups is abelian.
In other words, Group (Groups) is a subcategory of Ab. One now has to prove the converse, i.e. any
abelian group G admits homomorphic group multiplication m : G × G → G and homomorphic inverse
i : G → G. In other words, for any g, h ∈ G × G and x, y ∈ G,
Therefore, m and i are group homomorphisms, i.e. arrows in Groups. So any abelian group G is a
group in the category Groups. Hence, Group (Groups) = Ab. ■
T (A, B) = C.
79
5 Groups and Categories 80
α0 β β0
→ A0 −→ A00 in C and B −
α
2. If A − → B 0 −→ B 00 in D, then in the product category C × D, we have
(α,β) (α0 ,β 0 )
(A, B) (A0 , B 0 ) (A00 , B 00 )
Example 5.2. Hom (−, −) : C op × C → Sets is an example of a bifuntor. Suppose A and B are
objects of C, and hence objects of C op . Then this functor takes (A, B) to HomC (A, B), i.e.
for ϕ ∈ Hom (A, B). Let us now verify that the definition in (5.21) satisfies both (5.18) and (5.19).
Hom (1op
A , 1B ) (ϕ) = 1B ◦ϕ ◦ 1A = ϕ,
Hom (1op
A , 1B ) = 1HomC (A,B) . (5.22)
αop αop β1 β2
So (5.18) is satisfied. Now, let A −−1→ A0 −−2→ A00 be arrows in C op and B −→ B 0 −→ B 00 be arrows in
C.
C op × C
(αop
1 ,β1 ) (αop
2 ,β2 )
(A, B) (A0 , B 0 ) (A00 , B 00 )
(αop op op op
2 ,β2 )◦(α1 ,β1 )=(α2 ◦α1 ,β2 ◦β1 )
Hom(−, −)
Sets
Hom(αop
1 ,β1 ) Hom(αop
2 ,β2 )
HomC (A, B) HomC (A0 , B 0 ) HomC (A00 , B 00 )
Hom(αop op
2 ◦α1 ,β2 ◦β1 )
Now we need to verify equation (5.19) for the functor Hom (−, −) : C op × C → Sets which entails the
commutativity of the diagram in Sets given above.
80
5 Groups and Categories 81
Therefore,
Hom(α2op ◦ α1op , β2 ◦ β1 ) = Hom(α2op , β2 ) ◦ Hom(α1op , β1 ). (5.23)
Therefore, Hom (−, −) : C op × C → Sets is indeed a bifunctor.
B×B×B α B
□◦(1B ×□)◦I 0
f g
→ a0 , b −
→ b0 , c −
→ c0 in B, the following diagram commutes:
h
That is, given arrows a −
(f □g)□h
(a□b)□c (a0 □b0 )□c0
f □(g□h)
a□(b□c) a0 □(b0 □c0 )
Furthermore, the components αa,b,c : (a□b)□c → a□(b□c) are all isomorphisms.
• The bifunctor □ : B × B → B induces a functor in the second component by keeping the first
component e, i.e. □ (e, −) : B → B is a functor. λ : □ (e, −) ⇒ 1B is a natural isomorphism.
□(e,−)
B λ B
1B
f
That is, given an arrow a −
→ b in B, the following diagram commutes:
1e □f
e□a e□b
λa λb
a f
b
B ρ B
1B
81
5 Groups and Categories 82
f
That is, given an arrow a −
→ b in B, the following diagram commutes:
f □ 1e
a□e b□e
ρa ρb
a f
b
((a□b)□c) □d a□ (b□(c□d))
αa,b,c □ 1d 1a □αb,c,d
1a □λc
ρa □ 1 c
a□c
• λe = ρe .
B = hB, □, ei is called a strict monoidal category when all 3 natural isomorphisms α, λ, ρ are identity
natural transformation. For example, any category with finite products can be regarded as a monoidal
category with the product as the monoidal product and the terminal object as the unit.
ι h
Ker h = {g ∈ G | h(g) = eH } G H
uH !
i.e. uH ! = uH ◦!, and eH is the identity element of H. Also, ι : Ker h → G is the inclusion. We have
seen in Example 4.7 that this specification makes ι : Ker h → G an equalizer of h and uH !.
Observe that Ker h is a normal subgroup of G. Now, if N ⊆ G is a normal subgroup of G, then the
inclusion i : N ,→ G is a monomorphism. We can now construct the coequalizer
i π
N G G/N
uG !
82
5 Groups and Categories 83
f f
H
then f (n) = eH for each n ∈ N . Then there is a unique homomorphism f : G/N → H such that
f ◦ π = f , i.e. the triangle in the diagram above commutes. f is defined as follows:
f ([g]) = f (gN ) = f (g) . (5.24)
To check the well-definedness of f , consider g, h ∈ G such that [g] = [h]. Then gN = hN , so h−1 g ∈ N .
Therefore,
f (g) = f h ·G h−1 g = f (h) f h−1 g = f (h) ·H eH = f (h) .
So f ([g]) = f ([h]), and hence f is well-defined. The uniqueness of f follows from the fact that π is
0 0
an epimorphism. Indeed, if there is another arrow f : G/N → H such that f ◦ π = f , then we have
the following commutative diagram.
π
G G/N
0
f f f
H
0 0
Then f ◦ π = f ◦ π. Since π is an epi, f = f , so f is unique.
Theorem 5.3
Every group homomorphism h : G → H has a kernel Ker h = h−1 (uH ) (eH is the unit element of
H), which is a normal subgroup of G, with the property that for any normal subgroup N ⊆ G,
N ⊆ Ker h ⇐⇒ ∃! h : G/N → H
π
h
G/N
h h
83
5 Groups and Categories 84
Therefore,
h ◦ i = h ◦ uG !. (5.25)
We have seen earlier that π : G → G/N is a coequalizer of the parallel arrows i, uG ! : N → G. Hence,
there is a unique homomorphism h : G/N → H such that h ◦ π = h.
(⇐) Conversely, suppose there is a unique homomorphism h : G/N → H such that h ◦ π = h. Then
for any n ∈ N ,
h (n) = h (π (n)) = h ([n]) = h ([eG ]) = eH . (5.26)
Therefore, n ∈ Ker h, proving that N ⊆ Ker h. ■
Corollary 5.4
Every group homomorphism h : G → H factors as a quotient followed by an injective homomor-
phism:
h
G H
π
h
G/ Ker h
∼
=
In other words, h = h◦π, where h is injective. Thus h : G/ Ker h −
→ im (h) ⊆ H is an isomorphism
to the subgroup im (h).
Proof. Let us take N = Ker h in Theorem 5.3. Then there exists a unique homomorphism h :
G/ Ker h → H such that h ◦ π = h. So, the following diagram commutes:
h
G H
π
h
G/ Ker h
Now we need to show that h is injective. Choose [x] , [y] ∈ G/ Ker h such that h [x] = h [y]. Then we
have
84
5 Groups and Categories 85
Remark 5.1. We can also rephrase the definition of congruence as follows: a congruence is a
collection of equivalence relations RX,Y for X, Y ∈ Ob (C) such that
1. RX,Y ⊆ HomC (X, Y )×HomC (X, Y ) is an equivalence relation (i.e. it’s reflexive, symmetric,
transitive)
(b ◦ f ◦ a, b ◦ g ◦ a) ∈ Rdom(a),cod(b) (5.27)
Such equivalence relations clearly exist, as we can just take RX,Y = HomC (X, Y ) × HomC (X, Y ).
But such equivalence relations are not unique. So any equivalence relations RX,Y on HomC (X, Y )
satisfying (5.27) will be called a congruence.
Definition 5.5 (Congruence Category). Let ∼ be a congruence on the category C, and define the
congruence category C ∼ by
Ob (C ∼ ) = Ob (C) ,
HomC ∼ (X, Y ) = {(f, g) | f, g ∈ HomC (X, Y ) and f ∼ g} ,
e X = (1X , 1X ) ,
1
0
f 0 , g ◦ (f, g) = f 0 ◦ f, g 0 ◦ g .
Note that, in this definition, HomC ∼ (X, Y ) is nothing but the RX,Y mentioned in Remark 5.1. We
need to check the well-definedness of the definition of composition.
85
5 Groups and Categories 86
Let (f, g) ∈ HomC ∼ (X, Y ) and (f 0 , g 0 ) ∈ HomC ∼ (Y, Z). We need to show that (f 0 ◦ f, g 0 ◦ g) ∈
HomC ∼ (X, Z), i.e. f 0 ◦ f ∼ g 0 ◦ g.
1X f f0 1Z
X X Y Z Z
g g0
They leave the objects unchanged, i.e. pi (X) = X for X ∈ Ob (C ∼ ) = Ob (C), i = 1, 2, and
p1 (f, g) = f and p2 (f, g) = g. (5.29)
Clearly, for i = 1, 2,
e X = pi (1X , 1X ) = 1X .
pi 1 (5.30)
Furthermore,
p1 f 0 , g 0 ◦ (f, g) = p1 f 0 ◦ f, g 0 ◦ g
= f0 ◦ f
= p1 f 0 , g 0 ◦ p1 (f, g) . (5.31)
0 0 0 0
p2 f , g ◦ (f, g) = p2 f ◦ f, g ◦ g
= g0 ◦ g
= p2 f 0 , g 0 ◦ p2 (f, g) . (5.32)
Therefore, p1 and p2 are indeed functors. We now build the quotient category C/ ∼ as follows:
Ob (C/ ∼) = Ob (C)
HomC/∼ (X, Y ) = HomC (X, Y ) / ∼ .
The arrows of C/ ∼ have the form [f ], where f is an arrow in C, and we put
[1X ] = 1[X] , (5.33)
for X ∈ Ob (C), where the equivalence class [X] consists of X only. Furthermore,
[g] ◦ [f ] = [g ◦ f ] , (5.34)
for cod (f ) = dom (g) in C. We need to verify the well-definedness of this definition. Suppose [f ] = [f 0 ]
and [g] = [g 0 ]. Then f ∼ f 0 and g ∼ g 0 . Therefore, using (5.28), we get g ◦ f ∼ g 0 ◦ f 0 . So
[g ◦ f ] = [g 0 ◦ f 0 ] and the composition in C/ ∼ is well-defined.
Consider the quotient functor π : C → C/ ∼ by
π (X) = [X] and π (f ) = [f ] , (5.35)
for objects X and arrows f . Then the following is a coequalizer diagram in Cat:
86
5 Groups and Categories 87
p1
C∼ C π
C/ ∼
p2
The arrows p1 , p2 , π do not change the objects. So π ◦ p1 = π ◦ p2 clearly holds on objects. Let (f, g)
be an arrow in C ∼ . Then f ∼ g, so that [f ] = [g]. Now,
(π ◦ p1 ) (f, g) = π (f ) = [f ] ,
(π ◦ p2 ) (f, g) = π (g) = [g] .
π ◦ p1 = π ◦ p2 . (5.36)
F
(5.37)
F
Now we define the functor F : C/ ∼→ D as follows: given any object [X] ∈ Ob (C/ ∼), we define
F ([f ]) = F (f ) . (5.40)
Therefore, we have
F ◦ π = F. (5.41)
Therefore, there exists a functor F : C/ ∼→ D such that the triangle of (5.37) commutes. Now we
need to show the uniqueness of F . Suppose there is another functor G : C/ ∼→ D such that G ◦ π = F .
Given any object [X] ∈ Ob (C/ ∼),
87
5 Groups and Categories 88
Let us now see how we can use the notion of coequalizer to prove analogous homomorphism theorems
for categories. Suppose one has categories C and D and a functor F : C → D. Then F defines a
congruence ∼F on C by setting
Suppose f ∼F g with dom(f ) = dom(g) = X and cod(f ) = cod(g) = Y . Then for any arrow
a : A → X and b : Y → B,
The functors p1 , p2 : C ∼F → C are defined as (5.29). One then obtains the quotient category as the
coequalizer
p1
Ker F = C ∼F C π
C/ ∼F
p2
where π is defined as (5.35). The quotient category C/ ∼F then has the following UMP.
Theorem 5.5
Every functor F : C → D has a kernel category Ker F = C ∼F , determined by a congruence ∼F
on C such that given any congruence ∼ on C, one has
f ∼ g =⇒ f ∼F g
π
e
F
C/ ∼
In other words, F = Fe ◦ π.
F e
F
D
Given an arrow (f, g) in C ∼ , we have f ∼ g. So
88
5 Groups and Categories 89
[f ] = [g] =⇒ π (f ) = π (g)
=⇒ Fe (π (f )) = Fe (π (g))
=⇒ F (f ) = F (g) . (5.46)
Therefore, f ∼F g. ■
Corollary 5.6
Every functor F : C → D factors as F = Fe ◦ π, where π is bijective on objects and surjective on
Hom-sets (i.e. π is a full functor), and Fe is injective on Hom-sets (i.e. Fe is a faithful functor):
F
C D
π
e
F
C/ ∼F
Proof. Let us take ∼ = ∼F in Theorem 5.5. Then there exists a unique functor Fe : C/ ∼→ D such
thatF = Fe ◦ π. So, the following diagram commutes:
F
C D
π
e
F
C/ ∼F
Now, clearly π is bijective on objects since the objects of C/ ∼F are equivalence classes [X] containing
only X ∈ Ob (C). Furthermore, π is surjective on Hom-sets, since given any [f ] ∈ HomC/∼F (X, Y ),
[f ] = π (f ). We are only left to show that Fe is injective on Hom-sets.
Take [f ] , [g] ∈ HomC/∼F (A, B) such that Fe ([f ]) = Fe ([g]). Then we have
Fe ([f ]) = Fe (π (f )) = F (f ) .
89
6 Subobjects and Pullbacks
§6.1 Subobjects
Every subset U ⊆ X of a set X occurs as equalizer, and the equalizers are always monomorphisms.
i >
U X 2,
χU
Since every subset U ⊆ X occurs as equalizer and equalizers are monic, it is natural to treat monos
as generalized subsets. For instance, monos in Groups can be regarded as subgroups, and monos in
Top can be regarded as subspaces. Given a monomorphism m : M ↣ X in a category G of structured
sets of some sort (call it “gadget”), the image subset
{m (y) | y ∈ M } = m (M ) ⊆ X
More generally, we can think of the mono m : M ↣ X itself as determining a “part” of X, even in
categories where the arrows are not necessarily functions.
m : M ↣ X.
m m0
Thus we have the category SubC (X) of subobjects of X in C. The objects of SubC (X) are monomor-
phisms of C with codomain X. The objects of C/X are, on the other hand, all arrows of C with
codomain X.
In the construction of SubC (X), since m0 is monic, given the following commutative diagram,
f
M M0
m m0
90
6 Subobjects and Pullbacks 91
there is at most one f : M → M 0 . In other words, there is at most one element in the hom-set
HomSubC (X) (m, m0 ). Indeed, if there are f, f 0 : m → m0 in SubC (X), f, f 0 : M → M 0 are arrows in C
such that m0 ◦ f = m0 ◦ f 0 = m.
f
M M0
f0
m m0
Finally, we say that m and m0 are equivalent, written m ≡ m0 if and only if they are isomorphic as
subobjects, i.e. m ⊆ m0 and m0 ⊆ m. This holds if and only if f and f 0 making both triangles below
commute:
f
M M0
f0
m m0
X
In other words,
m0 ◦ f = m and m ◦ f 0 = m0 . (6.2)
Using (6.2), we get
m ◦ 1M = m = m0 ◦ f = m ◦ f 0 ◦ f. (6.3)
So m ◦ 1M = m ◦ (f 0 ◦ f ).
f 0 ◦f
m
M M X
1M
Since m is a monomorphism,
f 0 ◦ f = 1M . (6.4)
Similarly,
f ◦ f 0 = 1M 0 . (6.5)
Hence, M ∼= M 0 via f . Thus, we can see that equivalent subobjects (m ≡ m0 ) have isomorphic
domains (M ∼
= M 0 ).
Abuse of Notation. We sometimes abuse notation and language by calling M the subobject when
the monomorphism m : M ↣ X is clear.
It is often convenient to pass from the preorder SubC (X) to the poset SubC (X) / ≡ by factoring out
the equivalence relation ≡. Notice that two distinct monos m and m0 in SubC (X) can be equivalent,
i.e. m ≡ m0 so that both m ⊆ m0 and m0 ⊆ m hold with m and m0 being distinct. That’s why
SubC (X) is just a preorder category and not a poset category. As soon as we construct SubC (X) / ≡,
distinct m and m0 in SubC (X) with m ≡ m0 coincide, i.e. in SubC (X), [m] = [m0 ].
Now, in SubC (X) / ≡, for distinct equivalence classes [m] 6= [m0 ] one will have either [m] ⊆ [m0 ]
or [m0 ] ⊆ [m] (or neither) and noth both. Hence. ⊆ is antisymmetric in SubC (X) / ≡ so that
SubC (X) / ≡ is a poset category with respect to the inclusion ⊆.
91
6 Subobjects and Pullbacks 92
Proposition 6.1
In Sets, under this notion of subobject, one then has the isomorphism
SubSets (X) /≡ ∼
= P (X) .
Proof. Let X be a set. If X = ∅, then there is only one mono m : A → ∅, which is the empty function
m : ∅ → ∅. So SubSets (X) has cardinality 1, and hence is isomorphic to P (∅) = {∅}. Now suppose
X 6= ∅.
We define a function ϕ : SubSets (X) /≡ → P (X) as follows: given a subobject m : M ↣ X, we
define
ϕ ([m]) = im m = m (M ) ⊆ X. (6.6)
Let us check that ϕ is well-defined. Suppose m : M ↣ X and m0 : M 0 ↣ X are subobjects such that
[m] = [m0 ]. Then m ≡ m0 . In other words, there is an isomorphism f : M → M 0 such that m = m0 ◦ f ,
i.e. the following diagram commutes
f
M ∼
=
M0
m m0
X
Since f is an isomorphism, f (M ) = M 0 . So we have
im m = m (M ) = m0 (f (M )) = m0 M 0 = im m0 . (6.7)
Therefore,
ϕ ([m]) = im m = im m0 = ϕ m0 , (6.8)
so that ϕ is well-defined. Now we define another function ψ : P (X) → SubSets (X) / ≡ as follows:
given U ⊆ X, let iU : U ,→ X be the inclusion (which is injective, and hence a mono). Then we define
ψ (U ) = [iU ] . (6.9)
iim M
m
X
This diagram commutes. Therefore, m ≡ iim M , i.e. [m] = [iim m ]. Now,
Therefore,
ψ ◦ ϕ = 1SubSets (X)/≡ . (6.11)
Combining (6.10) and (6.11), we get that ϕ : SubSets (X) /≡ → P (X) is an isomorphism, with inverse
ψ : P (X) → SubSets (X) /≡. ■
92
6 Subobjects and Pullbacks 93
Suppose m, m0 are subobjects of X ∈ Ob (C), i.e. m : M ↣ X and m0 : M 0 ↣ X are monic. Also, let
f : m → m0 be an arrow in SubC (X). Then the following diagram commutes:
f
M M0
m m0
X
By Proposition 3.5, since m is monic, so is f . Hence, f ∈ SubC (M 0 ).
Given a monic arrow m : M ↣ X in C, one can construct a functor called composition functor
m∗ : SubC (M ) → SubC (X) by
m∗ (f ) = m ◦ f, (6.12)
at the level of objects; and at the level of arrows, m∗ is defined trivially:
m∗ (a) = a, (6.13)
as can be seen by looking at the following commutative diagram.
a
N P
f g
M
m∗ (f )=m◦f m∗ (g)=m◦g
m
X
If f : N ↣ M is monic, then m◦f : N → X is also monic by Proposition 3.5. Similarly, m◦g : P → X
is a monomorphism. Now, a : f → g is an arrow in SubC (M ), i.e. a : N → P is an arrow in C such
that f = g ◦ a. m∗ (a) is supposed to be an arrow from m∗ (f ) = m ◦ f to m∗ (g) = m ◦ g, i.e.
m∗ (a) : N → P is an arrow in C such that
m ◦ f = m ◦ g ◦ m∗ (a) .
Choosing m∗ (a) = a clearly satisfies our requirement, since f = g ◦ a.
§6.2 Pullback
Definition 6.2 (Pullback). In any category C, given arrows f, g with cod f = cod g,
A f
C
p1
A
such that f ◦ p1 = g ◦ p2 with a certain universal property.
93
6 Subobjects and Pullbacks 94
p2
P B
p1 g
A f
C
Z z2
p2
P B
z1
p1 g
A f
C
Z z2
(z1 ,z2 )
p2
A ×C B B
z1
p1 g
A f
C
Pullbacks are clearly unique up to isomorphism as they are given by a universal mapping property.
1X f (6.14)
X f
Y
Z z2
1X
X X
z1
1X f
X f
Y
94
6 Subobjects and Pullbacks 95
z = z1 = 1X ◦z 0 = z 0 . (6.15)
Example 6.2. If e : X → Y is a split epi with right inverse s : Y → X, i.e. e ◦ s = 1Y , and e is not
an isomorphism, then the following is not a pullback diagram:
1Y
Y Y
s 1Y (6.16)
X e Y
If it were a pullback diagram, then for any object Z with arrows z1 : Z → X and z2 : Z → Y such
that e ◦ z1 = 1Y ◦z2 , there would’ve existed a unique z : Z → Y such that s ◦ z = z1 and 1Y ◦z = z2 .
Z z2
1Y
Y Y
z1
s 1Y
X e Y
X e
1Y
Y Y
1X
s 1Y
X e Y
In other words,
s ◦ z = z1 = 1X and 1Y ◦z = e. (6.17)
The second equation 1Y ◦z = e gives us that z = e. Plugging it into the first equation, we get
s ◦ e = 1X . (6.18)
This clearly violates the hypothesis that e is not an isomorphism. Therefore, (6.16) is not a pullback
diagram.
Proposition 6.2
In a category with products and equalizers, given a corner of arrows
95
6 Subobjects and Pullbacks 96
A f
C
p1 A×B g
π1
A f
C
p1
A
satisfies the universal mapping property of pullback. In other words, we need to show that f ◦p1 = g◦p2
holds, and given any object Z and arrows z1 : Z → A and z2 : Z → B satisfying f ◦ z1 = g ◦ z2 , there
exists a unique u : Z → E such that p1 ◦ u = z1 and p2 ◦ u = z2 .
z2
Z
∃! u hz1 ,z2 i
p2
E B
e
π2
z1
p1 A×B g
π1
A f
C
f ◦ π1 ◦ e = g ◦ π2 ◦ e. (6.19)
96
6 Subobjects and Pullbacks 97
f ◦ p1 = g ◦ p2 . (6.20)
π π z z
Since A ←− 1
A × B −→2
B is a product diagram, for A ←−
1
A × B −→
2
B, there exists a unique
hz1 , z2 i : Z → A × B such that
u
hz1 ,z2 i
Z
By the UMP of equalizer, there is a unique u : Z → E such that
e ◦ u = hz1 , z2 i . (6.23)
Now,
p1 ◦ u = π1 ◦ e ◦ u = π1 ◦ hz1 , z2 i = z1 , (6.24)
p2 ◦ u = π2 ◦ e ◦ u = π2 ◦ hz1 , z2 i = z2 . (6.25)
Therefore, there exists an arrow u : Z → E such that p1 ◦ u = z1 and p2 ◦ u = z2 . Now we are left
to show the uniqueness of u. Suppose there is another arrow v : Z → E satisfying p1 ◦ v = z1 and
p2 ◦ v = z2 . Then we have
z1 = p1 ◦ v = π1 ◦ e ◦ v and z2 = p2 ◦ v = π2 ◦ e ◦ v. (6.26)
Z
hz1 ,z2 i
z1 z2
e◦v
A π1 A×B π2 B
Therefore, e ◦ v = hz1 , z2 i by the UMP of the product A × B. Then again, by (6.23), e ◦ u = hz1 , z2 i.
As a result,
e ◦ v = e ◦ u. (6.27)
u e
Z E A×B
v
p1
A
is a pullback of f and g.
97
6 Subobjects and Pullbacks 98
(f ◦ π1 ) ◦ e = f ◦ π1 ◦ hp1 , p2 i = f ◦ p1 , (6.28)
(g ◦ π2 ) ◦ e = g ◦ π2 ◦ hp1 , p2 i = g ◦ p2 . (6.29)
u
z
Z
Let π1 ◦ z = z1 and π2 ◦ z = z2 . From (f ◦ π1 ) ◦ z = (g ◦ π2 ) ◦ z, we get
(f ◦ π1 ) ◦ z = (g ◦ π2 ) ◦ z =⇒ f ◦ z1 = g ◦ z2 . (6.30)
p2
E B
e
π2
z1
p1 A×B g
π1
A f
C
Then we have
π1 ◦ (e ◦ u) = π1 ◦ hp1 , p2 i ◦ u = p1 ◦ u = z1 (6.31)
π2 ◦ (e ◦ u) = π2 ◦ hp1 , p2 i ◦ u = p2 ◦ u = z2 . (6.32)
Therefore,
e ◦ u = hz1 , z2 i = z. (6.33)
So indeed, there exists an arrow u : Z → E such that z = e ◦ u. Now we need to show the uniqueness
of u. Suppose there is another arrow v : Z → E such that e ◦ v = z. Then we have
z1 = π1 ◦ z = π1 ◦ e ◦ v = p1 ◦ v and z2 = π2 ◦ z = π2 ◦ e ◦ v = p2 ◦ v. (6.34)
98
6 Subobjects and Pullbacks 99
Corollary 6.3
If a category C has binary products and equalizers, then it has pullbakcs.
h00 h0 h
A f
B g C
1. If the two squares are pullbacks, then so is the outer rectangle. Thus
A ×B (B ×C D) ∼
= A ×C D.
2. If the right square and the outer rectangle are pullbacks, so is the left square.
Proof. 1. Suppose both the squares are pullbacks. One needs to show that the outer rectangle is a
pullback. The outer rectangle is
g 0 ◦f 0
F D
h00 h
A g◦f
C
g ◦ f ◦ h00 = g ◦ h0 ◦ f 0 = h ◦ g 0 ◦ f 0 . (6.35)
v u
g0
F E D
f0
z1
h00 h0 h
A f
B g C
g ◦ f ◦ z1 = h ◦ z2 gives us that
g ◦ (f ◦ z1 ) = h ◦ z2 . (6.36)
Since the right square is a pullback for g and h, there is a unique u : Z → E such that
f ◦ z1 = h0 ◦ u and z2 = g 0 ◦ u. (6.37)
Now, f ◦ z1 = h0 ◦ u, and the left square is a pullback of f and h0 . Therefore, there exists a unique
v : Z → F such that
z1 = h00 ◦ v and u = f 0 ◦ v. (6.38)
99
6 Subobjects and Pullbacks 100
z2
Z
u0 =f 0 ◦v 0
v0
g0
F E D
f0
z1
h00 h0 h
A f
B g C
g 0 ◦ u0 = g 0 ◦ f 0 ◦ v 0 = z2 , and (6.41)
0 0 0 0 0 00 0
h ◦ u = h ◦ f ◦ v = f ◦ h ◦ v = f ◦ z1 . (6.42)
[Link] the right square and the outer rectangle are pullbacks. We need to show that the left
square is also a pullback diagram. The left square clearly commutes, since the given diagram is a
commutative diagram. Now, given another object Z and arrows z1 : Z → A and z2 : Z → E such
that f ◦ z1 = h0 ◦ z2 . We need to show the existence of a unique u : Z → F such that z1 = h00 ◦ u
and z2 = f 0 ◦ u.
g 0 ◦z2
Z
z2
u
g0
F E D
f0
z1
h00 h0 h
A f
B g C
100
6 Subobjects and Pullbacks 101
Z g 0 ◦z2
z2
f 0 ◦u
g0
E D
f ◦z1
h0 h
B g C
We have g ◦ f ◦ z1 = h ◦ g 0 ◦ z2 . Therefore, there exists a unique v : Z → E such that
h0 ◦ v = f ◦ z1 and g 0 ◦ v = g 0 ◦ z2 . (6.46)
Clearly, taking z2 in place of v works, since f ◦ z1 . Therefore, v = z2 , by the uniqueness of v.
Furthermore,
h0 ◦ f 0 ◦ u = f ◦ h00 ◦ u = f ◦ z1 , g 0 ◦ f 0 ◦ u = g 0 ◦ z2 . (6.47)
Therefore, by the uniqueness of v, v = f 0 ◦ u. Hence,
f 0 ◦ u = z2 . (6.48)
So, there exists u : Z → F such that h00 ◦u = z1 and f 0 ◦u = z2 . Now we need to show the uniqueness
of u. Let’s say there is another u0 : Z → F satisfying h00 ◦ u0 = z1 and f 0 ◦ u0 = z2 .
g 0 ◦z2
Z
z2
u
u0
g0
F E D
z1 f0
h00 h0 h
A f
B g C
Remark 6.1. In practice, we often see a slightly different form of Two pullbacks lemma. In the
following commutative diagram,
h00
F A
f0 f
h0
E B
g0 g
D h
C
2. if the bottom square and the outer rectangle is pullback, so is the top square.
This is equivalent to the version we just proved. This diagram can be obtained by rotating our
diagram 90 degrees clockwise, and then reflecting about the diagonal.
101
6 Subobjects and Pullbacks 102
Remark 6.2. In the Two pullbacks lemma, if the left square and the outer rectangle are pullbacks,
then the right square need not be a pullback. The following is a counterexample: let e : X → Y
be a split epi with right inverse s : Y → X, i.e. e ◦ s = 1Y . Furthermore, suppose e is not an
isomorphism. Then consider the following commutative diagram:
1Y 1Y
Y Y Y
1Y s 1Y
Y s X e Y
1Y 1Y
Y e◦s=1Y
Y
This is also a pullback diagram by Example 6.1, since 1Y is monic. However, we assumed e is not
an isomorphism. So by Example 6.2, the right square is not a pullback diagram. Therefore, the
right square can fail to be a pullback even if the left square and the outer rectangle are pullbacks.
Corollary 6.5
The pullback of a commutative triangle is a commutative triangle. Specifically, given a commu-
tative triangle as on the right end of the following “prism diagram”:
hα
A0 A
γ0 γ
α
hβ (6.50)
α0 B0 B
β0 β
C0 h
C
α0 h
for any h : C 0 → C, if one forms the pullbacks α0 and β 0 as on the left end, i.e. if C 0 ←− A0 −→
α
A
β0 hβ β
is a pullback of C 0 −
h
− A and C 0 ←− B 0 −→ B is a pullback of C 0 −
α h
→C ← →C ← − B, then there
exists a unique γ : A → C 0 making the left end a commutative triangle, and the upper face a
0 0
α0 h
Proof. Since C 0 ←− A0 −→ A is a pullback of C 0 −
h α
α
→ C ←
− A, we have the following commutative
pullback square:
hα
A0 A
α0 α
C0 h
C
102
6 Subobjects and Pullbacks 103
Therefore,
h ◦ α 0 = α ◦ hα = β ◦ γ ◦ hα . (6.51)
β0 hβ β
Furthermore, C 0 ←− B 0 −→ B is a pullback of C 0 −
h
− B, and α0 : A0 → C 0 and γ ◦ hα : A0 → C
→C←
0
are arrows such that h ◦ α = β ◦ γ ◦ hα .
A0 γ◦hα
γ0
α0 B0 hβ
B
β0 β
C0 h
C
α0 = β 0 ◦ γ 0 and γ ◦ hα = hβ ◦ γ 0 . (6.52)
So γ 0 is the unique arrow making the left end triangle and the upper face of the prism diagram
commutative. Now, the prism diagram is equivalent to the following commutative diagram:
hα
A0 A
γ0 γ
α0 =β 0 ◦γ 0 B0 hβ
B α=β◦γ
β0 β
C0 h
C
The outer rectangle and the bottom square are pullbacks. Therefore, by Two pullbacks lemma, the
top square is also a pullback. ■
Proposition 6.6
Pullback is a functor, i.e. for fixed h : C 0 → C in a category C with pullbacks, there is a functor
h∗ : C/C → C/C 0 defined by
α 0 α0 0
A−
→ C 7→ C ×C A −→ C ,
where α0 is the pullback of α along h. The effect of the functor h∗ on an arrow γ : α → β in C/C
is given by the pullback diagram of a commutative triangle (6.50): h∗ (γ) = γ 0 , whose unique
existence is guaranted by Corollary 6.5.
Proof. Given an object α ∈ Ob (C/C), we must check that h∗ (1α ) = 1h∗ (α) . Given α : A → C in C, it
is an object in C/C. The arrow 1α in C/C is the arrow 1A in C. Then the following is a commutative
triangle in C.
103
6 Subobjects and Pullbacks 104
A
1A
α A
C
Consider the pullback of this commutative triangle along h : C 0 → C.
hα
C 0 ×C A = A0 A
h∗ (1 α) 1A
α
hα
α0 A0 A
α0 α
C0 h
C
By Corollary 6.5 h∗ (1α ) is the unique arrow A0 → A0 such that the left end triangle and the upper
face of the prism are commutative. In other words,
One can easily check that 1A0 clearly satisfies this requirement.
1 A0 hα
A0 A0 A0 A
α0 1A0 1A
α0
C0 A0 hα
A
α1 B
α2
C γ2
α3
D
γ10and γ20
are the unique arrows such that the left triangles and upper faces of the following prism
diagrams commute.
104
6 Subobjects and Pullbacks 105
hα1 hα2
A0 A B0 B
γ10 γ1 γ20 γ2
α1 α2
hα2 hα3
α01 B0 B α02 D0 D
α02 α2 α03 α3
C0 h
C C0 h
C
In other words,
α10 = α20 ◦ γ10 and γ1 ◦ hα1 = hα2 ◦ γ10 ; (6.56)
α20 = α30 ◦ γ20 and γ2 ◦ hα2 = hα3 ◦ γ20 . (6.57)
Combining these two prism diagrams, we get a commutative “cubic diagram”:
hα1
A0 A
γ10 γ1
α1
α01 B0 hα2
B
α02 α2
γ20
C0 h
C γ2
α03 α3
D0 hα3
D
α1 D
α3
C
(γ2 ◦ γ1 )0 is the unique arrow such that left triangle and upper face of the following prism diagram
commute:
hα1
A0 A
(γ2 ◦γ1 )0 γ2 ◦γ1
α1
hα3
α01 D0 D
α03 α2
C0 h
C
In other words,
α10 = α30 ◦ (γ2 ◦ γ1 )0 and (γ2 ◦ γ1 ) ◦ hα1 = hα3 ◦ (γ2 ◦ γ1 )0 . (6.58)
One can easily check that γ20 ◦ γ10 clearly satisfies this requirement.
105
6 Subobjects and Pullbacks 106
C0 D0 hα3
D
Therefore, γ20 ◦ γ10 satisfies (6.58). Since (γ2 ◦ γ1 )0 is unique, we must have
Example 6.3. Let I be an index set, and consider an I-indexed family of sets
obtained by “reindexing along α”. Let us describe this reindexing using pullback. For each set Ai in
the family (6.62), take the constant i-valued function pi : Ai → I with all of Ai mapped to i ∈ I, and
consider the induced map on the coproduct
a
p = [pi ] : Ai → I.
i∈I
`
It is the unique function i∈I Ai → I such that each of the following triangles commute:
I
pk
p
`
Ak ιk Ai
i∈I
`
Therefore, given (a, k) ∈ i∈I Ai , with a ∈ Ak ,
In a similar manner, for each Aα(j) in the family (6.63), we can form the constant j-valued function
qj : Aα(j) → J with all of Aα(j) mapped to j ∈ J, and consider the induced map on the coproduct
a
q = [qj ] : Aα(j) → J.
j∈J
`
It is the unique function j∈J Aα(j) → J such that each of the following triangles commute for all
l ∈ J:
106
6 Subobjects and Pullbacks 107
J
ql
q
`
Aα(l) Aα(j)
ι0l j∈J
`
Therefore, given (a, l) ∈ j∈J Aα(j) , with a ∈ Aα(l) ,
q (a, l) = q ι0l (a) = ql (a) = l.
The reindexed family Aα(j) can be obtained by taking the pullback along the function α : J → I
j∈J
as can be seen from the following diagram:
` αp `
Aα(j) Ai
j∈J i∈I
(6.64)
q p
J α I
` ` `
where αp : j∈J Aα(j) → i∈I Ai is defined as follows: given (a, l) ∈ j∈J Aα(j) , with a ∈ Aα(l) ,
a
αp (a, l) = (a, α (l)) ∈ Ai .
i∈I
`
It’s easy to see that the square above commutes, i.e. p ◦ αp = α ◦ q. Given (a, l) ∈ j∈J Aα(j) , with
a ∈ Aα(l) , one has
Therefore, p ◦ αp = α ◦ q. The fact the the UMP of pullback is satisfied for the above square can be
`
checked easily. Suppose there is another set X and functions f : X → J and g : X → i∈I Ai such
`
that p ◦ g = α ◦ f . We need to show the existence of a unique u : X → j∈J Aα(j) such that f = q ◦ u
and g = αp ◦ u, i.e. the following diagram commutes:
g
X
u
` αp `
Aα(j) Ai
j∈J i∈I
f
q p
J α I
`
Given x ∈ X, g (x) ∈ i∈I Ai , so g (x) = (a, i) for some i ∈ I and a ∈ Ai . Furthermore, let
f (x) = j ∈ J. Then p ◦ g = α ◦ f gives us
107
6 Subobjects and Pullbacks 108
where j = f (x) and (a, α (j)) = g (x). In terms of the inclusions of coproduct,
a
ια(j) (a) = (a, α (j)) ∈ Ai . (6.67)
i∈I
So a = ι−1
α(f (x)) (g (x)). In other words,
u (x) = ι−1
α(f (x)) (g (x)) , f (x) . (6.68)
Then
Furthermore, f = q ◦ v gives us
which matches precisely with the expression of u, from (6.68). Therefore, u is unique, and hence (6.64)
is a pullback diagram. Hence, !
a a
J ×I Ai ∼
= Aα(j) . (6.74)
i∈I j∈J
Proposition 6.7
A category has finite products and equalizers if and only if it has pullbacks and a terminal object.
Proof. (⇒) If a category has all finite products, then it has nullary product as well. A nullary
product is precisely a terminal object, as we observed in Section 4.5. Also, if a category admits all
finite products, it definitely admits all binary products. A category admitting binary products and
equalizers have pullbacks, by Corollary 6.3.
(⇐) Suppose we are in a category with pullbacks and a terminal object 1. In order to show that the
category admits finite products, it suffices to show that the category admits binary products, since
any finite product can be constructed from binary products. Given objects A and B, there are unique
uA uB
arrows uA : A → 1 and uB : B → 1. Now, consider the pullback of A −−→ 1 ←−− B:
p2
A ×1 B B
p1 uB
A uA 1
We claim that A ×1 B is a product of A and B. In order to show that, we need to verify the UMP of
product. Suppose we are given any arrows x1 : X → A and x2 : X → B.
108
6 Subobjects and Pullbacks 109
X x2
u
X
x1 x2
u A ×1 B p2 B
x1
A p1 A ×1 B p2 B p1 uB
A uA 1
Since 1 is a terminal object, there is a unique arrow X → 1. uA ◦ x1 , uB ◦ x2 are arrows from X to 1.
Therefore, uA ◦ x1 = uB ◦ x2 . From the UMP of product, there is a unique arrow u : X → A ×1 B
such that x1 = p1 ◦ u and x2 = p2 ◦ u (which is precisely what the UMP of product says). Therefore,
A ×1 B is a product of A and B, i.e.
A ×1 B ∼= A × B. (6.75)
Now, we have to prove the existence of equalizers. Suppose we are given two parallel arrows f, g :
A → B. Since we already proved that the category admits binary products, we can form the arrows
hf, gi : A → B × B and ∆ = h1B , 1B i : B → B × B. They are the unique arrows such that the
diagrams below commute:
A B
f g 1B 1B
hf,gi h1B ,1B i
B π1 B×B π2 B B π1 B×B π2 B
hf,gi ∆
Now, let us form the pullback of A −−−→ B × B ←
− B:
h
E B
A B×B
hf,gi
First, let us verify that f ◦ e = g ◦ e. Since (6.76) is a pullback diagram, it’s a commutative square.
Therefore,
hf, gi ◦ e = h1B , 1B i ◦ h. (6.77)
Using Proposition 3.10, hf, gi ◦ e = hf ◦ e, g ◦ ei and h1B , 1B i ◦ h = hh, hi. As a result,
hf ◦ e, g ◦ ei = hh, hi . (6.78)
π1 ◦ hf ◦ e, g ◦ ei = π1 ◦ hh, hi =⇒ f ◦ e = h, (6.79)
π2 ◦ hf ◦ e, g ◦ ei = π2 ◦ hh, hi =⇒ g ◦ e = h. (6.80)
109
6 Subobjects and Pullbacks 110
f
e
E A B
g
u
a
Z
Consider the following diagram:
Z f ◦a=g◦a
u
∃!
h
E B
a
e ∆=h1B ,1B i
A B×B
hf,gi
Since f ◦ a = g ◦ a, we have
Therefore, hf, gi ◦ a = ∆ ◦ (f ◦ a). By the UMP of pullbacks, there exists a unique arrow u : Z → E
such that e ◦ u = a and h ◦ u = f ◦ a. So there indeed exists an arrow u : Z → E satisfying e ◦ u = a.
Now we need to verify the uniqueness of u.
Suppose there is another v : Z → E satisfying e ◦ v = a. Now, consider the following diagram:
Z f ◦a=g◦a
u
v
h
E B
a
e ∆=h1B ,1B i
A B×B
hf,gi
h ◦ v = (f ◦ e) ◦ v = f ◦ (e ◦ v) = f ◦ a. (6.82)
110
6 Subobjects and Pullbacks 111
u
a
Z
we needed to show the existence of a unique u : Z → E such that the triangle above commutes,
i.e. e ◦ u = a. u is the unique arrow such that e ◦ u = a and h ◦ u = f ◦ a. But we need uniqueness
with respect to the condition e ◦ u = a only. We cannot invoke the argument regarding uniqueness
of u in the pullback diagram to conclude that u is unique in the equalizer diagram, since we are
relaxing the condition a little bit. In principle, there could exist another arrow v for which e◦v = a
but h ◦ v 6= f ◦ a. This does not violate the uniqueness property of u. That is why we needed to
check the uniqueness again.
111
7 Limits and Colimits
§7.1 Limits
Definition 7.1. Let J be a small category and C be any category. A diagram of type J in C is
a functor
D : J → C.
We write the objects in the “index category” J with lowercase i, j, . . ., and the values of the functor
D : J → C in the form Di , Dj , . . . being objects in C.
• an object C in C, and
such that for each arrow α : i → j in J , cj = Dα ◦ ci , i.e. the following diagram commutes:
C
ci cj
Di Dα
Dj
is an arrow ϑ : C → C 0 in C making each triangle of the following form commute: (for each
j ∈ Ob (J )):
C ϑ
C0
c0j
cj
Dj
i.e. cj = cj0 ◦ ϑ for all j ∈ Ob (J ). Thus we have a category Cone (D) of all cones to a diagram
D.
Given arrows ϑ : (C, cj ) → C 0 , c0j and % : C 0 , c0j → C 00 , c00j between cones, one can form the
composite
% ◦ ϑ : (C, cj ) → C 00 , c00j .
Then ϑ : C → C 0 and % : C 0 → C are arrows in C such that the following triangles commute for each
j ∈ Ob (J ):
%
C ϑ
C0 C0 C 00
c0j c00
j
cj c0j
Dj Dj
112
7 Limits and Colimits 113
Combining these two triangles, we get the following commutative diagram, for each j ∈ Ob (J ):
%◦ϑ
C ϑ
C0 % C 00
c0j
cj c00
j
Dj
c00
j
cj
Dj
So % ◦ ϑ is indeed an arrow from (C, cj ) to C 00 , c00j in Cone (D). The associativity of composition
is clear, since the arrow in Cone (D) are actually arrows in the category C, and associativity of
composition holds in C.
Given any object (C, cj ) in Cone (D), its identity arrow 1(C,cj ) is the arrow 1C in C. Indeed, the
following triangle commutes for each j ∈ Ob (J ):
1C
C C
cj
cj
Dj
Therefore, 1C is indeed an arrow (C, cj ) to itself. Given any arrow ϑ : (C, cj ) → C 0 , c0j in Cone(D),
since ϑ : C → C 0 is an arroow in C, ϑ ◦ 1C = ϑ in C. Therefore,
ϑ ◦ 1(C,cj ) = ϑ
1(C 0 ,c0 ) ◦ϑ = ϑ
j
in Cone(D). Hence, 1(C,cj ) = 1C is indeed the identity arrow of the object (C, cj ) in Cone (D).
Therefore, Cone(D) is a category.
We can imagine a cone to be cone over a diagram D with its apex in C.
Definition 7.3 (Limit). A limit for a diagram D : J → C is a terminal object in Cone (D). A
finite limit is a limit for a diagram on a finite index category J .
for all j. In other words, the following diagram commutes for each i, j:
113
7 Limits and Colimits 114
u
ci cj
limj Dj
←−
pi pj
Di Dα
Dj
Thus the limiting cone limj Dj , pj can be thought of as the “closest” one to the diagram D, and
←−
indeed the other cones come from it just by composing with an arrow at the vertex, namely u : C →
limj Dj .
←−
Example 7.1. 1. Take J = {1, 2}, the discrete category with two objects and no nonidentity arrows.
A diagram D : J → C is a pair of objects D1 and D2 in C. A cone to D is an object C of C equipped
with arrows
c1 c2
D1 C D2
A limit of D is a terminal such cone, that is product of D1 and D2 in C:
π1 π2
D1 D1 × D2 D2
Therefore,
∼ D1 × D2 .
lim Dj =
←−
j
A cone is an object C along with a pair of arrows c1 : C → D1 and c2 : C → D2 such that the
following diagram commutes:
Dα
D1 D2
Dβ
c1
c2
C
In other words,
Dα ◦ c1 = c2 = Dβ ◦ c1 . (7.2)
c
A limit for D is, therefore, an equalizer C −→
1
D1 of the parallel arrows Dα , Dβ : D1 → D2 . If there
is any other cone
Dα
D1 D2
Dβ
c01
c02
C0
satisfying Dα ◦ c01 = c02 = Dβ ◦ c01 , then from the UMP of limit, we know that there exists a unique
arrow u : C 0 → C such that c1 ◦ u = c01 and c2 ◦ u = c02 .
114
7 Limits and Colimits 115
Dα
D1 D2
Dβ
c1 c2
C
c01 c02
u ∃!
C0
The diagram is equivalent to the following equalizer diagram:
c1 Dα
C D1 D2
Dβ
u
c01
C0
Therefore, the equalizer is the “nearest” cone to the underlying diagram, i.e. a limit.
3. Now, J can be any small category, even the empty category. When J is the empty category, it has
no objects and no arrows. In this case, the cone consists of the apex (an object of C) only. Therefore,
the category Cone (D) is actually the category C. The limit for this diagram is the terminal object
of Cone (D), which coincides with the terminal object 1 of C. Therefore, the limit of the diagram
D : J → C when J is empty is 1. We write this as
lim Dj ∼
= 1.
←−
j
3 α 1
So a diagram D : J → C of type J consists of the objects and arrows in C as below:
D2
Dβ
D3 Dα
D1
A cone to this diagram D is given by the following commutative diagram:
c2
C D2
c1
c3 Dβ
D3 Dα
D1
Each of the triangles above commute, so that
Dα ◦ c3 = c1 = Dα ◦ c2 . (7.3)
Now, if C is the nearest cone to D, then from the UMP of a limit, we know that given any other
cone C 0 , c0j , there is a unique arrow u : C 0 → C such that c0j = cj ◦ u for all j, i.e. the following
diagram commutes:
115
7 Limits and Colimits 116
C0 c02
u
∃! c01
C c2 D2
c03
c3 Dβ
c1
D3 Dα
D1
This is precisely the UMP of pullback. Therefore,
lim Dj ∼
= D3 ×D1 D2 . (7.4)
←−
j
Definition 7.4. A category C is said to have all finite limits if every finite diagram D : J → C has
a limit in C.
Proposition 7.1
A category has all finite limits if and only if it has finite products and equalizers, i.e. it has
pullbacks and a terminal object.
Proof. (⇒) If a category has all finite limits, then it has all finite products and equalizers, since finite
products and equalizers can be seen as finite limits, by Example 7.1.
(⇐) Let a category C admit finite products and equalizers. We have to prove that it admits all finite
limits. Let D : J → C be a finite diagram, i.e. the index category J is finite. Let J0 and J1 denote
the object set and arrow set of J , respectively, which are both finite sets. For i ∈ J0 , Di is an object
in C. Since C admits finite products, we can form the following products:
Y Y
Di and Dcod β .
i∈J0 β∈J1
πcod α
ϕ
Q
Dcod α pα Dcod β
β∈J1
Q Q
In other words, ϕ : i∈J0 Di → β∈J1 Dcod β is the unique arrow such that
πcod α = pα ◦ ϕ (7.6)
116
7 Limits and Colimits 117
Dα ◦πdom α
ψ
Q
Dcod α pα Dcod β
β∈J1
Q Q
In other words, ψ : i∈J0 Di → β∈J1 Dcod β is the unique arrow such that
Dα ◦ πdom α = pα ◦ ψ. (7.8)
Q ϕ Q
Di Dcod β
i∈J0 ψ β∈J1
πdom α pα
Ddomα Dα
Dcod α
(Note that this is NOT technically a commutative diagram. The upper triangle commutes with
respect to ϕ, the lower square commutes with respect to ψ.) So we have two parallel arrows
Q ϕ Q
Di Dcod β
i∈J0 ψ β∈J1
Q
Since C has all equalizers, take the equalizer e : E → i∈J0 Di of ϕ and ψ.
e Q ϕ Q
E Di Dcod β
i∈J0 ψ β∈J1
Dj α Dk
117
7 Limits and Colimits 118
Q
Since e : E → i∈J0 Di is an equalizer of of ϕ and ψ, ϕ ◦ e = ψ ◦ e. Given an arrow α : j → k in J ,
we have
µk = πk ◦ e = πcod α ◦ e
= pα ◦ ϕ ◦ e = pα ◦ ψ ◦ e
= Dα ◦ πdom α ◦ e = Dα ◦ πj ◦ e
= D α ◦ µj . (7.9)
Hence, (E, µj ) is a cone to the diagram D. We now need to verify the UMP of limit. Suppose
F, τj : F → Dj is another cone to the diagram D. Then for any arrow α : j → k in J , the following
diagram commutes:
F
τj τk
Dj Dα
Dk
Q
Dj πj Di
i∈J0
In other words, πj ◦ h = τj , for all j ∈ J0 . Now, given arrows τcod α = πcod α ◦ h : F → Dcod α , there is
Q
a unique arrow g : F → β∈J1 Dcod β such that the following diagram commutes for all α ∈ J1 :
F
τcod α =πcod α ◦h
g
Q
Dcod α pα Dcod β
β∈J1
u
h
118
7 Limits and Colimits 119
In other words, e ◦ u = h.
u
F E
τj
µj
Dj
µj ◦ u = πj ◦ e ◦ u = πj ◦ h = τj , (7.13)
for all j ∈ J0 . Therefore, u is indeed an arrow from the cone (F, τj ) to (E, µj ). We now need to show
the uniqueness of u. Suppose there is another arrow v : F → E such that µj ◦ v = τj . Then we have
τj = µj ◦ v = πj ◦ (e ◦ v) . (7.14)
for all j ∈ J0 . But h is the unique arrow such that πj ◦ h = τj for all j ∈ J0 . Therefore, by the
uniqueness of h, h = e ◦ v. Moreover, u is the unique arrow such that e ◦ u = h. So u = v, proving
the uniqueness of u. Hence, there is a unique arrow from the cone (F, τj ) to (E, µj ). So (E, µj ) is a
limiting cone. ■
Note that there is no real use of the finiteness of the index category, except for forming the products
Y Y
Di and Dcod β .
i∈J0 β∈J1
Corollary 7.2
A category has all limits of some cardinality if and only if it has all equalizers and all products
of that cardinality, where the category C is said to have limits (resp. products) of a cardinality κ
if and only if C has a limit for every diagram D : J → C where card (J1 ) ≤ κ.
(Here, F Di = (F D)i = F (Di )) A functor that preserves all limits is said to be continuous.
We have seen earlier that given a category C admitting products of a given cardinality and all equalizers,
it admits all limits of the same cardinality for any diagram D : J → C. Now, take a functor F : C → D
that preserves products of the given cardinality and also preserve equalizers. One can immediately
form a diagram F ◦ D : J → D. Now, construct a limit (E, µj : E → Dj ) of the diagram D : J → C
following the way outlined in the proof of Proposition 7.1, where the apex E of the limiting cone is
obtained from the equalizer of a pair of parallel arrows between two products. Now use the property
of the functor F : C → D that is preserves products and equalizers to construct a limit of the diagram
119
7 Limits and Colimits 120
F ◦ D : J → D in the category D. Then the pertinent limit is (F (E) , F (µj ) : F (E) → F (Dj )). It
means that one has !
F lim Dk ∼ = lim F Dk .
←− ←−
k k
The above definition is precisely the definition of preservtion of a limit under the functor F : C → D.
One observes that in order to verify that a functor preserves limit of a certain cardinality, it suffices
to show that it preserves products of that cardinality and all equalizers.
For instance, let C be a (locally small) category with all small limits (i.e. the index category is
small). The representable functors will preserves those limits. In other words, for a given object C in
C, the functor
HomC (C, −) : C → Sets
will preserve limits. In fact, a stronger result is true. HomC (C, −) preserves all limits that exist.
Theorem 7.3
The covariant representable functors HomC (X, −) preserve limits that exist. In other words, if
µj : limi Di → Dj is a limit for the diagram D : J → C, then the cone
←−
!
HomC (X, −) (µj ) : HomC (X, −) lim Di → HomC (X, −) (Dj )
←−
i
Dj Dα
Dk
Under the action of the functor HomC (X, −), this commutative diagram goes to the following com-
mutative diagram in Sets.
HomC X, limi Di
←−
(µj )∗ (µk )∗
We now need to show that it is a limiting cone. For that purpose, suppose (C, pj ) is another
cone
tothis diagram
in Sets.
We need to show the existence of a unique arrow u : (C, pj ) →
HomC X, limi Di , (µj )∗ .
←−
120
7 Limits and Colimits 121
u
pj pk
HomC X, limi Di
←−
(µj )∗ (µk )∗
where pj (c) : X → Dj and pk (c) : X → Dk are arrows in C. In other words, the following diagram
commutes for all arrows α : j → k in J :
X
pj (c) pk (c)
Dj Dα
Dk
u(c)
pj (c) pk (c)
limi Di
←−
µj µk
Dj Dα
Dk
In other words, there exists a unique arrow u (c) : X → limi Di such that
←−
µj ◦ u (c) = pj (c) (7.17)
121
7 Limits and Colimits 122
u v
pj pk
HomC X, limi Di
←−
(µj )∗ (µk )∗
Corollary 7.4
Let C be a category that admits all limits. Then the representable functors HomC (C, −) preserve
all limits.
where F (A) and F (B) are the assigned objects of D under F . In other words, given an arrow
f : A → B in C, F (f ) : F (B) → F (A) is an arrow in D, such that the following hold:
122
7 Limits and Colimits 123
C D
f F (f )
A B F (A) F (B)
F
g F (g)
g◦f F (g◦f )
C F (C)
g◦f
§7.3 Colimits
Colimit is the dual construction of limit. As before, we define a cocone to a diagram D : J → C and
we form the category of cocones. A colimit for the diagram D is then defined to be an initial object
in the category of cocones.
123
7 Limits and Colimits 124
• an object C in C, and
such that for each arrow α : i → j in J , cj ◦ Dα = ci , i.e. the following diagram commutes:
Dα
Di Dj
ci cj
is an arrow ϑ : C → C 0 in C making each triangle of the following form commute: (for each
j ∈ Ob (J ))
C ϑ
C0
c0j
cj
Dj
i.e. c0j = ϑ ◦ cj for all j ∈ Ob (J ). Thus we have a category Cocone (D) of all cocones to a
diagram D.
Definition 7.8 (Coimit). A colimit for a diagram D : J → C is a terminal object in Cocone (D).
A finite colimit is a colimit for a diagram on a finite index category J .
pi : Di → lim Dj .
−→
j
The colimit of a diagram itself is a cocone limj Dj , pj . The colimit of a diagram has the following
−→
UMP: Given any cocone (C, cj ) to D, there is a unique arrow u : limj Dj → C such that
−→
u ◦ pj = cj , (7.28)
for all j. In other words, the following diagram commutes for each i, j:
u
ci cj
limj Dj
−→
pi pj
Di Dα
Dj
124
7 Limits and Colimits 125
Thus the colimiting cone limj Dj , pj can be thought of as the “furthest” one to the diagram D, or
−→
the “universal repelling object”.
Lemma 7.5
Let (L, µj ) be a limit to the diagram D : J → C. Then L, µop
j is a colimit to the opposite
diagram Dop : J op → C op , defined as
Dop (i) = Di ,
Dop (αop ) = D (α)op = Dαop .
Proof. Since (L, µj ) is a cone to the diagram D in C, we have µj = Dα ◦ µi for each arrow α : i → j
in J , i.e. the following diagram commutes in C op :
L
µi µj
Di Dα
Dj
Then reversing all the arrows, we get the following commutative diagram in C op :
L
µop
i
µop
j
Di op Dj
Dα
Therefore, for every arrow αop : j → i in J op , µop op
j = µi ◦ Dα . So L, µj
op op
is indeed a cocone to the
diagram D : J → C in C .
op op op op
Note that we only used the fact that (L, µj) is a cone. So this actually proves that if (C, pj ) is a
cone to the diagram D : J → C, then C, pop j is a cocone to the opposite diagram Dop : J op → C op .
Dually, if C, pop
j is a cocone to the diagram Dop : J op → C op , then (C, pj ) is a cone to the diagram
D : J → C.
Let us now verify that L, µop j is a colimit. Suppose we have another cocone C, p op
j to the
diagram D : J → C . Then (C, pj ) is a cone to the diagram D : J → C. Since (L, µj ) is a
op op op
limiting cone to the diagram D, there is a unique arrow u : C → L such that pj = µj ◦ u for all
j ∈ Ob J . In other words, the following diagram commutes for each i, j:
C
u
pi pj
L
µi µj
Di Dα
Dj
125
7 Limits and Colimits 126
uop
pop pop
j
i
L
µop
i
µop
j
Di op Dj
Dα
So, given another cocone C, pop j , there is an arrow uop : L → C such that pop j = u
op ◦ µop for all
j
j ∈ Ob (J op ). The uniqueness of u follows from the fact that u is unique. Indeed, if there existed
another arrow v op : L → C satisfying pop j = v
op ◦ µop (in C op ) for all j ∈ Ob (J op ), then v satisfies
j
pj = µj ◦ v (in C) for all
j ∈ Ob J . Therefore, by the uniqueness of u, u = v, and hence
v op = uop .
op op op
Hence, given a cocone C, pj , there is a unique arrow uop : L, µj → C, pj in the cocone
category Cocone(Dop ). Therefore, L, µop
j is an initial object in Cocone(Dop ), i.e. a colimit to the
diagram Dop . ■
Corollary 7.6
The contravariant representable functors HomC (−, X) take colimits to limits. In other words, if
µj : Dj → limi Di is a colimit for the diagram D : J → C, then the cocone
−→
!
HomC (−, X) (µj ) : HomC (−, X) lim Di → HomC (−, X) (Dj )
−→
i
µi µj
limi Di
−→
let us examine where the functor HomC (−, X) takes this cocone to.
HomC (Dα ,X)
Dα HomC (Di , X) HomC (Dj , X)
Di Dj
HomC (−, X)
µi µj
=
HomC (µi ,X) HomC (µj ,X)
limi Di HomC limi Di , X
−→ −→
(7.29)
Since the contravariant functor HomC (−, X) is in one-to-one correspondence with the covariant functor
HomC op (X, −) : C op → Sets, the diagram on the RHS of (7.29) is isomorphic to the follwoing diagram:
op
HomC op (X,Dα )
HomC op (X, Di ) HomC op (X, Dj )
(7.30)
HomC op (X,µop
i ) HomC op (X,µop
j )
HomC op X, limi Di
−→
126
7 Limits and Colimits 127
Furthermore, since limi Di , µj is a colimit to the diagram D : J → C, by the dual statement of
−→
Lemma 7.5, limi Di , µop is a limit to the diagram Dop : J op → C op . Furthermore, by Theorem 7.3,
−→ j
the covariant hom-functors preserve limits. Therefore, the diagram in (7.30) is a limiting cone. In
other words, the diagrams in (7.29) are also limiting cones. Hence, HomC (−, X) takes colimits to
limits. ■
Example 7.2 (Pushout). Pushout is the dual construction of pushback. Let us consider pushout in
Sets. Suppose we have two functions:
g
A C
B
We can construct the pushout of f and g as follows: Start with the coproduct (disjoint union) of B
and C.
iB iC
B B+C C
The identity those elements b ∈ B with the elements c ∈ C whenever there is an element a ∈ A with
f (a) = b and g (a) = c,
i.e. we take the equivalence relation ∼ on B + C generated by the conditions
(f (a), 0) ∼ (g(a), 1) ,
for each a ∈ A. Finally quotient out B + C by ∼ to obtain the pushout
B +A C ∼
= (B + C) / ∼ . (7.31)
We obtain B +A C as the following coequalizer:
iB ◦f
π
A B+C B +A C
iC ◦g
It’s the dual construction of the pullback, as the pullback was obtained as an equalizer between two
parallel arrows.
g
A C
iC
f B+C π◦iC
iB π
B π◦iB
B +A C
Example 7.3 (Pushout in Top). Pushouts in Top are similarly formed from coproducts and coequal-
izers, which can be made first in Sets and then topologized as sum (topological sum) and quotient
spaces. For example, pushout can be used to construct S 2 from D2 . Let D2 be the 2-disk and S 1
be the 1-dimensional sphere (i.e. circle) with the inclusion i : S 1 → D2 as the boundary of the disk.
Then the 2-sphere S 2 is the pushout
i
S1 D2
D2 S2
127
7 Limits and Colimits 128
i2
π◦i2
π
i1
π◦i1
Here π is the quotient map that identifies the boundaries of the 2-disks.
of groups and group homomorphsms, and we want a colimiting group G∞ with group homomorphisms
un : Gn → G∞ satisfying un+1 ◦ gn = un for all n ∈ N. Moreover, G∞ should be “universal” with this
property. We are looking at the colimit of the diagram D : ω → Groups, where the index category is
the ordinal numbers ω = (N, ≤) regarded as a poset category
0 1 2 3 ···
It is a diagram of type ω in the category Groups. The colimiting group is the colimit of this diagram
D, which is an initial object in the category Cocone (D).
lim Gn ∼
= G∞ .
−→
n∈ω
This group always exists and can be constructed as follows. Begin with the coproduct (disjoint union)
of the sets Gn , for n ∈ ω: G
Gn
n∈ω
is regarded as the union of all ordered pairs (xn , n) for xn ∈ Gn , as n varies over ω. We want to put
F
an equivalence relation ∼ on n∈ω Gn . For i ≤ j, we define gei,j to be the composite:
gi gi+1 gi+2 gj−1
Gi Gi+1 Gi+2 ··· Gj
e
gi,j =gj−1 ◦···◦gi+1 ◦gi
128
7 Limits and Colimits 129
In particular, gei,i+1 = gi , and gei,i = 1Gi . We define (xn , n) ∼ (ym , m) if and only if there exists some
k ≥ m, n such that
gen,k (xn ) = gem,k (ym ) . (7.33)
Since gen,n+1 = gn , one has (xn , n) ∼ (gn (xn ), n + 1) for each xn ∈ Gn . One can easily verify that ∼ is
an equivalence relation.
F
• (Reflexivity) Given (xn , n) ∈ i∈ω Gi , (xn , n) ∼ (xn , n), because gen,n (xn ) = gen,n (xn ).
• (Symmetry) If (xn , n) ∼ (ym , m), there exists some k ≥ m, n such that gen,k (xn ) = gem,k (ym ). So
there is some k ≥ n, m such that gem,k (ym ) = gen,k (xn ). Therefore, (ym , m) ∼ (xn , n).
• (Transitivity) Suppose (xn , n) ∼ (ym , m) and (ym , m) ∼ (zl , l). Then there exists some k1 ≥ m, n
and k2 ≥ n, l such that
gen,k1 (xn ) = gem,k1 (ym ) and gem,k2 (ym ) = gel,k2 (zl ) . (7.34)
Without loss of generality, suppose k2 ≥ k1 (if not, we can always choose a larger k2 ). Then
gek1 ,k2 ◦ gen,k1 = (gk2 −1 ◦ · · · ◦ gk1 +1 ◦ gk1 ) ◦ (gk1 −1 ◦ · · · ◦ gn+1 ◦ gn ) = gn,k2 . (7.35)
129
7 Limits and Colimits 130
un un+1
G∞
For xn ∈ Gn , xn ∼ gn (xn ). So [xn ] = [gn (xn )]. Therefore,
(un+1 ◦ gn ) (xn ) = [gn (xn )] = [xn ] = un (xn ) . (7.47)
Hence, un+1 ◦ gn = un for each n. So (G∞ , un : Gn → G∞ ) is indeed a cocone. The universality
of G∞ along with the homomorphisms un : Gn → G∞ results from the fact that this construction
is essentially a colimit in Sets with an induced group structure. Suppose there is a group H with
homomorphisms hn : Gn → H such that hn+1 ◦ gn = hn for each n. We need to show the existence of
a unique h : G∞ → H such that hn = h ◦ un for each n.
gn
Gn Gn+1
un un+1
G∞ (7.48)
hn hn+1
h
130
7 Limits and Colimits 131
We have to show that h is well-defined. Suppose xn ∼ ym for some ym ∈ Gm . Then there exists
k ≥ n, m such that gen,k (xn ) = gem,k (ym ). Now,
hn = hn+1 ◦ gn
= hn+2 ◦ gn+1 ◦ gn
= hn+3 ◦ gn+2 ◦ gn+1 ◦ gn
= ···
= hk ◦ gk−1 ◦ · · · ◦ gn+1 ◦ gn = hk ◦ gen,k . (7.50)
H
hn hk
hn+2
hn+1
e
gn,k =gk−1 ◦···◦gn+1 ◦gn
h ([xn ]) = hn (xn )
= hk (gen,k (xn ))
= hk (gem,k (ym ))
= hm (ym ) = h ([ym ]) . (7.51)
un un+1
G∞
hn hn+1
h h0
131
8 Exponentials
§8.1 Exponential in a Category
Exponentials can be thought of as the categorical notion of a “function space”. As with everything,
we shall first consider the category Sets to motivate ourselves about the definition of exponentials. In
Sets, we use the notation C B to denote the set of all functions from B to C, i.e.
C B = HomSets (B, C) .
f (a, −) : B → C,
fe : A → C B
a 7→ f (a, −) .
Furthermore, any map g : A → C B is uniquely of the form fe, for some f : A × B → C. This function
f is defined as follows:
f (a, b) = g (a) (b) .
So we have an isomorphism of Hom-sets
HomSets (A × B, C) ∼
= HomSets A, C B . (8.1)
In other words, there is a bijection HomSets (A × B, C) → HomSets A, C B taking f to fe. This
bijection is mediated by an operation of evaluation. In Sets, this evaluation function is
eval : C B × B → C
(g, b) 7→ g (b) .
In other words, eval (g, b) = g (b). This evaluation function has the following UMP: given any set A
and any function f : A × B → C, there is a unique function fe : A → C B such that
eval ◦ fe × 1B = f. (8.2)
eval
CB CB × B C
fe fe×1B
f
A A×B
Now we can extend this to any arbitrary category that admits binary products.
132
8 Exponentials 133
CB CB × B C
fe fe×1B
f
A A×B
The arrow : C B × B → C is called evaluation, and the unique arrow fe : A → C B is called the
(exponential) transpose of f : A × B → C. Given any arrow g : A → C B , we define
g = ◦ (g × 1B ) : A × B → C,
and also call g the transpose of g. Let ϕ : HomC (A × B, C) → HomC A, C B be the function
defined as
ϕ (f ) = fe. (8.4)
Furthermore, we define ψ : HomC A, C B → HomC (A × B, C) as
ψ (g) = g = ◦ (g × 1B ) . (8.5)
e which is the unique arrow A → C B such that the following
Then given g : A → C B , ϕ (ψ (g)) = g,
diagram commutes:
CB × B C
eg×1B
g
A×B
In other words,
g = ◦ ge × 1B . (8.6)
e we get
But the definition of g is g = ◦ (g × 1B ). Therefore, by the uniqueness of g,
ge = g, (8.7)
for any g ∈ HomC A, C B . Therefore,
fe×1B
f
A×B
133
8 Exponentials 134
So ◦ fe × 1B = f , and hence
fe = f, (8.10)
for any f ∈ HomC (A × B, C). Therefore,
Example 8.1. We have already seen that Sets is a cartesian closed category. The category Setsfin
of finite sets is also a cartesian closed category (CCC). If M and N are finite sets, then the set N M
of all functions from M to N is also a finite set. In fact, it has cardinality
N M = |N ||M | .
Example 8.2. Consider the category Pos of posets and monotone functions. This is a cartesian
closed category. Given posets P and Q, the cartesian product of P and Q is also a poset, and is
partially ordered by
(p, q) ⩽ p0 , q 0 ⇐⇒ p ≤P p0 and q ≤Q q 0 . (8.13)
Then ⩽ is a partial order on P × Q, because
• If (p, q) ⩽ (p0 , q 0 ) and (p0 , q 0 ) ⩽ (p00 , q 00 ), then p ≤P p0 and p0 ≤ p00 ; and q ≤Q q 0 and q 0 ≤Q q 00 . By
the transitivity of ≤P and ≤Q , we get p ≤ p00 and q ≤ q 00 . Therefore, (p, q) ⩽ (p00 , q 00 ).
• If (p, q) ⩽ (p0 , q 0 ) and (p0 , q 0 ) ⩽ (p, q), then p ≤P p0 and p0 ≤ p; and q ≤Q q 0 and q 0 ≤Q q. By the
antisymmetry of ≤P and ≤Q , p = p0 and q = q 0 . Therefore, (p, q) = (p0 , q 0 ).
P π1 P ×Q π2 Q
π1 and π2 are clearly monotone, since given (p, q) ⩽ (p0 , q 0 ), we have p ≤P p0 and q ≤Q q 0 . So
(p, q) ⩽ p0 , q 0 =⇒ π1 (p, q) ≤P π1 p0 , q 0 .
Therefore, π1 is monotone. Similarly, π2 is also monotone. Now suppose that given another poset
X, there are monotone functions x1 : X → P and x2 : X → Q. We need to show the existence of a
unique monotone function h : X → P × Q such that the following diagram commutes:
X
f g
h (8.15)
P π1 P ×Q π2 Q
134
8 Exponentials 135
for x ∈ X. If x ≤X x0 , then f (x) ≤P f (x0 ) since f is monotone. Similarly, g (x) ≤Q g (x0 ) since g is
monotone. Therefore,
h (x) = (f (x) , g (x)) ⩽ f x0 , g x0 = h x0 .
Therefore, h is monotone. Now,
X
f g
h h0
P π1 P ×Q π2 Q
P π1 P ×Q π2 Q
is a product diagram in Pos. In other words, Pos admits finite products (any singleton {∗} is a
terminal object in Pos). Let us now show that Pos admits exponentials. Given posets P and Q, we
define
QP = HomPos (P, Q) = {f : P → Q | f is monotone } . (8.18)
We put a partial order on QP as follows:
• If f g and g h, then f (p) ≤Q g (p) and g (p) ≤Q h (p) for any p ∈ P . By the transitivity of
≤Q , f (p) ≤Q h (p) for all p ∈ P . Therefore, f h.
• If f g and g f , then f (p) ≤Q g (p) and g (p) ≤Q f (p) for any p ∈ P . By the antisymmetry
of ≤Q , f (p) = g (p) for all p ∈ P . Therefore, f = g.
135
8 Exponentials 136
fe fe×1P f
X X ×P
Then clearly we have ◦ fe × 1B = f , because given any (x, p) ∈ X × P ,
◦ fe × 1P (x, p) = fe (x) , p = fe (x) (p) = f (x, p) . (8.23)
Now we have to show the uniqueness of fe. Suppose g : X → QP is another monotone function such
that ◦ (g × 1B ) = f .
QP × P Q
fe×1P
g×1P
f
X ×P
Since this equality holds for any p ∈ P , we can conclude that g (x) = f (x, −). Therefore, g = fe,
proving the uniqueness of fe. Therefore, QP is indeed an exponential of the objects P and Q in Pos.
Proposition 8.1
In a cartesian closed category (CCC) C, exponentiation by a fixed object A is a functor
(−)A : C → C.
(−)A takes an object B to the exponential B A ; and given an arrow β : B → C in C, (−)A takes
it to
β A := β^
◦ B : B A → C A ,
where B : B A × A → B is the evaluation arrow.
Proof. β A : B A → C A is the unique arrow such that the triangle below commutes:
C
CA CA × A C
βA β A ×1A
β◦B
BA BA × A
136
8 Exponentials 137
β A ×1A β
BA × A B B
Let us now verify the functorial properties of (−)A . Given the identity arrow 1B : B → B, (1B )A is
the unique arrow B A → B A such that the following square commutes:
B
BA × A B
(1B )A ×1A 1B
BA × A B B
1B A ×A =1B A × 1A 1B
BA × A B B
Writing this commutativity in an equation, we get
But (1B )A is the unique arrow such that (8.26) holds. In (8.28), we found that 1B A also satisfies the
same commutativity. Therefore, by the uniqueness, we get
(1B )A = 1B A . (8.29)
BA × A B B CA × A C B BA × A B B
137
8 Exponentials 138
Combining the two commutative squares for β A and γ A , we get the following commutative diagram:
D
DA × A D
γ A ×1A γ
C
CA × A C
β A ×1A β
BA × A B B
So the following square commutes:
D
DA × A D
B
BA × A B
But (γ ◦ β)A is the unique arrow such that (8.30) holds. In (8.33), we found that γ A ◦ β A also satisfies
the same commutativity. Therefore, by the uniqueness, we get
(γ ◦ β)A = γ A ◦ β A . (8.34)
138
9 Naturality
§9.1 The Category of Categories
Let us start by discussing the category Cat of categories and functors. This category has finite
coproducts 0 (the empty category) and C + D; and finite products 1 (the category with only one
object and its identity arrow) and C × D. We can also construct equalizers in Cat as follows: suppose
we are given two parallel functors F, G : C → D. Then we define the category E and functor E,
E F
E C D
G
as follows:
E0 = {C ∈ C0 | F (C) = G (C)}
(9.1)
E1 = {f ∈ C1 | F (f ) = G(f )} ,
and let E : E → C be the inclusion. Then this is an equalizer, which can be easily checked. The
category E is a subcategory of C, i.e. E : E → C is a monomorphism (since it is an equalizer).
is injective.
Example 9.1. A faithful functor need not be injective on arrows. Consider the coproduct of categories
C + C. The objects of this category are of the form (C, 0) or (D, 1), for C, D ∈ C0 . If f : C → D is an
arrow in C, then
(f, 0) : (C, 0) → (D, 0) and (f, 1) : (C, 1) → (D, 1)
are arrows in C + C. The inclusion functors i1 , i2 : C → C + C are defined as
i1 (C) = (C, 0) , i1 (f ) = (f, 0) ; (9.2)
i2 (C) = (C, 1) , i2 (f ) = (f, 1) . (9.3)
Then the “codiagonal functor” ∇ : C + C → C is the unique functor such that the following diagram
commutes:
i1 i2
C C+C C
∇
1C 1C
139
9 Naturality 140
This codiagonal functor ∇ is faithful, but not injective on arrows. If f : C → D is an arrow in C, then
(f, 0) : (C, 0) → (D, 1) is an arrow in C + C, so is (f, 1) : (C, 1) → (D, 1). Then
∇ (f, 0) = ∇ (i1 (f )) = 1C (f ) = f,
∇ (f, 1) = ∇ (i2 (f )) = 1C (f ) = f.
Therefore, ∇ is not injective on arrows. But it is faithful. Given two objects (C, i) and (D, j) in C + C,
with i, j ∈ {0, 1} and C, D ∈ C0 , if i 6= j, then
is a bijection, so it’s clearly injective. Therefore, ∇ is a faithful functor, but not injective on arrows.
A full subcategory U ↣ C consists of some objects of C, and all the arrows between them. For
example, Setsfin is a full subcategory of Sets. The inclusion functor Setsfin ↣ Sets is full and faithful.
On the other hand, the forgetful functor Groups → Sets is faithful but not full. There is another
forgetful functor for groups: Groups → Cat. This is both full and faithful, since a functor between
two groups is exactly the same thing as group homomorphism.
Example 9.2. Let C be a (locally small) category, so that we have the representable functors
for all objects C ∈ C0 . This functor is faithful if and only if for all objects X, Y , the function
is injective (here F = HomC (C, −)). FX,Y is injective if and only if for f, g : X → Y with f 6= g,
FX,Y (f ) 6= FX,Y (g), i.e. F (f ) 6= F (g). But F (f ) and F (g) are both functions from HomC (C, X)
to HomC (C, Y ). Two functions are unequal if and only if there exists some input where the functions
don’t agree. Therefore, F (f ) 6= F (g) if and only if there is some x ∈ HomC (C, X) such that
F (f ) (x) 6= F (g) (x). But since F = HomC (C, −),
Similarly, F (g) (x) = g ◦ x. Therefore, HomC (C, −) is faithful if and only if for all objects X, Y and
arrows f, g : X → Y with f 6= g, there exists an arrow x : C → X such that f ◦ x 6= g ◦ x.
Example 9.3. Let G be a group in a (locally small) category C. Then the contravariant representable
functor HomC (−, G) has a group structure, so that we have a functor
For example, if C = Sets, then for each set X, we can define the group operation on HomSets (X, G)
pointwise:
140
9 Naturality 141
• Let e ∈ G be the identity element. Then the identity element of HomSets (X, G) is the function
u : X → G that sends all x ∈ X to e ∈ G.
• The inverse of f ∈ HomSets (X, G) is the function g : X → G such that
g (x) = f (x)−1 . (9.7)
such that ϕ (x) ∈ Gx for every x ∈ X. In our case, Gx = G for all x ∈ X. Therefore, the elements of
Q
the product x∈X G are all the functions ϕ : X → G, so that the isomorphism in (9.8) holds.
Furthermore, given any function h : X → Y , h∗ : HomSets (Y, G) → HomSets (X, G) is a group
homomorphism. Indeed, given any f, g : Y → G,
[h∗ (f ?Y g)] (x) = [(f ?Y g) ◦ h] (x)
= (f ?Y g) (h (x))
= f (h (x)) ∗G g (h (x))
= [f ◦ h ?X g ◦ h] (x)
= [h∗ (f ) ?X h∗ (g)] (x) .
Therefore,
h∗ (f ?Y g) = h∗ (f ) ?X h∗ (g) , (9.9)
i.e. h∗ is a group homomorphism. So we say that the contravariant functor HomSets (−, G) "captures"
the group structure of G.
The group structure is not particularly a special structure. We can do the above for pretty much any
algebraic structure. For instance, R has a ring structure, and using that ring structure, we can form the
ring HomTop (X, R) of all the continuous functions from the topological space X to R. HomTop (X, R)
is also written C (X). The ring structure of HomTop (X, R) is inherited from that of R (the addition
and multiplication are defined pointwise, in a similar manner as before). In this case as well, given a
continuous function h : X → Y , the function
h∗ : HomTop (Y, R) → HomTop (X, R)
is a ring homomorphism.
However, not all algebraic structures are preserved. For instance, R has the structure of a field, but
HomTop (X, R) is not a field. We can consider X = R, and the continuous function f (x) = x. Then
f 6= 0, but f has no multiplicative inverse in HomTop (X, R).
§9.2 Naturality
We have already defined natural transformation in Definition 3.10. Let us recall the definition once
again.
Definition 9.2 (Natural Transformation). Let F and G be two functors between the categories C
and D. Then a natural transformation η : F ⇒ G is a family of arrows
141
9 Naturality 142
F (f )
F (X) F (Y )
ηX ηY
G(X) G(Y )
G(f )
Example 9.4. Consider the free monoid M (X) on a set X, and let U : Sets → Sets be the functor
that takes a set X to the underlying set of its free monoid, i.e. U (X) = |M (X)|. Let us see the
action of U on functions. Suppose f : X → Y is a function between sets. Let iX : X → |M (X)| and
iY : Y → |M (Y )| be the insertion of generators. Then we have a function iY ◦ f : X → |M (Y )|. By
the UMP of a free monoid, there exists a unique monoid homomorphism fe : M (X) → M (Y ) such
that the following diagram commutes in Sets:
fe
|M (X)| |M (Y )|
iX iY
X f
Y
ηX ηY
U (X) = |M (X)| U (Y ) = |M (Y )|
U (f )= fe
Example 9.5. Let C be a category with products. In § [Link], we have seen a functor
× : C × C → C.
Then we define a “twist” natural transformation t : × ⇒ × as follows: given the product diagrams
π1 π2
A A×B B
p1 p2
B B×A A,
we take t(A,B) : A × B → B × A to be the unique arrow such that the following diagram commutes:
A×B
π2 t(A,B) π1
B p1 B×A p2 A
142
9 Naturality 143
In other words,
p1 ◦ t(A,B) = π2 and p2 ◦ t(A,B) = π1 . (9.11)
In order to show that t : × ⇒ × is a natural transformation, we need to show the commutativity of
the following diagram, given arrows α : A → A0 and β : B → B 0 in C:
α×β
A×B A0 × B 0
t(A,B) t(A0 ,B 0 )
B×A β×α
B 0 × A0
A×B
β◦π2 α◦π1
u
B0 B 0 × A0 A0
p01 p02
In other words,
p01 ◦ u = β ◦ π2 and p02 ◦ u = α ◦ π1 . (9.12)
Now, in light of the following commutative diagrams,
π1 π2
A×B A A×B B
π2 t(A,B) π1 α β
α×β
p1 p2 π10 π20
B B×A A A0 A0 × B 0 B0
β β×α α t(A0 ,B 0 )
p02 p01
B0 B 0 × A0 A0 B 0 × A0
p01 p02
we can see that both (β × α) ◦ t(A,B) and t(A0 ,B 0 ) ◦ (α × β) fits the requirement of (9.12). Therefore,
by the uniqueness of u,
(β × α) ◦ t(A,B) = u = t(A0 ,B 0 ) ◦ (α × β) , (9.13)
and hence t : × ⇒ × is a natural transformation.
Definition 9.3 (Functor Category). The functor category Fun (C, D) has
• Objects: functors F : C → D
143
9 Naturality 144
F
η
G
C D
ϑ
has components
(ϑ ◦ η)C = ϑC ◦ ηC .
Lemma 9.1
A natural transformation ϑ : F ⇒ G is a natural isomorphism if and only if each componenet
ϑC : F (C) → G (C) is an isomorphism.
Proof. Suppose ϑ is a natural isomorphism, i.e. an isomorphism in Fun (C, D). Then there is another
natural transformation η : G ⇒ F such that ϑ ◦ η = 1G and η ◦ ϑ = 1F . Then for each C ∈ C0 ,
Conversely, suppose ϑC : F (C) → G (C) is an isomorphism for each C ∈ C0 . Then we define another
natural transformation η : G ⇒ F , whose components are ηC = ϑ−1C . One can easily check that η is a
natural transformation. For that purpose, we need to show the commutativity of the following square
given any arrow f : X → Y in C:
F (f )
F (X) F (Y )
ϑ−1
X ϑ−1
Y
(9.15)
G(X) G(Y )
G(f )
ϑX ϑY
G(X) G(Y )
G(f )
In other words,
ϑY ◦ F (f ) = G (f ) ◦ ϑX . (9.16)
Composing with ϑ−1
Y to the left and ϑ−1
X to the right, we get
F (f ) ◦ ϑ−1 −1
X = ϑY ◦ G (f ) . (9.17)
144
9 Naturality 145
Example 9.6. Consider the category VectR of real vector spaces and linear transformations f : V →
W . Every vector space has a dual space
ηV : V → V ∗∗
x 7→ (evx : V ∗ → R) ,
where evx (ϕ) = ϕ (x) for every ϕ : V → R. This map ηV is the component of a natural transformation
η : 1VectR ⇒ (−)∗∗ ,
ηV ηW (9.20)
V ∗∗ f ∗∗
W ∗∗
Both evf (x) and evx ◦ f ∗ are elements of W ∗∗ , i.e. they are linear maps W ∗ → R. Now, given any
ψ ∈ W ∗ , ψ : W → R is a linear map. Now,
f ∗∗ ◦ ηV = ηW ◦ f. (9.24)
Therefore, (9.20) commutes, so that η : 1VectR ⇒ (−)∗∗ is a natural transformation. When V is finite
dimensional, ηV is an isomorphism, so
η : 1Vectfin ⇒ (−)∗∗
R
145
9 Naturality 146
F (α,B) F (α,B 0 )
F (A0 , B) F (A0 , B 0 )
F (A0 ,β)
(A0 , B) (A0 , B 0 )
(1A0 ,β)
146
9 Naturality 147
Similarly,
F (A0 , B) F (A0 , B 0 )
F (1A0 ,β)
Therefore,
F −, B 0 (α) ◦ F (A, −) (β) = F A0 − (β) ◦ F (−, B) (α) , (9.29)
i.e. the interchange law holds.
for (A, B) ∈ (A × B)0 and arrow (α, β) : (A, B) → (A0 , B 0 ). Let us now check the functorial properties.
Suppose 1(A,B) = (1A , 1B ) is the identity arrow of the object (A, B) ∈ (A × B)0 . Then,
F 1(A,B) = F (1A , 1B ) = F (A, −) (1B ) ◦ F (−, B) (1A )
= 1F (A,−)(B) ◦ 1F (−,B)(A)
= 1F (A,B) ◦ 1F (A,B)
= 1F (A,B) . (9.32)
Now, using the following commutative diagram (commutativity is guaranteed by the interchange law
(9.31)),
F (A,−)(β 0 ◦β)
F (A, B) F (A, B 00 )
F (A00 , B) F (A00 , B 00 )
F (A00 ,−)(β 0 ◦β)
F (α0 , β 0 ) ◦ (α, β) = F α0 ◦ α, β 0 ◦ β
= F A00 , − β 0 ◦ β ◦ F (−, B) α0 ◦ α
= F A00 , − β 0 ◦ F A00 , − (β) ◦ F (−, B) α0 ◦ F (−, B) (α) . (9.33)
147
9 Naturality 148
F (A0 ,−)(β)
F (A0 , B) F (A0 , B 0 )
F (A00 , B) F (A00 , B 0 )
F (A00 ,−)(β)
F A00 , − (β) ◦ F (−, B) α0 = F −, B 0 α0 ◦ F A0 , − (β) . (9.34)
Plugging (9.34) into (9.33), we get
F (α0 , β 0 ) ◦ (α, β) = F A00 , − β 0 ◦ F −, B 0 α0 ◦ F A0 , − (β) ◦ F (−, B) (α) . (9.35)
Now we shall use interchange law once again.
F (A,−)(β) F (A0 ,−)(β 0 )
F (A, B) F (A, B 0 ) F (A0 , B 0 ) F (A0 , B 00 )
Therefore,
F (α, β) = F A0 , − (β) ◦ F (−, B) (α) , (9.36)
0 0 00 0 0 0
F α ,β = F A ,− β ◦ F −, B α . (9.37)
Now plugging (9.36) and (9.37) into (9.35), we get
F (α0 , β 0 ) ◦ (α, β) = F (α0 , β 0 ) ◦ F (α, β). (9.38)
Therefore, F : A × B → C is a functor. ■
Theorem 9.3
Cat is cartesian closed, with the exponential
DC = Fun (C, D) .
ϑC ϑC 0
G(C) G(C 0 )
G(f )
148
9 Naturality 149
We shall use Bifunctor Lemma to prove that is a functor. First, we need to show that is functorial
in each argument. If we fix a functor F : C → D, then
(F, −) : C → D
takes an object F ∈ Fun (C, D)0 , i.e. a functor F : C → D, to F (C). Furthermore, it takes an arrow
ϑ : F ⇒ G to
(−, C) (ϑ) = (ϑ, 1C ) = G (1C ) ◦ ϑC = 1G(C) ◦ϑC = ϑC . (9.42)
So (−, C) (ϑ) is just the component of ϑ at C. As a result, (−, C) is also a functor.
Now we need to verify interchange law. Let ϑ : F ⇒ G be a natural transformation, and f : C → C 0
be an arrow in C. We need to verify that
(G, −) (f ) ◦ (−, C) (ϑ) = −, C 0 (ϑ) ◦ (F, −) (f ) .
(G, C) (G, C 0 )
(G,−)(f )
F (f )
F (C) F (C 0 )
ϑC ϑC 0 (9.43)
G(C) G(C 0 )
G(f )
(9.43) clearly commutes since ϑ is a natural transformation. Therefore, interchnage law holds, and
hence : Fun (C, D) × C → D is a functor.
Given any category X and a functor F : X × C → D, we need to show the existence of a unique
functor Fe : X → Fun (C, D) such that
F = ◦ Fe × 1C .
e×1C
F F
X ×C
149
9 Naturality 150
η is indeed a natural transformation from F (X, −) to F (Y, −), since the following diagram commutes
(commutativity is guaranteed by interchange law, since F is a bifunctor) for any arrow α : C → C 0 in
C:
F (X,−)(α)
F (X, C) F (X, C 0 )
F (Y, C) F (Y, C 0 )
F (Y,−)(α)
So we define
Fe (f ) = (η : F (X, −) ⇒ F (Y, −)) ∈ Fun (C, D)1 . (9.46)
In other words,
Fe (f ) = F (−, C) (f ) .
C
This is clearly functorial since F (−, C) : X → D is a functor. So we have constructed the functor Fe .
Now, given any X ∈ X0 and C ∈ C0 ,
h i
◦ Fe × 1C (X, C) = Fe (X) , C = F (X, −) (C) = F (X, C) . (9.47)
where the last equality follows from the interchange law of the bifunctor F .
F (X,−)(α)
F (X, C) F (X, C 0 )
F (Y, C) F (Y, C 0 )
F (Y,−)(α)
Therefore,
◦ Fe × 1C = F, (9.50)
on both objects and arrows. Now we need to show the uniqueness of Fe . Suppose there is another
functor G : X → Fun (C, D) such that ◦ (G × 1C ) = F , i.e. the following diagram commutes
Fun(C, D) × C D
G×1C
F
X ×C
150
9 Naturality 151
^
Then F = ◦ (G × 1C ). We shall now look at the exponential transpose of ◦ (G × 1C ). Write
e : X → Fun (C, D) is an arrow (defined as above) such that
H := ◦ (G × 1C ) : X × C → D. Then H
the following diagram commutes
Fun(C, D) × C D
e C
H×1 H
X ×C
Now, for any X ∈ X0 , using (9.44),
e (X) = H (X, −) = [ ◦ (G × 1C )] (X, −) = (G (X) , −) = G (X) .
H (9.51)
Therefore,
e (f )
H = G (f )C (9.54)
C
e (f ) = G (f ) for all f ∈ X1 . Hence, H
for all C ∈ C0 . Therefore, H e = G both at the object and arrow
level. But since H := ◦ (G × 1C ) = F ,
G=H e = Fe . (9.55)
Therefore, Fe = G, so that Fe is unique. So the UMP of exponential is satisfied, and thus Cat is a
CCC. ■
151