Exercise sessions for the Category Theory course,
fall semester 2020-21
Giulio Lo Monaco
Week 1
Exercise Define Rel as follows: its objects are sets, and a morphism A → B is a
relation, that is, a subset R ⊆ A × B. Moreover, define the identity on A
to be the diagonal relation {(a, a) ∈ A × A|a ∈ A}, and the composition
of R ⊆ A × B and S ⊆ B × C as
S ◦ R = {(a, c) ∈ A × C|∃b ∈ B such that (a, b) ∈ R and (b, c) ∈ S}.
Prove that Rel is a category.
Solution First prove the identity axiom. We need to show that for any R ⊆ A × B,
then idB ◦ R = R. The dual is similar. Now
idB ◦ R = {(a, b)|∃b ∈ B such that (a, b ) ∈ R and (b , b) ∈ idB}
but (b , b) ∈ idB if and only if b = b so the condition reduces to ∃b ∈ B
such that (a, b) ∈ R. This is precisely R.
Now we show associativity: choose R ⊆ A×B, S ⊆ B ×C and T ⊆ C ×D
and compute
(T ◦ S) ◦ R = {(a, d) ∈ A × D|∃b ∈ B such that (a, b) ∈ R and (b, d) ∈ T ◦ S}
= {(a, d) ∈ A × D|∃b ∈ B, ∃c ∈ C such that (a, b) ∈ R, (b, c) ∈ S and (c, d) ∈ T}
= {(a, d) ∈ A × D|∃c ∈ C, ∃b ∈ B such that (a, b) ∈ R, (b, c) ∈ S and (c, d) ∈ T}
= {(a, d) ∈ A × D|∃c ∈ C such that (a, c) ∈ S ◦ R and(c, d) ∈ T}
= T ◦ (S ◦ R)
Examples Other commonly used categories:
• Grp, objects are groups and morphisms are group homomorphisms;
• Ab, objects are abelian groups and morphisms are group homomor-
phisms;
• Top, objects are topological spaces and morphisms are continuous
maps;
• Met, objects are metric spaces and morphisms are contractions;
1
• Haus, objects are Hausdorff spaces and morphisms are continuous
maps;
• Pos, objects are partially ordered sets and morphisms are orderpreserving
maps.
Example In all the examples above, objects are defined as sets with additional
structure put on them. Morphisms are functions between the underlying
sets which preserve the additional structure. Can we do something similar
for categories? We would like to define a “morphism” between categories
as a function on objects plus a function on morphisms in a way that the
structure of category is preserved.
Definition A functor F : A → B between categories consists of a function F0 : obA →
obB and another function F1 : arA → arB in such a way that for each
objects A, B, C ∈ A and morphisms f : A → B and g : B → C
• domF1(f) = F0(A);
• codF1(f) = F0(B);
• F1(g) ◦ F1(f) = F1(g ◦ f);
• F1(idA) = idF0(A).
Example Let P be a partially ordered set. Then we can define a category ˜P as
follows: the objects of ˜P are exactly the points of P. For two p, q ∈ P, the
set of morphisms from p to q will be a singleton if p ≤ q, empty otherwise.
In other words
• ˜P(p, q) = {(p, q)} whenever p ≤ q;
• ˜P(p, q) = ∅ whenever p q.
If P and Q are posets, then a functor ˜P → ˜Q corresponds precisely with
an order-preserving map P → Q.
Example Let M be a monoid. Then we can define a category BM as follows:
obBM = {∗}, that is, there is just one object, so we only need to specify
one set of morphisms, and we set BM(∗, ∗) = M. Composition and
identity are given by:
• ∀m, n ∈ M, n ◦ m = mn
• id∗ = 1M .
This gives indeed the structure of a category. Moreover, if M and N are
monoids, then a functor BM → BN corresponds precisely with a monoid
homomorphism M → N.
Exercise Show that monomorphisms and epimorphisms in Set correspond respectively
to injections and surjections.
2
Solution We need to show Mono ⊆ Inj, Inj ⊆ Mono, Epi ⊆ Surj and Surj ⊆ Epi.
Take a monomorphism f : A → B. Consider two points a, a ∈ A such
that f(a) = f(a ). If ∗ is a singleton, there are two maps ga, ga : ∗ → A
selecting a and a respectively. By hypothesis, fga = fga which implies
ga = ga since f is monic. But this means that ga and ga select the same
point, so that a = a .
Now suppose that f is injective, and choose maps
C A B.
g
h
f
such that fg = fh. This means that for every element c ∈ C we have
fg(c) = fh(c). By injectivity of f this implies g(c) = h(c).
Now assume f is epic. Consider the set B/f(A) of equivalence classes of
points of B under the relation b ∼ b if and only if either both are in the
image of f, or b = b . Let us now take the maps
A B B/f(A)
f p
c
where p is the projection on the quotient and c is constant on the equivalence
class determined by f(A). Clearly, we have pf = cf. Since f is epic,
this implies p = c which means that every point of B is in f(A). Thus f
is surjective.
Finally, assume that f is surjective, and consider two maps g, h : B → C
such that gf = hf. For each b ∈ B, by surjectivity of f there is some
a ∈ A such that f(a) = b, so we can compute
g(b) = gf(a) = hf(a) = h(b)
which means that g = h. We are finished.
Exercise Let Mon be the category of monoids and monoid homomorphisms. Prove
that in Mon the inclusion N → Z is an epimorphism.
Solution Consider two morphisms f, g : Z → M such that f(n) = g(n) whenever n
is a natural number. It remains to show that the equality holds also for
negative integers. Observe that if h : P → Q is any monoid homomorphism
and p ∈ P has an inverse −p, then h(−p) = −h(p). Using this fact,
we compute
f(−n) = −f(n) = −g(n) = g(−n)
in our case, which completes the proof that f = g.
Definition We say that a category C is balanced if whenever a morphism is both a
monomorphism and and epimorphism then it is an isomorphism.
3
Example We (almost) proved above that the category Set is balanced. Indeed, if a
morphism is both mono and epi, then it is an injection and a surjection,
which means it is a bijection of sets. Isomorphisms in Set are precisely
bijections.
We have also seen that the inclusion N → Z is an epimorphism in Mon.
Moreover, it is a monomorphism, because monomorphisms in Mon are
precisely injective homomorphisms. So Mon is not balanced.
For a similar reason (for instance, take the inclusion Z → Q) the category
CRng of commutative rings and ring homomorphisms is not balanced.
Example For a poset P, the category ˜P is not balanced. Indeed, every morphism
in ˜P is both monic and epic, but the only isomorphisms are identities.
Example There is an inclusion Haus ⊂ Top. We have that a morphism which is
epic in Haus is not necessarily so in Top.
Exercise Prove that epimorphisms in Haus are exactly dense maps, and say why
this is not the case in Top.
Solution Let f : X → Y be a dense map of Hausdorff spaces, and let g, h : Y → Z
be two other continuous maps of Hausdorff spaces such that gf = hf.
Let us choose any point y ∈ Y . Since f is dense, there is a sequence of
points in X such that limn→+∞ f(xn) = y. Moreover, since g and h are
continuous, they preserve limits. So we have
g(y) = g(lim f(xn)) = lim gf(xn) = lim hf(xn) = h(lim f(xn)) = h(y).
Conversely, suppose that f is an epimorphism. If f(X) is the closure of
f(X) in Y , then we take the disjoint union of two copies of Y and put
an equivalence relation on it as follows: two points (x, i) and (y, j) are
equivalent if either (x, i) = (y, j) or x = y ∈ f(X). In other words, we
are gluing the two copies along the common subspace f(X). We call the
quotient Q, and observe that it is a Hausdorff space. In particular there
are two maps p1, p2 : Y → Q, given by the projection on the quotient
of the two distinct copies of Y . Clearly, we have p1f = p2f so that by
assumption we obtain p1 = p2. Since the two maps are only equal on
f(X), this means that Y = f(X), which is exactly saying that f is dense.
In Top, the first direction doesn’t work because limits are not unique
even when they exist in general topological spaces. The second direction
actually works, but in addition we may consider the two maps p, c : Y →
Y/f(X) just as we did in the case of sets, which is not possible in Haus
because that quotient is in general not a Hausdorff space, and this gives
strict surjectivity.
Exercise Prove that neither Top nor Haus are balanced.
Solution In Top, consider for instance this map: for a non-trivial set X, call Xd
the discrete space and Xi the indiscrete space on X, and take the identity
map Xd → Xi. This is continuous and bijective (therefore both monic
and epic), but it is not an isomorphism because its set-theoretical inverse
is not continuous.
4
In Haus, consider for instance the inclusion { 1
n }n∈N → { 1
n }n∈N∪{0}, with
the canonical topology. This is dense, therefore epic, and an inclusion,
therefore monic, but not an isomorphism since not surjective.
Exercise What are the initial and terminal objects of Set, Mon, Grp, Top, CRng,
˜P, Rel?
Solution In Set, the initial object is ∅, because for any other set X the only map
∅ → X is the vacuous map. A terminal object is any singleton ∗, because
for any other map X the only map X → ∗ is the map sending every element
of X to the only point of ∗.
In Mon, the one-point monoid 0 is both initial and terminal. In particular,
it is initial because every monoid homomorphism preserves the unit 0.
In Grp, the one-point group 0 is both initial and terminal, as above.
In Top, the initial and terminal object are as in Set, that is, the empty
space and the one-point space.
In CRng, the terminal object is the one-point ring 0, as above. The initial
object is Z. To see this, observe that, if R is any commutative ring, than
a ring homomorphism f : Z → R is required to send 0 to 0R and 1 to 1R.
Moreover, f preserves sums, so that for every n ∈ Z+
we have
f(n) = f(1 + . . . + 1) = f(1) + . . . + f(1) = 1R + . . . + 1R
and finally it preserves additive inverses, so that we have a similar formula
for negative integers. In other words, if a homomorphism f exists, then it
is forced to be of the form above. We conclude by saying that this definition
of f gives indeed a ring homomorphism because it clearly preserves
sums and, since products in Z can be expressed in terms of sums, it also
preserves products.
In ˜P, an initial and a terminal object correspond respectively to a minimum
element and to a maximum element.
In Rel, ∅ is both initial and terminal. To see this, it suffices to observe
that for any other set A, the equalities
A × ∅ = ∅ = ∅ × A
which only has the trivial subset.
Definition We define the dual of a category C as follows: the objects of Cop
are exactly
those of C; for two objects A, B ∈ C, the set of morphisms A → B in Cop
is exactly the set of morphisms B → A in C. We write:
• obCop
= obC;
• ∀A, B ∈ obCop
, Cop
(A, B) = C(B, A).
5
Week 2
Exercise Show that the following are equivalent for an arrow f : A → B:
1. f is an isomorphism;
2. f is a monomorphism and a split epimorphism;
3. f is a split monomorphism and an epimorphism;
4. f is a split monomorphism and a split epimorphism.
Solution If f is iso, this trivially implies all the other conditions. Assume that f is
mono and split epi. Then there is a map s : B → A such that fs = idB.
Therefore, we also have fsf = f which, since f is mono, implies sf = idA,
and f is iso. The case of split mono + epi is analogous.
Solution Show that all sets are projective.
Solution Choose a diagram
A
X B
f
h
where f is epi. For each x ∈ X, we choose an element a ∈ A such that
f(a) = h(x). This defines a function g : X → A such that fg = h.
Exercise Show that a retract of a projective object is also projective.
Solution Let X be projective, and Y a retract of X, so that there are maps r :
X → Y and s : Y → X with rs = idY . Suppose we have a diagram
A
X Y B.
f
r h
g
Since X is projective, there exists a lift g : X → A such that fg = hr.
Now we have fg s = hrs = h, so that g s is the desired lift.
Exercise For an arrow f : A → B in a category, show that the arrow (idA, f) : A →
A × B is a monomorphism.
Solution Consider two arrows g, h : D → A such that (idA, f) ◦ g = (idA, f) ◦ h.
By universal property of the product we know that πA ◦ (idA, f) = idA,
where πA : A × B → A is the projection from the product. In particular,
postcomposing with πA we obtain g = h.
Example Given a family of objects (Ai)i∈I in a category C, take their product
i∈I Ai, with projections πj : i∈I Ai → Aj. Given any other object B,
we can evaluate the functor C(B, −) at these maps, obtaining
C(B, πj) : C(B, i∈I Ai) → C(B, Aj).
6
The universal property of products in Set then yields a map
φ : C(B, i∈I Ai) → i∈I C(B, Ai).
The universal property of products in C says exactly that φ is an isomorphism
of sets.
Exercise Show that the forgetful functor U : Mon → Set, taking every monoid to
its underlying set, is representable. Infer that it preserves products.
Solution For a monoid M, consider the set Mon(N, M). We will prove that this
is isomorphic to M. To a morphism f : N → M we will associate f(1) ∈
M. Viceversa, for an element m ∈ M, we define a homomorphism by
imposing f(1) = m. By homomorphism property, necessarily f(0) = 0M
and f(n) = m+. . .+m. Since this is always a well-defined homomorphism
and it is the only possible choice, we are done. So U is represented by the
object N.
By the example above, this implies that U preserves products.
Definition Given two categories C and D and two functors F, G : C → D, a natural
transformation α : F ⇒ G is an assignment of an arrow αC : F(C) →
G(C) in D for every object C ∈ C, in such a way that, for every morphism
f : C → D in C, the square
F(C) F(D)
G(C) G(D)
αC
F (f)
αD
G(f)
commutes.
Example Many processes give rise to natural transformations:
– Given a functor F : C → D, the identity morphism F(C) → F(C) is
a natural transformation id : F ⇒ F;
– the projection from a group onto its abelianization G → Gab
is a
natural transformation idGrp ⇒ (−)ab
;
– the diagonal map X → X ×X of sets, groups, spaces and many other
structures is a natural transformation from the identity fuctor to the
functor sending X to X × X and f to f × f;
– the inclusion X → X {∗} of a set, or topological space, into the set
(space) obtained by adjoining one point is a natural transformation
id ⇒ (−) {∗};
– given a set A and a category C, we can take an arbitrary functor
F : A → C (where A is regarded as a category only containing identity
morphisms). Moreover, choosing an object C ∈ C, there is a constant
functor δC : A → C. Then a natural transformation F ⇒ δC
corresponds to the choice of morphisms F(a) → C, for every a ∈ A;
– later on we will see many other useful examples in the theory of
limits.
7
Definition A natural isomorphism α : F ⇒ G is a natural transformation where each
of the components αC is an isomorphism.
Example The classical example of natural isomorphism is that from a vector space
to the double dual. The components φV : V → V ∗∗
assemble to form a
natural transformation id ⇒ (−)∗∗
.
Definition Given two categories C and D, we say that two functors F : C D : G
form an equivalence if there are natural isomorphisms idC ⇒ GF and
idD ⇒ FG.
Definition We define a category CABA. A complete Boolean algebra is a poset A
that has all meets and all joins and such that for every element a ∈ A
there is an element ¬a ∈ A such that a ∨ ¬a = 1 and a ∧ ¬a = 0. An
atom is an element that is minimal in A \ {0} with respect to the order
relation. A complete Boolean algebra is atomic if each element b ∈ A
can be expressed as b = i∈I ai, where ai’s are atoms. A morphism of
complete atomic Boolean algebras is a function that preserves order, meets
and joins.
Exercise Let B be a complete atomic Boolean algebra. Prove that if a is an atom,
then a b ⇔ a ∧ b = 0.
Solution Observe that, for general a, b, we have a ≤ b ⇔ a ∧ b = a. Now compute
a b ⇔ a ∧ b = a ⇔ a ∧ b = 0
where the first step is the observation above, the second is true because a
is an atom.
Exercise Prove that if B is an complete atomic Boolean algebra, S ⊆ B and a ∈ B
is an atom, then a ≤ S implies that there is an element b ∈ S such that
a ≤ b.
Solution Suppose by contradiction that for all b ∈ S then a b. By the previous
exercise, we have that for all b ∈ S, a ∧ b = 0. Then we compute
a ∧ S = S(a ∧ b) = S 0 = 0
which is a contradiction because we know that a ∧ S = a.
Exercise Prove that if f : A → B is a morphism of complete atomic Boolean
algebras, and b ∈ B is an atom, then there is a unique atom a ∈ A such
that b ≤ f(a).
Solution Since A is atomic, we have 1A = {a ∈ A|a is an atom}. Since f preserves
all joins, we also have 1B = f(1A) = {f(a) ∈ B|a ∈ A is an atom}.
Now, if b ∈ B then b ∈ 1B. Taking S = {f(a) ∈ B|a ∈ A is an atom},
then we can use the previous exercise to conclude that there is an atom
a ∈ A such that b ≤ f(a). It remains to show that this atom is unique.
Suppose that there is another atom a with the property that b ≤ f(a ),
then
8
b ≤ f(a) ∧ f(a ) = f(a ∧ a ) = f(0) = 0
which is impossible. Therefore, there is only one atom with this property.
Exercise Prove that there is an equivalence between the category Setop
of sets and
opposite functions and the category CABA of complete atomic Boolean
algebras.
Solution We need two functors Setop
→ CABA and CABA → Setop
. For each set
X, take the power set PX, and for a function f : X → Y , take the inverse
image f−1
: PY → PX. We verify that this is a well-defined functor
P : Setop
→ CABA. For each set, its power set is a poset via the inclusion
relation and, moreover, joins are given by unions and meets are given by
intersections. Atoms are precisely singleton. In fact, there are no subsets
between ∅ and a singleton, and if a subset S is not a singleton, we can
always take out an element to obtain a subset S \ {s} which sits between
∅ and S. Now, every subset S ⊂ X is given by the union x∈X{x}, so
PX is also atomic. The inverse image maps preserves inclusions, unions
and intersections, so it is a morphism in CABA. Functoriality is readily
verified.
For the next step, we need a functor At : CABA → Setop
. For a
complete atomic Boolean algebra B, At B will be the set of atoms of B.
For a morphism h : A → B in CABA, we define At h : At B → At A as
follows: given an atom b ∈ B, by the previous exercise there is a unique
atom a ∈ A such that b ≤ h(a). Now we set At h(b) = a. Functoriality
follows by the fact that there is always only one possible such atom.
Now we define two natural isomorphisms φ : idSetop ⇒ At P and ψ :
PAt ⇒ idCABA. For a set X, At PX is the set of all singletons of
elements of X. Now φX : X → At PX is the map which sends a point
x to {x}. This is clearly an isomorphism. For the naturality condition,
observe that for a function f : X → Y , then by definition of At , the map
At Pf : At PX → At PY sends a singleton {x} to the only singleton
{y} such that {x} ⊆ f−1
(y). Therefore it must be y = f(x), and we have
At Pf : {x} → {f(x)}. The commutativity of the diagram
X Y
At PX At PY
f
φX φY
At Pf
now follows trivially.
For a complete atomic Boolean algebra A, PAt A is the power set of atoms
of A. Now we will define ψ as follows: given a set S of atoms of A, so
that S ∈ PAt A, we send it to S ∈ A. Observe that if S ⊆ S then
S ≤ S , so ψA preserves the order relation. Moreover,
i∈I Si = i∈I S;
i∈I Si = i∈I Si,
so it also preserves joins and meets.
Also, ψA is surjective because A is atomic. Let us prove that it is injective.
9
For two sets of atoms S = S , there must be at least one atom a such that
a ∈ S and a /∈ S . This means in particular that a ≤ ψA(S). We will
see that a ψA(S ). Indeed, if we suppose a ≤ ψA(S ) = S , then the
previous exercise says that there is a ∈ S such that a ≤ a , but this is
impossible since a is an atom. So ψA is an isomorphism. Finally, we need
to show that it is natural, that is, that the diagram
PAt A PAt B
A B
PAt h
ψA ψB
h
commutes. Observe that if S is a set of atoms of A, then PAt h(S) is the
set T := {b ∈ At B|∃a ∈ S such that b ≤ h(a)}. Now compute
ψB ◦ PAt h(S) = ψB(T) = T
h ◦ PAt A(S) = h( S) = h(S).
so we need to show that T = h(S).
For each b ∈ T, then there is a ∈ S such that b ≤ h(a) ≤ h(S), which
implies T ≤ h(S).
Conversely, if h(a) ∈ h(S), since B is atomic h(a) is a join of atoms. In
particular, h(a) = {b ∈ At B|b ≤ h(a)}, so it is the join of a subset of
T, so also h(a) ≤ T. Again, this implies h(S) ≤ T. This concludes
the proof.
Week 3
Example We know that the Yoneda lemma states that, for a functor C → Set,
where C is a small category, then there is a natural bijection
F(C) ∼= Nat(C(C, −), F)
for each object C ∈ C. In particular, if F = C(D, −), this means that
there is a bijection
C(D, C) ∼= Nat(C(C, −), C(D, −))
which is natural in both C and D. What does this mean? There are two
functors
Cop
× C Set
C(−,−)
Nat(C(C,−),C(D,−))
and the bijection above is a natural transformation between these two.
Exercise Show that in a category C, if two objects C and C are such that for any
other object D we have natural bijections
10
C(C, D) ∼= C(C , D)
then we also have C ∼= C .
Solution We know that the natural isomorphism φ : C(C, −) → C(C , −) must
be represented by a unique morphism f : C → C. Moreover, its inverse
ψ : C(C , −) → C(C, −) is uniquely represented by a morphism g : C → C .
We will show that f and g are inverse to each other.
Consider the map f ◦ g : C → C. This induces a map C(C, −) → C(C, −)
but, since the Yoneda isomorphism is natural, this map must be exactly
φ◦ψ. Since φ and ψ are inverse to each other by hypothesis, we have that
φ ◦ ψ = idC(C,−), so we obtained that the map represented by f ◦ g is the
identity. But now, idC : C → C also represents the identity on C(C, −),
and we know that the representing morphism is unique. This implies that
f ◦ g = idC.
Analogously, we prove that g ◦ f = idC .
Exercise (Full + faithful = injective up to iso). Let F : C → D be a functor.
Prove that, if F is full and faithful, then C ∼= C ∈ C if and only if
F(C) ∼= F(C ) ∈ D.
Solution Assume that C ∼= C . Let D ⊆ D be the image of F, i.e. the full
subcategory of D spanned by all objects of the form F(C ) for some
C ∈ C. Observe that F(C) and F(C ) are isomorphic in D if and only
if they are isomorphic in D . Now we have by the exercise above that
C ∼= C if and only if C(C, −) ∼= C(C , −) if and only if D (F(C), −) ∼=
D (F(C ), −) because F is full and faithful, and finally this is true if and
only if F(C) ∼= F(C ) again by the exercise above.
Example Observe that, if instead of starting off with C we take Cop
instead, we
will obtain a dual Yoneda embedding. This means that, for a functor
F : Cop
→ Set, there are natural bijections
F(C) ∼= Nat(C(−, C), F)
and in particular, when F = C(−, D), we have natural bijections
C(C, D) ∼= Nat(C(−, C), C(−, D))
for all C, D ∈ C.
Exercise Show that in a Cartesian closed category C every object C defines a functor
C(−)
: Cop
→ C.
Solution We first define it on objects, which is easy: just set B → CB
. For a
morphism f : A → B, we need to define a morphism Cf
: CB
→ CA
.
Such morphisms are in natural bijection with morphisms A × CB
→ C,
so it suffices to give one of these. Let us take
A × CB
B × CB
C.
f×CB
ev
11
Let’s prove that this assignment preserves identities. If f = idB, the map
defined above is precisely ev. We need to prove that the universal property
of exponentials associates ev to idCB . This is clear since the diagram
CB
× B C
CB
× B
ev
idCB ×idB ev
obviously commutes.
Now consider two morphisms f : A → B and g : B → D. We want to
show that Cgf
= Cf
Cg
. Again, it suffices to show that the associated
maps CD
× A → C are equal. First observe that there is a square
CD
× B CD
× D
CB
× B C
Cg
×B
CD
×g
ev
ev
which commutes by definition of Cg
, so we have ev◦(CD
×g) = ev◦(Cg
×
B). For the same reason, we have ev ◦ (CB
× f) = ev ◦ (Cf
× A). Finally,
we clearly have a commutative square
CD
× A CD
× B
CB
× A CB
× B.
CD
×f
Cg
×A Cg
×B
CB
×f
We want to use these facts to complete our proof. Now, the map which
corresponds to Cgf
is, by definition, ev ◦ (CD
× gf). Now compute
ev ◦ (CD
× gf) = ev ◦ (CD
× g) ◦ (CD
× f)
= ev ◦ (Cg
× B) ◦ (CD
× f)
= ev ◦ (CB
◦ f) ◦ (Cg
× A)
= ev ◦ (Cf
× A) ◦ (Cg
× A)
= ev ◦ (Cf
Cg
× A)
Exercise Let C be a Cartesian closed category. Show that, for objects A, B, C ∈ C
we have a natural isomorphism
AC
× BC ∼= (A × B)C
.
Solution By the contravariant version of the Yoneda embedding (example above)
it suffices to show that the two objects represent naturally isomorphic
functors. Now choose an object D ∈ C and show that the two sets
C(D, AC
× BC
) and C(D, (A × B)C
) are in natural bijection. In order
to do so, compute
12
C(D, AC
× BC
) ∼= C(D, AC
) × C(D, BC
) ∼= C(D × C, A) × C(D × C, B)
∼= C(D × C, A × B) ∼= C(D, (A × B)C
)
and all those isomorphisms are natural, so their composite also is.
Example Remember that the universal property of products can be expressed in the
following way. Given two objects X and Y , their products is characterized
by the fact that, for every other object Z there are natural isomorphisms
C(Z, X × Y ) ∼= C(Z, X) × C(Z, Y ).
The same line of reasoning leads us to an analogous characterization of
coproducts: the coproduct X + Y is characterized by the fact that for
every other object Z there are natural isomorphisms
C(X + Y, Z) ∼= C(X, Z) × C(Y, Z).
Exercise Let C be a Cartesian closed category. Show that, for objects A, B, C ∈ C
we have a natural isomorphism
A(B+C) ∼= AB
× AC
.
Solution As above, we want to prove that there are natural bijections between
C(D, A(B+C)
) and C(D, AB
× AC
). Compute
C(D, A(B+C)
) ∼= C(D×(B+C), A) ∼= C(B+C, AD
) ∼= C(B, AD
)×C(C, AD
)
C(B × D, A) × C(C × D, A) ∼= C(D, AB
) × C(D, AC
) ∼= C(D, AB
× AC
)
where we are using both universal properties of products and coproducts
in their compact form.
Definition Let B be a Boolean algebra. Then a filter U is a proper subset of B such
that
1. 1 ∈ U;
2. x, y ∈ U implies x ∧ y ∈ U;
3. x ≤ y and x ∈ U implies y ∈ U.
Moreover, a filter is called an ultrafilter if it is maximal, that is, there
are no filters U of B such that U ⊂ U or, equivalently, for each x ∈ B,
precisely one between x and ¬x is in U.
Exercise Show that, for any Boolean algebra, B, the set of ultrafilters on B is
isomorphic to the set of morphisms of Boolean algebras B → 2, so that
there is an isomorphism Ult(B) ∼= BA(B, 2).
13
Solution We already know that, if we regard B as a set, there is a bijection P(B) ∼=
Set(B, 2), given by sending a subset A ⊆ B to the map χA that sends
elements of A to 1 and all other elements to 0. We need to show that this
map is a morphism of Boolean algebras if and only if A is an ultrafilter.
The preservation of the order relation is equivalent to condition 3 of a
filter.
For the preservation of meets, observe that when χA(x) = 0 (or χA(y) = 1)
it just follows by x ∧ y ≤ x plus condition 3; when χA(x) = χA(y) = 1, it
is exactly condition 2.
Similarly, for the preservation of joins, when χA(x) = 1 (or χA(y) = 1)
it follows by x ∨ y ≥ x plus condition 3. When χA(x) = χA(y) = 0, we
consider two cases: if x ≤ y, then x ∨ y = y and it becomes trivial; if
x y and y x, then χA(x ∨ y) = 1 would imply x ∨ y ∈ A, so that
A A ∪ {z ∈ B|x ≤ z} B which contradicts maximality.
Conversely, assuming that χA is a morphism of Boolean algebras, A is a
proper set because χA(0B) = 0 = 1. Condition 1 is trivial, condition 2 and
3 were already discussed. For maximality, suppose by contradiction that
A is not maximal, so there is either an element x ∈ B such that x, ¬x ∈ A
or such that x, ¬x /∈ A. In the former case, we obtain 0 = x ∧ ¬x ∈ A
which is impossible. In the latter, we obtain 0 = 0∨0 = χA(x)∨χA(¬x) =
χA(x ∨ ¬x) = χA(1) = 1, which also is a contradiction.
Week 4
Example Take two functions of sets, f : A → X and g : B → X. We want to give
a concrete description of their pullback. We claim that their pullback is
the subset of the product Sf=g ⊆ A × B containing all the pairs (a, b)
such that f(a) = g(b), and the two projections are the restrictions of
the two canonical projections from the product p1 : A × B → A and
p2 : A × B → B. To see that, take two other functions h : D → A
and k : D → B such that fh = gk. We want to find a factorization
t : D → Sf=g, and see that it is unique.
For an element d ∈ D, define t(d) = (h(d), k(d)) ∈ A × B. First, we need
to see that this is well-defined, that is, that this function lands in the
subset Sf=g. Observe that fh(d) = gk(d) by hypothesis, so this is clearly
satisfied. Moreover, p1t(d) = p1(h(d), k(d)) = h(d), so that p1t = h,
and analogously we obtain p2t = k, so this map is indeed a factorization.
To see that it is unique, observe that its definition is forced on the two
components respectively by the requirements that p1t = h and p2t = k.
Example Now we want to understand equalizers and coequalizers in Set. Take two
functions f, g : A → B between sets. We claim that their equalizer is the
subset E ⊆ A of all elements a ∈ A such that f(a) = g(a). To see that,
choose another function h : D → A such that fh = gh, and prove that it
factors uniquely through the inclusion E ⊆ A.
We want to define a function t as in the diagram
14
D
E A B.
t
h
f
g
For an element d ∈ D, let us set t(d) = h(d). Since fh = gh by hypothesis,
h(d) is indeed in the subset E, so the map is well-defined. Moreover, the
commutativity of the left triangle forces t to have this form.
Exercise Show that the pullback square
A ×X B A
B X
p2
p1
f
g
is also the product of f and g when regarded as objects of C/X.
Solution Take an object h : C → X ∈ C/X with maps q1 : C → A, q2 : C → B such
that fq1 = h = gq2, so that they are morphisms in C/X. This condition
exactly means that the outer square in the diagram
C
A ×X B A
B X
q1
q2
r
p2
p1
f
g
commutes. By the universal property of pullbacks, we thus obtain a unique
factorization r : C → A×X B, which is precisely the factorization we were
looking for, and it is a morphism in C/X.
Exercise Let C be a category with pullbacks. Show that a morphism f : X → Y is
monic if and only if the square
X X
X Y
idX
idX f
f
is a pullback diagram.
Solution Suppose that the diagram above is a pullback. We take two morphisms
g, h : Z → X such that fg = fh. This means that the outer square of the
diagram
15
Z
X X
X Y
g
h
idX
idX f
f
commutes. The universal property provides a factorization Z → X for
the two bent arrows, which means that g = h.
Conversely, suppose that f is monic, we want to prove that the squre
above is a pullback. Let us take a commutative outer square as the one
above. Since f is monic, the condition fg = fh which is exactly the
commutativity of the square implies that g = h, so we choose this as a
factorization Z → X. It is unique by the identity property of idX.
Exercise Let C be a category with products and pullbacks. Consider the pullback
square
E B
A B × B
e ∆
(f,g)
and show that the map e : E → A is an equalizer of f and g.
Solution Let us take an arrow q : Q → A such that fq = gq. Firstly, we want to
show that (f, g)q = ∆fq. By the universal property of the product, it
suffices to show it after postcomposing with the two projections p1, p2 :
B × B → B. Now we have p1(f, g)q = fq = p1∆fq and also p2(f, g)q =
gq = fq = p2∆fq. This means that the outer square in the diagram
Q
D B
A B × B
q
fq
r
e ∆
(f,g)
commutes. By universal property of the pullback, there is a dotted arrow
r making everything commute, so that in particular q = er. This
factorization is unique because it is also a factorization for the pullback.
Example In Grp, pullbacks are computed as in Set. We already saw a proof in Set,
what remains to show is that the subset Sf=g ⊆ A × B as in the previous
example is a subgroup, and that the factorization t : D → Sf=g we defined
is a group homomorphism. For the first, observe that 1 is preserved by f
and g, so that 1 ∈ Sf=g. Moreover, choose (a, b), (a , b ) ∈ Sf=g and take
their product in A × B, that is, (aa , bb ). Now we have that f(aa ) =
16
f(a)f(a ) = g(b)g(b ) = g(bb ), so the product lies in Sf=g.
Finally, for two elements d, d ∈ D, we need to show that t(dd ) = t(d)t(d ).
For that, let us compute
t(dd ) = (h(dd ), k(dd ))
= (h(d)h(d ), k(d)k(d ))
= (h(d), k(d))(h(d ), k(d ))
= t(d)t(d )
where we used that h and k are group homomorphisms.
Example In Top, pullbacks are also computed in the same manner. The topology
on the pullback is the subspace topology of the product topology.
Example In CRng and Mon, the same thing happens.
Example We now want to look at the dual notion of coequalizer. What is a coequalizer
in Set? We claim that, given two maps f, g : A → B, their
coequalizer is the quotient of B obtained by the following equivalence relation:
b ∼= b whenever there is an element a ∈ A such that f(a) = b
and g(a) = b . This is in general not reflexive, symmetric, or transitive.
We simply take ∼ to be the smallest equivalence relation generated by
∼=. More explicitly, two elements b and b are ∼-equivalent if there is
a finite sequence of elements (bi)i=1,...n such that b = b1, b = bn and
∀i = 1, . . . n − 1 we have either bi ∼= bi+1 or bi+1 ∼= bi.
Consider a function h : B → D such that hf = hg. We want to show
that this factors uniquely through the projection p : B → B/ ∼, as in the
diagram
A B B/ ∼
D.
f
g
p
h
k
For an element [b] ∈ B/ ∼, define k([b]) = h(b). We first need to see that
this is well defined, that is, if b ∼ b then h(b) = h(b ). We know that
there is a sequence of elements bi’s as described above. By induction, it
suffices to restrict our attention to bi and bi+1, for i = 1, . . . n−1. In other
words, we may assume that b ∼= b . This means that there is an element
a ∈ A such that f(a) = b and g(a) = b . Since hf = hg by hypothesis,
we now that h(b) = hf(a) = hg(a) = h(b ), so the map k is well-defined.
Moreover, it clearly satisfies kp = h.
To see that it is unique, observe that the commutativity of the right triangle
forces the form we just gave.
Example In a similar way, we can construct pushouts in Set. Consider two maps
f : A → B and g : A → C. We claim that the pushout is computed as the
quotient on the disjoint union B C given by the following equivalence
17
relation: if two elements belong to the same component of the disjoint
union, we do nothing; if b ∈ B and c ∈ C, we say that a ∼= c whenever
there is an element a ∈ A such that f(a) = b and g(a) = c. As in the case
of coequalizers, this relation is in general far from being an equivalence
relation, but we can complete it to an equivalence relation ∼ on B C.
This gives a commutative square
A B
C (B C)/ ∼
g
f
where the map B → (B C)/ ∼ is given as the composition of the inclusion
in the disjoint union B → B C and the projection to the quotient
B C → (B C)/ ∼, and similarly for the map C → (B C)/ ∼. The
proof that this is a pushout square is analogous to that for coequalizers.
Remark As in previous examples, pullbacks and equalizers in categories of algebras
are computed on the underlying sets. This is generally not the case for
pushouts or coequalizers.
However, this is the case in other categories such as Top, where both
pushouts and coequalizers are computed on the underlying sets, which are
then endowed with the quotient topology.
Week 5
Exercise Given a functor F : J → C, we denote by Conej∈J(A, Fj) the set of all
cones on F with vertex A.
Give a description of limits in Set in terms of cones. By the theorem of
existence of limits given products and equalizers, we can obtain another
explicit description. Verify that the two are isomorphic.
Solution Given a functor F : J → Set, we can compute
limj∈J Fj ∼= Set(∗, limj∈J Fj) ∼= Conej∈J(∗, Fj)
where the first isomorphism is a peculiarity of Set, and the second is
simply the universal property of limits. Now, let us spell out in detail
what a cone on F with vertex ∗ is.
For each j ∈ J, we are given a map ∗ → Fj, which corresponds to an
element xj ∈ Fj. The cone condition says that, for a morphism f : j → j
in J, we need to have xj = Ff(xj). This is all we need. A cone is then a
tuple of elements (xj ∈ Fj)j∈J satisfying the condition above. So the set
of cones on F with vertex ∗ is the subset of j∈J Fj determined by that
property, which is exactly the description given by the existence theorem.
Example We know that, for an object C ∈ C in a category, the representable functor
C(C, −) : C → Set preserves limits. This follows directly by the universal
property of limits. In particular, we can obtain the following equivalent
18
definition of limits.
Given a diagram (Ci)i in C and a cone (C → Ci)i, these induce maps of
the form
C(D, C) → C(D, Ci)
for every other object D ∈ C. This is a cone in Set with vertex C(D, C).
By universal property of limits in Set, this cone induces a map
φD : C(D, C) → limi C(D, Ci).
Now, C is a limit of the diagram (Ci)i if and only if for every object D ∈ C
the natural map φD is an isomorphism of sets. This implies that there is
a natural isomorphism C(D, limi Ci) ∼= limi C(D, Ci).
Example There is a completely analogous discussion for colimits. Suppose we have
a diagram (Ci)i and a cocone (Ci → C)i. For every object D ∈ C, the
maps to the vertex of this cocone induce maps
C(C, D) → C(Ci, D)
which form a cone (not a cocone!) in Set with vertex C(C, D). Therefore,
again by the universal property of limits (not colimits!) in Set, we have
a canonical map
ψD : C(C, D) → limi C(Ci, D).
Then the object C is a colimit for the diagram if and only if for every
object D ∈ C the map ψD is an isomorphism of sets. In other words, there
are natural isomorphisms C(colimi Ci, D) ∼= limi C(Ci, D).
Example Unfortunately, there is no simple way to describe colimits in Set as in
the exercise above. Therefore, we have to rely on the existence theorem
and deduce what they look like from what we know about coproducts and
coequalizers.
In short, given a functor F : J → Set, the colimit of F may be thus
computed. First take the coproduct j∈J Fj. By the existence theorem
and the description of coequalizers, we know that the colimit has to be a
quotient of this.
Define an equivalence relation on j∈J Fj as follows: for x ∈ Fj and
y ∈ Fj , we say that x ∼= y if there exists a k ∈ J and two morphisms
j
k
j
f
f
19
with an element z ∈ Fk such that Ff(z) = x and Fg(z) = y. This relation
is reflexive (because we allow identities) and symmetric (because we are
not considering j and j in any particular order), but it is in general not
transitive. We define ∼ as the transitive closure of this relation. Clearly,
it gives an equivalence relation. A bit more visually, x, y ∈ j∈J Fj are
equivalent if and only if there is a zig-zag of morphims in J that move x
to y through evaluating functions or choosing preimages.
Taking the quotient of this equivalence relation, we get the desired de-
scription
colimj∈J Fj ∼= ( j∈J Fj)/∼.
Exercise Let C be a category admitting limits of shape J, and let Fun(J, C) be
the category of functors J → C, having functors as objects and natural
transformations as morphisms. Show that there is a functor
limJ : Fun(J, C) → C.
Solution For a functor F : J → C, we simply choose a limit limJ F. Given a natural
transformation α : F → G, we want to obtain a morphism lim F → lim G.
Note that there is a cone (tj : lim F → Fj)j∈J. We can compose this
objectwise with α, so to obtain maps (αj ◦ tj : lim F → Gj)j∈J. We want
to check that this is also a cone. Given a morphism j → j in J, we have
a diagram
lim F
Fj Fj
Gj Gj .
tj tj
αj αj
Here, the upper triangle commutes because (tj) is a cone, the lower square
commutes because α is natural. Therefore, (αj ◦ tj) is a cone over G.
By universal property of limits, this induces a unique map, which we
will call lim α : lim F → lim G, such that sj ◦ lim α = αj ◦ tj, where
(sj : lim G → Gj) is a limiting cone for G. We need to check that this is
functorial.
Given the identity natural transformation id : F → F, the composed cone
as in the diagram above is still (tj), so the identity id : lim F → lim F will
be a possible factorization for it. Since this factorization is unique, the
identity is the only possible choice.
Now, given two natural transformations α : F → G and β : G → H,
we obtain as above the induced factorizations lim α : lim F → lim G and
lim β : lim G → lim H. By uniqueness of factorizations, it will suffice
to show that lim β ◦ lim α is a factorization for the cone (βj ◦ αj ◦ tj)
over H with vertex lim F. If we use the same notation as above, plus
(rj : lim H → Hj) for the limiting cone of H, we compute, for each j ∈ J,
20
rj ◦ lim β ◦ lim α = βj ◦ sj ◦ lim α = βj ◦ αj ◦ tj
which is exactly what we need.
Example This is the key example of density of a functor. Let C be any category, and
let y : C → SetCop
the Yoneda embedding, so that y(C) = C(−, C). Here,
embedding means full and faithful (and we know that this functor is such).
Then y is a dense functor. In particular, for every functor F ∈ SetCop
,
we have a slice category SetCop
/F , so we can take the subcategory spanned
by all representable functors over F, and we call it C/F . This comes with
a natural projection C/F → C. We claim that F is the colimit of the
composite functor
C/F → C → SetCop
.
We will not spell out all the details of the proof here, but the strategy
is the following: given a functor G ∈ SetCop
and a cocone on C/F with
vertex G, we need to show that it factors uniquely through F.
We will give each component θC : F(C) → G(C) of the factorization.
Given an element x ∈ F(C), by the Yoneda lemma it corresponds to
a natural transformation αx : C(−, C) → F, which is then an object
of C/F . Therefore, since we have a cocone on C/F with vertex G there
is a corresponding natural transformation tαx
: C(−, C) → G. Using
the Yoneda lemma again, this yields an element z ∈ G(C). Now we set
θC(x) := z.
Moreover, θ is natural, which is a consequence of the fact that the Yoneda
isomorphisms are all natural. That it is the desired factorization is directly
a consequence of its very definition and of the fact that the Yoneda lemma
applied to G gives a bijection
G(C) ∼= Nat(C(−, C), G).
Finally, it is uniquely determined for the same reason (assuming that there
are two different ones, we would obtain that there is at least one C ∈ C
that falsifies Yoneda).
Week 6
Exercise Show that limits in a functor category are computed objectwise. This
means that, assuming that C has all limits of shape J, and choosing a
diagram F : J → Fun(D, C), the value of the limit of F on an object
D ∈ D can be calculated as
(limj∈J Fj)(D) = limj∈J(Fj(D)).
Solution Note that the functor F : J → Fun(D, C) corresponds to a functor J×D →
C, which in turn corresponds to a functor ˜F : D → Fun(J, C) sending an
object D ∈ D to the functor j → Fj(D). In a previous exercise, we
have seen that the computation of limits can be assembled in a functor
lim : Fun(J, C) → C. Now, the functor on the right-hand side of the
statement is precisely the composite
21
lim ◦ ˜F : D → Fun(J, C) → C.
We want to show that this functor has the universal property of limits
with respect to the diagram F.
First, we observe that for an object D ∈ D we have a cone pD
j : limj∈J(Fj(D)) →
Fj(D). The maps forming this cone are natural, because given a morphism
k : D → D in D, the square
limj∈J(Fj(D)) Fj(D)
limj∈J(Fj(D )) Fj(D )
pD
j
lim F j(k) F j(k)
pD
j
commutes. This is true by definition of the left vertical map. So we have a
cone (pj : limj∈J Fj → Fj) in Fun(D, C). Let us show it has the universal
property.
Choose another cone (αj : G → Fj)j∈J in Fun(D, C). For every object
D ∈ D, this yields a cone (αD
j : G(D) → Fj(D))j∈J in C. So by the
universal property of limits in C, we obtain a unique natural morphism
θD
: G(D) → limj∈J(Fj(D)) such that pD
j ◦ θD
= αD
j . It only remains to
show that the morphisms (θD
)D∈D form a natural transformation.
Given a morphism k : D → D , consider the diagram
G(D) limj∈J(Fj(D))
G(D ) limj∈J(Fj(D )) Fj(D ).
θD
G(k) lim F j(k)
θD
pD
j
We need to show that lim Fj(k) ◦ θD
and θD
◦ G(k) are equal. By the
universal property of limj∈J(Fj(D )), it suffices to show that they coincide
after composing with all the projections pD
j . Now compute
pD
j ◦ lim Fj(k) ◦ θD
= Fj(k) ◦ pD
j ◦ θD
= Fj(k) ◦ αD
j
= αD
j ◦ G(k)
= pD
j ◦ θD
◦ G(k)
where we are using the fact that the θD
components are factorizations for
the αD
components, plus the definition of lim Fj(k) and the naturality of
α.
In conclusion, we have obtained a natural transformation θ : G → limj∈J(Fj(−))
such that pj ◦ θ = αj for every j. This factorization is unique because if it
weren’t, there would be two different factorizations for at least one component
D, which contradicts the universal property of limits in C.
22
Remark Exactly by the same reason, colimits are computed objectwise in functor
categories. So if we have a diagram F : J → Fun(D, C), the functor
colimj∈J Fj : D → C sends an object D ∈ D to colimj∈J(Fj(D)), and the
action on morphisms is determined by the universal property of colimits.
Remark Another way to express the fact that limits and colimits are computed
objectwise is saying that, for every object D ∈ D, the evaluation functor
evD : Fun(D, C) → C
preserves limits and colimits.
Exercise Let C be a category. Prove that the Yoneda embedding y : C → SetCop
preserves all limits that exist in C.
Solution Let us choose a diagram F : J → C, and assume that it has a limit. We
want to show that y(lim F) ∼= lim yF. The left-hand side is the functor
C(−, lim F), the right-hand side is the limit of the functor J → SetCop
sending an object j ∈ J to C(−, Fj). It suffices to show that these two
are naturally isomorphic, that is, we need to show that, once evaluated in
C ∈ C, they yield a natural isomorphism.
Now the statement follows immediately by observing that, by the universal
property of limits, we have natural isomorphisms
C(C, limj∈J Fj) ∼= limj∈J C(C, Fj).
Remark The Yoneda embedding does not preserve colimits, even in the trivial case
y : ∗ → Set∗ ∼= Set.
Furthermore, the Yoneda embedding y : Cop
→ SetC
does not preserve
colimits either. Indeed, if we have a diagram (Ci)i∈I in C, then we know
that C(colim Ci, D) ∼= lim C(Ci, D) for any other object D ∈ C. Since
colimits in C correspond with limits in Cop
, the conclusion is that the
dual Yoneda embedding preserves limits, just as the Yoneda embedding.
Another way to see it is that this functor is simply a special case of the
Yoneda embedding which, as we already know, preserves limits but not
colimits.
This might seem strange at first, but the following should clarify things.
Observe that, since the Yoneda embedding of Cop
preserves limits, this
means exactly that the embedding yop
: C → (SetC
)op
preserves colimits.
This polarization between limits and colimits is closely connected to
the fact that SetCop
is the free cocompletion, and (SetC
)op
is the free
completion of C.
Definition Recall that a subobject of an object C in a category is an equivalence
class of monomorphisms with codomain C, where two such f : A → C
and g : B → C are equivalent if there exists a commutative triangle
A B
C
q
f g
23
where q is an isomorphism.
We say that a category with a final object has a subobject classifier if
there is an object Ω with a monomorphism t : ∗ → Ω such that for every
subobject A → C there is a unique map C → Ω such that the square
A ∗
C Ω
t
is a pullback.
Remark In other words, this means that the operation of pulling back gives a bijection
C(C, Ω) ∼= Sub(C). Moreover, since monomorphisms and isomorphisms
are both stable under pullback, there is a functor Sub : Cop
→ Set.
The present statement says that if C has a subobject classifier this is a
representable functor.
Exercise Assume that there is a monomorphism t : Q → Ω which satisfies the
universal property of the subobject classifier. Prove that Q is terminal.
Solution Given an object C, we need to show that there exists a unique morphism
C → Q. For the existence, observe that the identity idC : C → C is a
monomorphism, so there is a pullback square
C Q
C Ω.
f
idC t
This gives a morphism f : C → Q. Moreover, the bottom horizontal
morphism is tf. Suppose there are two morphisms f, g : C → Q. We have
a diagram
C Q Q
C Q Ω
idC
g idQ
idQ t
g t
where the right square is a pullback because t is monic, and the left square
is a pullback by direct check. Thus the composite tg classify the identity
C → C, but by universal property of the subobject classifier there can
only be one morphism that does that, so we must have tf = tg. Finally,
since t is a monomorphism, we get f = g.
Exercise Given a small category C, find the subobject classifier in the category
SetC
.
Solution If Ω exists, it is a functor C → Set which satisfies the universal property
Nat(F, Ω) ∼= Sub(F) for every other functor F : C → Set, where the
isomorphism is given by pulling back a (yet to be found) natural transformation
∗ → Ω. If this is true, then by the Yoneda lemma we can evaluate
the functor Ω at an object C as
24
Ω(C) ∼= Nat(y(C), Ω) ∼= Sub(y(C)).
We use this to define Ω as sending C to the set Sub(y(C)), and a morphism
f : C → C to the pullback map f∗
: Sub(y(C )) → Sub(y(C)). The
natural transformation t : ∗ → Ω has components tC : ∗ → Sub(y(C)),
defined as the map selecting the maximal subobject id : y(C) → y(C).
The universal property holds by construction.
Week 7
Definition Recall that given two categories C and D, we define F : C → D and
G : D → C to be adjoint, and write F
⊥
G, if for every object C ∈ C and
D ∈ D there are bijections
φC,D : D(F(C), D) ∼= C(C, G(D))
that are natural in both C and D. This means that for a morphism
h : C → C the square
D(F(C), D) C(C, G(D))
D(F(C ), D) C(C , G(D))
F (f)∗
φC,D
f∗
φC ,D
commutes. Analogously, for a morphism k : D → D , the square
D(F(C), D) C(C, G(D))
D(F(C), D ) C(C, G(D ))
k∗
φC,D
G(k)∗
φC,D
commutes.
There is a more compact way of expressing naturality of these isomorphisms.
Consider the two functors Cop
×D → Set given as the composites
Dop
× D
Cop
× D Set
Cop
× C.
D(−,−)F op
×id
id×G C(−,−)
What we are saying is now that φC,D is a natural isomorphism between
these two functors.
Exercise Show that whenever a category has exponentials, then for an object C ∈ C
there is an adjoint pair (−) × C
⊥
(−)C
.
25
Solution By definition of exponential, we know that there is a map evA : C ×AC
→
A such that for every f : C × B → A there is a unique ˜f : B → AC
fitting
in a commutative diagram
C × B A
C × AC
.
f
C× ˜f evA
In particular, we may define φB,A to send f to ˜f. This is a bijection
by universal property. We want to prove that it is natural. Choose a
morphism h : B → B and a morphism k : A → A . We need to show that
the square
C(C × B, A) C(B, AC
)
C(C × B , A ) C(B , A C
)
C(C×h,k)
φB,A
C(h,kC
)
φB ,A
is commutative. Choosing a map f : C × B → A, the right-then-down
composite takes it to kC
◦ ˜f ◦ h, the down-then-right composite takes it
to the map associated to k ◦ f ◦ (C × h) by the universal property of
exponentials. Since this map is unique, it suffices to check that kC
◦ ˜f ◦ h
fits in the appropriate diagram. This diagram is
C × B A
C × A C
.
k◦f◦(C×h)
C×(kC
◦ ˜f◦h) evA
This can be decomposed into the following, a bit more complicated dia-
gram
C × B
C × B
A A
C × AC
C × A C
.
C×h
k◦f◦(C×h)
C× ˜f
f
k
C×kC
evA
evA
Here the upper square commutes evidently, the middle triangle by universal
property of exponentials and the lower square by definition of kC
.
26
Example As a consequence of the theorem above, we have many interesting examples
where the functor taking products with a fixed object has a right
adjoint: Set, Mon, Grp, Ab, Haus, CRng, just to name a few, are
special cases of it.
Example The product-exponential pattern is very common, and many adjunction
that arise naturally are variants of this form. Another very common pattern
is constituted by the free-forgetful adjunctions. We give one example,
the others are more or less similar to this.
Given a set X, we say that FX is the free group generated by X if there is
a map ηX : X → FX such that, for any other group G and every function
X → G of underlying sets, there exists a unique group homomorphism
FX → G fitting in the commutative triangle
X G
FX.
ηX
Denoting by U : Grp → Set the forgetful functor associating to every
group its underlying set, observe that the map X → G above should more
precisely written as X → UG. The universal property of free groups then
associates to every such map X → UG a unique group homomorphism
FX → G, thus giving a bijection
Grp(FX, G) ∼= Set(X, UG)
which is natural in both variables. This is indeed an adjunction
F : Set Mon : U.
Example The evaluation map evA : C × AC
→ A and the injection ηX : X → FX
play dual roles in their respective settings. Indeed, if we denote a general
left adjoint functor by L and a right adjoint by R, the former is of the form
εQ : LRQ → Q and the latter is of the form ηQ : Q → RLQ for an object
Q. Moreover, they are natural in Q, so they are in fact natural transformations
of the forms ε : LR ⇒ id and η : id ⇒ RL respectively. These
are precisely the counit and the unit of the corresponding adjunctions.
Exercise What are the counits of the product-exponential adunction in Set? And
what about the counit of the free-forgetful adjunction between Set and
Mon?
Solution There is a natural bijection
Set(A × C, A × C) ∼= Set(A, (A × C)C
) ∼= Set(A, AC
× CC
)
and we know that the unit corresponds to the identity in the left-hand
side. An explicit calculation yields that the identity is sent to the map
sending an element a ∈ A to the pair (ca, idC), where the first component
is the constant map in a, and the second is simply the identity C → C.
Similarly, the counit of F
⊥
U corresponds to he identity via the bijection
27
Set(UG, UG) ∼= Mon(FUG, G).
Now, elements of the group FUG are finite sequences (g1, . . . , gn), where
the gi’s are elements of G. The counit map FUG → G sends such a
sequence to the product g1 · · · gn.
Exercise Show that, if C is a category having all J-indexed limits, there is an ad-
junction
δ : C CJ
: lim
where δ is the functor sending C to the functor constant at C.
Solution We need to show that there are natural bijections of the form
CJ
(δC, F) ∼= C(C, lim F).
But now the left-hand side is precisely Cone(C, F), which is naturally
isomorphic to C(C, lim F) by universal property of limits.
Example By a dual argument, we know that there are natural bijections
C(colim F, C) ∼= CJ
(F, δC)
so that we have an adjunction
colim : CJ
C : δ
Exercise Show that a left adjoin preserves colimits and that a right adjoint preserves
limits.
Solution We will show that a right adjoint preserves limits, the other argument is
dual. Let (Di)i∈I be a diagram in the category D, and let there be an
adjunction
L : C D : R
we want to show that R(limi∈I Di) is a limit of the diagram (RDi)i∈I.
Let us compute, for an object C ∈ C,
C(C, R(lim
i∈I
Di)) ∼= D(LC, lim
i∈I
Di)
∼= lim
i∈I
D(LC, Di)
∼= lim
i∈I
C(C, RDi)
∼= C(C, lim
i∈I
RDi)
where all the isomorphisms are natural by various universal properties.
Now the result follows by a characterization of limits.
28
Week 8
Exercise Let F : A → B be a functor. Show that F has a right adjoint if and
only if for every object B ∈ B the functor B(F−, B) : Aop
→ Set is
representable.
Solution Clearly, if F has a right adjoint G, then
B(FA, B) ∼= A(A, GB)
naturally in both A and B. This means that the functor above is represented
by GB.
Conversely, suppose that every functor of the form B(F−, B) is represented
by some object ¯B. This means that there are natural bijections
φA,B : B(FA, B) ∼= A(A, ¯B)
that are natural in A. Now choose such an object ¯B ∈ A and such a
bijection for every object B ∈ B and define a functor G : B → A as
follows: on objects, the action is given by GB := ¯B. For a morphism
f : B → B , consider the composite
A(A, GB) B(FA, B) B(FA, B ) A(A, GB ).
φA,B f∗ φ−1
A,B
By Yoneda lemma, this corresponds to an arrow GB → GB , which we
call Gf.
Now, the square
B(FA, B) A(A, GB)
B(FA, B ) A(A, GB )
φA,B
f∗
φA,B
commutes by the very definition of the right vertical map, giving naturality
in B as well.
It only remains to show that G is a functor. If we pick the identity, the
composite φ−1
A,B ◦id∗
B ◦φA,B : B(FA, B) → B(FA, B) as above is the identity,
therefore it corresponds to the identity via the Yoneda isomorphism.
If f : B → B and g : B → B are two composable maps, then we have
φ−1
A,B ◦ g∗
◦ φA,B ◦ φ−1
A,B ◦ f∗
◦ φA,B = φ−1
A,B ◦ g∗
◦ f∗
◦ φA,B
= φA,B ◦ (gf)∗
◦ φA,B.
Since the left-hand side corresponds to Gg ◦ Gf and the right-hand side
to G(gf) via the Yoneda isomorphism, this concludes the proof.
29
Remark We also have the dual statement, that is, given a functor G : B → A,
then it has a left adjoint if and only if for every object A ∈ A the functor
A(A, G−) : B → Set is representable. The proof is analogous, and uses
the covariant Yoneda lemma instead of the contravariant one.
Exercise Let Ω be a subobject classifier in an elementary topos, and let φ : Ω → Ω
be a monomorphism. Prove that φ ◦ φ = idΩ. In particular, φ is an
isomorphism.
Solution First, define the two pullback squares
V U 1
1 Ω Ω.
k t
t φ
The fact that the outer square is a pullback can be expressed as φt = χV .
Moreover, there is a double pullback
V V 1
U 1 Ω
t
χV
where the right part is a pullback by definition, and the left part is easily
checked to verify the universal property, using that the map U → 1 is
monic. By uniqueness of the classifying map, this means that χV iU = k.
Using this and the fact that k is monic, we see that there is a double
pullback
U T U
U 1 Ω
k
χV
so that T is a subobject of 1 such that U ≤ T and T ≤ U, which implies
T = U. As a consequence, we know that the left square (and the right
one as well) is a pullback in the diagram
U U 1
1 Ω Ω.
k t
χV φ
Again by uniqueness of the classifying map, this means that φχV = χU .
The key facts that we proved and need to keep in mind for the following
step are:
– φt = χV ;
– χV iU = k;
30
– φχV = χU .
Now, in the big diagram
V V 1 1
U U Ω Ω
U 1 Ω Ω
U 1 Ω Ω
t t
k
φ φ
t
φ
t φ
every square is a pullback. By the three formulas above, the outer square
can be rewritten as
V 1
U Ω.
χU
k
This fact combined with the first double square in the proof implies that
φχU = φt. Since φ is monic, this implies χU = t. Now we have
φ2
t = φχV = χU = t.
To conclude, compute the following pullback
1
W 1
Ω Ω.
t
t
φ2
Since φ2
t = t, the outer square commutes so there is a factorization. Thus,
W is a subobject of 1 that has a section, which means that it is in fact
isomorphic to 1, so that the square
1 1
Ω Ω
t t
φ2
is a pullback. Using the universal property of Ω one last time yields that
φ2
= idΩ as desired.
Exercise Show that in an elementary topos the subobject classifier is injective.
31
Solution Remember that Ω being injective means that for every monomorphism
A → B and every morphism A → Ω, there is a lift in the diagram
A Ω
B.
Compute the pullback diagram
M 1
A Ω
t
So that in particular we have a composite monomorphism M → A → B.
In turn, this is classified by a morphism B → M. We want to show that
this is the lift we are looking for.
By universal property of Ω, it suffices to show that the given morphism
A → Ω and the composite A → B → Ω classify the same subobject of B.
To see this, observe the following diagram
M M 1
A A
A B Ω.
id
t
id
id
The right square is a pullback by definition, the left lower square by a
characterization of monomorphisms and the left upper square evidently.
Therefore, the bigger square is a pullback, so the composite A → B → Ω
is a classifying map for the subobject M → A, but this is classified by the
morphism A → Ω by definition. This concludes the proof.
Week 9
Definition Recall that a functor G : D → C is said to satisfy the solution set condition
if, for every object C ∈ C there is a set of objects (Di)i∈I in D such that
every map C → GD can be factored as C → GDi → GD for some i ∈ I
and some map Di → D in C.
Theorem Also recall the following theorem, of the utmost importance in category
theory.
Let G : D → C be a functor, where D is complete. Then G has a left
adjoint if and only if the two following conditions are satisfied:
1. G preserves all small limits;
2. G satisfies the solution set condition.
32
Example The forgetful functor U : CHaus → Set, assigning to every compact
Hausdorff space its underlying set of points, has a left adjoint.
To see this, we need to verify the two conditions of the above theorem. By
a direct check of the universal property, we see that the product topology
and the subspace topology provide products and equalizers, which means
that U preserves limits.
We need the solution set condition. Fixing a set S, we need to find a
suitable set of compact Hausdorff space. We will get there through the
following reasoning: given a function f : S → UX (that we would like to
factor through the set we are looking for), we construct a map fS → PPX
by sending every point x ∈ fS to the set
Lx = {D ⊆ S|x ∈ fD}.
Using that X is compact Hausdorff, for two distinct points x, x ∈ X we
can always construct two open sets U x and U x in such a way that
U ∩ U = ∅. In particular, f−1
U ∈ Lx but f−1
U /∈ Lx . This implies that
the function L : X → PPS is injective. Now, observe that f factors as
S → fS ⊆ UX
and we have just proven that fS can be regarded as a subset of PPS with
a suitable topology.
This construction motivates the following choice: once we fix a set S, we
take the set of all subsets of PPS with all possible compact Hausdorff
topologies on them. The above discussion proves that this is indeed a
solution set.
Therefore, the adjoint functor theorem yields a left adjoint to U. More
explicitly, this left adjoint assigns to each set S the Stone-ˇCech compactification
of the discrete topology on S.
Exercise Show that the forgetful functor U : Grp → Set has a left adjoint using
the adjoint functor theorem.
Solution We already know that there is a natural isomorphism U ∼= Grp(Z, −), so
that it preserves limits.
We need to show that U satisfies the solution set condition. Choose a
set X. There exists a cardinal λ such that X has less than λ elements.
Now we take the set of all groups that admit a generating set smaller than
λ. This is indeed a set, because up to isomorphism these groups are in
bijection with quotients of groups of the form Zi
, with i < λ.
Given a group G and an arbitrary map X → UG, observe that, since
|X| < λ, its image in G is smaller than λ. Therefore, the subgroup
GX ⊆ G generated by the image certainly belongs to the set of groups that
we described above. Now the image inclusion provides the factorization
X → UGX → UG
that we were looking for.
33
Counterexample Consider the forgetful functor U : CBool → Set. The category CBool of
complete Boolean algebras is complete, and the forgetful functor preserves
small limits. However, it has been (non-trivially) proven that for every
set S there are arbitrarily large complete Boolean algebras generated by
S, which falsifies the solution set condition. As a consequence, there is no
”free complete Boolean algebra” functor.
Remark In the case of groups, we used essentially that every set is bounded by some
cardinal and that every group can be constructed out of its subgroups
with a similar bound on the respective generating sets. This motivates
the following definitions.
Definition Let λ be a regular cardinal. We say that a small category J is λ-filtered
if every diagram in J which is smaller than λ admits a cocone.
For an intuition, think of a set X. The poset of all subsets of X of
cardinality < λ is λ-filtered, since the union of λ-small subsets is itself
λ-small.
Definition Let C ∈ C be an object of a category. Let us fix a regular cardinal λ. We
say that C is λ-compact if the functor C(C, −) preserves λ-filtered colimits.
In other words, if J is a λ-filtered category and (Di)i∈J is a diagram in C,
the natural map
colimJ C(C, Di) → C(C, colimJ Di)
is an isomorphism.
Remark The above definition can be expressed more explicitly by saying that every
map C → colimJ Di factors through one of the colimit inclusions ci : Di →
colimJ Di. Moreover, this factorization is essentially unique in the sense
that, if there is a set of factorizations (C → Di)i∈I, where |I| < λ, then
there is an object Dt, with t ∈ J, and a cocone (Di → Dt)i∈I such that
all the composite maps
(C → Di → Dt)i∈I
are equal. In other words, a set of less than λ factorizations can always
be amalgamated to a single object.
Example In Set, λ-compact objects are precisely sets of cardinality smaller than λ.
In Grp (and categories of algebras generally), λ-compact objects are
presicely groups that admit a λ-small generating set.
Top is ill-behaved in this respect, in that its λ-compact objects are precisely
discrete spaces of cardinality smaller than λ, so it does not capture
topological notions of compactness. In particular, compact spaces are not
necessarily finitely compact in the present sense.
Definition We say that a category K is locally λ-presentable if
– it is cocomplete,
– the subcategory Kλ
⊆ K of λ-compact objects is essentially small
and
34
– every object K ∈ K is a λ-filtered colimit of λ-compact objects.
We say that K is locally presentable if it is locally λ-presentable for some
λ.
Example Typically, categories arising in algebra are presentable, whereas categories
arising in topology are not. In particular, Set, Grp, Mon, R−Mod, Pos
and all categories of the form SetC
with C small are locally presentable.
The categories, Top, Haus, CHaus, CBool, CABA are not locally
presentable.
Tools These facts are very handy but highly non-trivial, so we are just stating
them for future usage.
1. In a locally presentable category, for every µ the subcategory of µcompact
objects is essentially small.
2. In a locally presentable category, every object is µ-compact for some
µ. As a consequence, a locally presentable category K can be written
as a union of small categories µ Kµ
.
3. If a category is locally presentable, there are arbitrarily large cardinals
µ such that it is locally µ-presentable.
Moreover, observe that for λ < µ every λ-compact object is also µ-
compact.
Theorem (Adjoint functor theorem, presentable version).
Let G : D → C be a functor between locally presentable categories. Then
G has a left adjoint if and only if it preserves limits and λ-filtered colimits
for some λ.
Proof We only need to verify the solution set condition. Fix an object C ∈ C. It
is µ-compact for some µ, and we may assume that µ ≥ λ. Then take the
set of µ-compact objects of D. Now, given a morphism C → GD, express
D as a µ-filtered colimit of µ-compact objects, D ∼= colim Di.
Since µ ≥ λ, we know that G preserves µ-filtered colimits, so that we also
have GD ∼= colim GDi. Since C is µ-compact, there is a factorization
C → GDi → GD
as we wanted.
For the converse, we only need to show that G preserves λ-filtered colimits.
Let F be a left adjoint to G. Let λ be such that C is locally λ-presentable
and let µ be such that the image of every λ-compact object along F is
µ-compact, and take a µ-filtered diagram (Di). By the Yoneda lemma, it
suffices to show that there are natural isomorphisms C(C, colim GDi) ∼=
C(C, G colim Di) for every C ∈ C. Express C as a colimit of λ-compact
objects Cj’s. Remembering that F preserves all colimits, we may now
compute
35
C(C, G colim
i
Di) ∼= D(FC, colim
i
Di)
∼= D(colim
j
FCj, colim
i
Di)
∼= lim
j
D(FCj, colim
i
Di)
∼= lim
j
colim
i
D(FCj, Di)
∼= lim
j
colim
i
C(Cj, GDi)
∼= lim
j
C(Cj, colim
i
GDi)
∼= C(colim
j
Cj, colim
i
GDi)
∼= C(C, colim
i
GDi)
which completes the proof.
Week 10
Remark Observe that a λ-small colimit of λ-compact objects is λ-compact. To
see this, let C = colimi Ci be a λ-small colimit, where each of the Ci’s is
λ-compact, and let D = colimj Dj be any λ-filtered colimit. Using that
λ-filtered colimit commute with λ-small limits in Set, we compute
C(C, colimj Dj) ∼= limi C(Ci, colimj Dj) ∼= limi colimj C(Ci, Dj) ∼=
colimj limi C(Ci, Dj) ∼= colimj C(C, Dj)
which proves the claim.
Exercise Show that for a small category C the category SetCop
is locally presentable.
Solution It is clear that SetCop
has all small colimits. Moreover, every functor
F : Cop
→ Set is a colimit of representables indexed by the diagram C/F .
Let us take the diagram D ⊇ C/F of all finite colimits of representables
over F. This is small, filtered, and a check of the universal property shows
that its colimit must be the same as that of C/F . We only need to show
that objects of D are compact. By the lemma above, we are reduced to
showing that representable functors are compact. In fact, we can show
the stronger result that they are absolutely compact, that is, the functors
SetCop
(C(−, C), −) (in the second variable) preserve all colimits. To see
this, choose a colimit F = colim Fi in SetCop
and compute
SetCop
(C(−, C), F) ∼= F(C) ∼= colim Fi(C) ∼= colim SetCop
(C(−, C), Fi)
which concludes the proof.
Exercise Prove that, if K is locally presentable, there is a small category C such
that K is a reflective full subcategory of SetCop
.
36
Solution We know that there is λ such that the full subcategory Kλ
is small. Take
C = Kλ
. First, we want to show that there is a full embedding E : K →
SetKλop
. We define it to be the restriction of the Yoneda embedding, so
that its action on objects is
K → K(−, K)
where the functor K(−, K) is only intended to take λ-compact objects as
inputs. We want to show that K(K, H) ∼= SetKλop
(K(−, K), K(−, H)).
Suppose f = g : K → H. Let us express K as a λ-filtered colimit of
λ-compact objects (Kj)j∈J . By the universal property of colimits, there
is at least one j such that the two composites
Kj → K H
are different, which means that the induced natural transformations K(−, f)
and K(−, g) are different as well, and E is faithful.
Now, take a natural transformation K(−, K) → K(−, H), where the input
is restricted to λ-compact objects. Taking the same diagram J as above,
the components
K(Kj, K) → K(Kj, H)
gives rise, by taking limits on the opposite diagram Jop
, to a map
limj K(Kj, K) → limj K(Kj, H)
which is isomorphic to
K(K, K) → K(K, H)
so that we get a morphism K → H as image of idK, which represents our
natural transformation.
Now we need to show that E has a left adjoint. By the adjoint functor
theorem in its presentable version, it suffices to show that E preserves
λ-filtered colimits. So if H = colimi Hi is a λ-filtered colimit in K, what
we need to show is that EL(K) ∼= colimi EHi(K) naturally for every
λ-compact object K. Compute
EH(K) ∼= K(K, H) ∼= colimi K(K, Hi) ∼= colimi EHi(K)
so we are done.
For additional clarity, let us write a left adjoint explicitly. The idea is
that, since every functor Kλop
→ Set is a λ-filtered colimit of objects of
Kλ
, this functor concretely calculates this colimit inside K.
In detail, given a functor F : Kλop
→ Set, this is a colimit of the diagram
Kλ
/F → Kλ
→ SetKλop
. We define LF to be a colimit of the diagram
Kλ
/F → Kλ
→ K. This is clearly functorial, it remains to show that it is in
37
fact a left adjoint to E. Let H ∈ K, and express it as a λ-filtered colimit
of λ-compact objects L = colimi Hi. Now compute
K(LF, H) ∼= K(colim Kj, H)
∼= lim K(Kj, H)
∼= lim colim
i
Kλ
(Kj, Hi)
∼= lim colim
i
SetKλop
(K(−, Kj), K(−, Hi))
∼= lim SetKλop
(K(−, Kj), colim
i
K(−, Hi))
∼= lim SetKλop
(K(−, Kj), EH)
∼= SetKλop
(colim K(−, Kj), EH)
∼= SetKλop
(F, EH).
Corollary Every locally presentable category is complete.
Proof Let K be locally presentable and let E : K → SetCop
be an embedding as
above, with L being its left adjoint. Observe that, since E is fully faithful,
we have LE ∼= idK.
Given a small diagram p : J → K, compose it with E. Since SetCop
is
already known to be complete, the diagram Ep has a limit. Take a limiting
cone
(lim EKj → EKj)j∈J
and plug it through the left adjoint L. This yields a cone in K of the form
(L lim EKj → LEKj
∼= Kj)j∈J.
We want to show that this is a limiting cone. Given another cone
(Q → Kj)j∈J
using that Q ∼= LEQ, this corresponds precisely to a cone
(EQ → LKj)j∈J
in SetCop
which, by universal property, yields a unique factorization lim EKj →
EQ. By adjunction, this corresponds uniquely to a morphism L lim EKj →
LEQ ∼= Q, which is the unique factorization we were looking for.
Remark The proof that we have seen of the adjoint functor theorem in its presentable
version actually uses that locally presentable categories are complete.
Therefore, if we don’t know this fact from other sources, we can’t
use AFT in the above theorem, and the explicit construction of L becomes
necessary.
38
Remark The above corollary does not mean that L preserves limits. Rather, it
preserves all limits of objects that are in the image of E.
Definition Given two functors f : C → D and p : C → C , a left Kan extension of
f along p is a pair (F, α), where F : C → D and α : f ⇒ Fp such that
for any other such pair (G, β) there is a unique natural transformation
γ : F ⇒ G such that β = γp ◦ α.
C D
C
f
p F
G
α
γ
Remark Given a functor G ∈ DC
) with a natural transformation β ∈ DC
(f, Gp),
the universal property of left Kan extensions gives a unique natural transformation
γ ∈ DC
(F, G). This means that, if we conveniently denote F
by Lanpf, the assignment f → F (which is functorial by naturality of the
construction) gives rise to a natural bijection
DC
(Lanpf, G) ∼= DC
(f, p∗
G)
thus, if all left Kan extensions of functors C → D along p exist, they give
rise to an adjunction
Lanp : DC
DC
: p∗
⊥
The natural transformation α : f → Fp = Lanpf ◦ p = p∗
Lanpf plays the
role of the unit of this adjunction.
Definition Dually, there is a definition for right Kan extension. Given f and p as
above, we say that a right Kan extension of f along p is a pair (F, α),
where α : Fp ⇒ f such that for any other pair (G, β), where G : C → D
and β : Gp ⇒ f there is a unique natural transformation γ : G ⇒ F such
that β = α ◦ γp.
In this case, provided all the relevant right Kan extensions exist, there is
an adjunction
p∗
: DC
DC
: Ranp⊥
Remark Kan extensions do not always exist, but of course when they do they are
unique up to natural isomorphism. However, there are some circumstances
in which the existence of Kan extensions is granted.
The most usual is in the assumption that C is small and D is cocomplete.
In this case, a left Kan extension Lanpf always exists, and it can be
computed by the following formula for an object C ∈ C : first take the
pullback square
39
C/C C/C
C C
πC
p
and then define Lanpf(C) := colim fπC. In other words, we take the
colimit of all objects of C that live over C via the functor p.
The natural map α is defined objectwise as the inclusion in the colimit.
Exercise Show that, if C is small, D is cocomplete and moreover p is a full embedding,
then α is an isomorphism.
Solution In the case above, we are enabled to use the colimit formula. Moreover, if
C ⊆ C is a full subcategory, then for an object C ∈ C the category C/C is
an honest slice category, so it has a terminal object. Therefore, the colimit
of fπC must be the image of its terminal object, which is f(C).
Remark Another way to phrase this is saying that if p is a full embedding then the
diagram
C D
C
p
f
Lanpf
commutes (up to isomorphism).
Week 11
The (co)limit formula We want to show that, in a diagram
C D
C
p
f
where C is small and D is cocomplete, the mentioned colimit formula
actually gives a left Kan extension of f along p.
For an object X ∈ C , we denote by C/X the category whose objects are
pairs (M, s : p(M) → X) with M being an object of C, and where a
morphism from (M, s) to (M , s ) is a morphism M → M in C such that
the triangle
p(M) p(M )
X
s s
40
commutes. This category has an obvious forgetful functor πX : C/X → C.
Then define F(X) := colim fπX. A morphism X → Y in C induces a
functor C/X → C/Y by postcomposition, and the triangle
C/X C/Y
C
πX πY
obviously commutes. This means that colim fπY is the vertex of a cocone
on the diagram fπX, therefore there is a unique factorization colim fπX →
colim fπY . All this defines a functor F : C → D. Moreover, for an object
A ∈ C, the indexing diagram of Fp(A) is given by objects M ∈ C with
a morphism p(M) → p(A), so that A itself is such an object. Therefore,
there is a colimit inclusion αA : f(A) → colim fπp(A), which is natural in
A and therefore defines α : f ⇒ Fp. We want to prove that this has the
universal property of Kan extensions.
Assume that we are given another functor G : C → D with a natural
transformation β : f ⇒ Gp. Given an object (M, s) ∈ C/X, we have a
composite morphism
f(M) Gp(M) G(X)
βM Gs
and, since β is natural and Gs is compatible with morphisms in C/X by
definition, this defines a cocone on fπX with vertex G(X). The universal
property of colimits now yields a unique factorization morphism γX :
colim fπX → G(X), which is readily verified to be natural in X by the
same universal property. Moreover, for an object A ∈ C, the triangle
f(A)
colim fπp(A) Gp(A)
αA
βA
γp(A)
commutes. Incidentally, this also proves that γ is uniquely determined in
the image of p. It remains to show that it is uniquely determined on all
C .
For this, take another natural transformation γ : F ⇒ G with the property
that γ p ◦ α = β. We want to show that for each X ∈ C it must be
γX = γX. Consider such an object X and its corresponding component
γX : F(X) → G(X). If C/X is empty, then F(X) = colim ∅ which is an initial
object, so there is no choice for γX. Otherwise, for every (M, s) ∈ C/X
we have a commutative diagram
41
Fp(M) Gp(M)
f(M)
F(X) G(X)
γp(M)
F (s) G(s)
αM
γX
which exhibits γX as the unique factorization of the cocone
(Gs ◦ γp(M) ◦ αM )(M,s)∈C/X
= (Gs ◦ βM )(M,s)∈C/X
.
But this was precisely γX by definition, so we are done.
Remark Dually, if we assume that D is complete instead of cocomplete, we get a
limit formula for right Kan extensions, so for an object X ∈ C we will
have
Ranpf(X) = lim fπX
where πX is now the projection CX/ → C.
Corollary As we have already shown, this implies that, with the additional hypothesis
that p is fully faithful, then Fp(A) ∼= f(A) for every A ∈ C.
Example Let K be a locally λ-presentable category, and let Kλ
be its full subcategory
of λ-compact objects. Then the diagram
Kλ
K
SetKλop
y
i
gives rise to an adjunction Lanyi Laniy.
To see this, note that the colimit formula applies in both cases, so we have
an explicit way of computing the two Kan extensions. In the first case,
given F ∈ SetKλop
, we have
Lanyi(F) ∼= colim iπF = colimKj ∈Kλ
/F
Kj
which is precisely the functor L from last week.
The computation for the other functor, given an object K ∈ K, is
Laniy(K) ∼= colim yπK = colimKj ∈Kλ
/K
K(−, Kj)
but since this functor only takes values in λ-compact objects, and the
category Kλ
/K is λ-filtered, this isomorphic to the functor represented by
colimKj ∈Kλ
/K
K, which is precisely the E of last week. We conclude by
remembering that we already know that L E is an adjunction.
42
Remark The same proof applies to a more general result. Given a functor p : C →
D, where C is small and D is cocomplete, then there is an adjunction
Lanyp : SetCop
D : Lanpy⊥
Example Special cases of the above whose role is of the greatest importance are the
adjunctions h : sSet Cat : N and | − | : sSet Top : Sing.
Example If K is locally λ-presentable and i : Kλ
→ K is the inclusion, then we have
Lanii ∼= idK, which can be seen directly by applying the colimit formula.
This suggests an alternative, equivalent definition of density of a subcategory.
We say that a subcategory C0 ⊆ C is dense if the left Kan extension
of the inclusion along itself is isomorphic to the identity on C.
Example Consider a functor f : C → D. A left Kan extension of f along the
terminal map C → • is a functor • → D which selects a colimit of f. In
fact, this can be taken as an equivalent definition of colimit.
Dually, right Kan extensions of f classify limits of f.
Example A functor F : C → D has a left adjoint if and only if RanF idC exists, in
which case the Kan extension is itself a left adjont. Similarly, F has a
right adjoint if and only if LanF idC exists.
Note the mismatch between the direction of the extensions and the resulting
adjoint functors. This is essentially due to the direction of the corresponding
units and counits. Indeed, assuming for instance that RanF idC
exists, then the natural map α : RanF idC ◦ F → idC has the direction of a
counit, so the right Kan extension is a left adjoint.
Example This technology can be used to prove the universal property of the free
cocompletion in a slick way. Since the Yoneda embedding is fully faithful,
we know that y∗
Lany
∼= id. Now take a small category C and a cocomplete
category D, and observe that, for two functors f, g : C → D, we have
DP(C)
(Lanyf, Lanyg) ∼= DC
(f, y∗
Lanyg) ∼= DC
(f, g)
which means that the functor Lany : Fun(C, D) → Fun(P(C), D) is fully
faithful, so that there is an equivalence of categories with the image
Fun(C, D) FunLan
(P(C), D).
It only remains to show that a functor F : P(C) → D is a left Kan
extension if and only if it preserves colimits. One direction is true because
such left Kan extensions are always left adjoint, as seen above, therefore
they preserve colimits. For the other direction, observe that, defining
f = Fy, the condition that F preserves colimits forces it to be defined via
the colimit formula (because every presheaf is a colimit of C/F ), so it is
automatically a left Kan extension of f.
43
Week 12
Lambek’s lemma For an endofunctor T : C → C, if i : TI → I is an initial T-algebra, then i
is an isomorphism.
Proof Consider the diagram
TI T2
I TI
I TI I
i
where both composites in the right square are i ◦ Ti, and the horizontal
morphisms in the left triangle are uniquely given by initiality of i among
T-algebras.
In particular, we have an arrow s : I → TI and, by uniqueness of morphisms
from i in T-Alg, the lower horizontal composite must be the identity,
so is = idI. Moreover, the upper horizontal composite says that
Ti ◦ Ts = idT I, and the left square says that Ti ◦ Ts = si, so that we may
conclude si = idT I, and s is a two-side inverse of i.
Exercise Check that, given an adjunction L : C D : R, the composite functor
RL indeed gives a monad on C.
Solution We call T := RL. Now, the multiplication µ : T2
→ T and the unit
η : id → T of the monad will be defined respectively as
RεL : RLRL → RL
η : id → RL.
We need to show the associativity and the unitality axioms. The first
amounts to showing that the diagram
RLRLRLC RLRLC
RLRLC RLC
RLRεLC
RεLRLC
RεLC
RεLC
commutes for every object C ∈ C. By an application of R, it clearly
suffices to show that the diagram
LRLRLC LRLC
LRLC LC
LRεLC
εLRLC
εLC
εLC
commutes. It will be enough to show that both composites correspond to
the same morphism RLRLC → RLC via the adjunction L R. Using the
notation ˜− for adjunct morphisms and remembering that adjunctions are
natural in both variables, we obtain that the right-then-down composite
corresponds to
44
RεLC ◦ ˜εLRLC = RεLC
since εLRLC corresponds to idRLRLC by definition. The down-then-right
composite corresponds to
˜εLC ◦ RεLC = RεLC
since, similarly, εLC corresponds to idRLC. This concludes the verification
of associativity.
As for unitality, we will need an alternative characterization of adjunctions.
With the data of two functors and two natural transformations
with the same domains and codomains as the unit and counit, we have an
adjunction if and only if the two triangles of natural transformations
LRL
L L
εLLη
idL
RLR
R R
RεηR
idR
commute. They are often called the triangular identities. Now back to
the case at issue, we need to check that the two triangles
RLC RLRLC RLC
RLC
RLηC
idRLC
RεLC
ηRLC
idRLC
commute for every object C ∈ C. The left one is simply the former triangular
identity applied to the object C and then plugged into the functor
R. The right one is the latter triangular identity applied to the object
LC.
Definition Recall the definition of the category of algebras and its universal property.
Given a monad (T, µ, η) on a category C, a T-algebra is an object C ∈ C
with a morphism h : TC → C such that the diagrams
T2
C TC
TC C
µC
T h
h
h
C TC
C
µC
idC
h
commute. A homomorphism of T-algebras is a morphism in C that is
compatible with the algebra structures in the obvious way. This defines
a category, called the category of T-algebras and usually denoted by CT
.
There is a free-forgetful adjunction F : C CT
: U.
Theorem The category of T-algebras is universal among all adjunctions that give rise
to the monad T, in the following sense. Given an adjunction L : C D : R
that induces the monad T, then there is a unique functor K : D → CT
such that KL = F and UK = R. In other words, in the diagram
45
D CT
C
R
K
UL
F
the two triangles comprising respectively both left adjoints and both right
adjoints commute.
Remark This means that the category of T-algebras is terminal among adjunctions
inducing T. We will now see that there is also an initial such category.
Definition Given a monad as above, we define its Kleisli category CT as follows.
The objects are the same as those of C, but conventionally denoted as
CT , DT . . ., and a morphism fT : CT → DT is precisely a morphism
f : C → TD in C. The composite of fT : CT → DT and gT : DT → ET is
defined as
µE ◦ Tg ◦ f : C → TD → T2
E → TE.
Exercise Check that the Kleisli category is indeed a category.
Solution We first check that composition is associative. Take morphisms
CT DT ET FT .
fT gT hT
Unwinding the definitions, we see that hT ◦ (gT ◦ fT ) is given by
C TD T2
E TE T2
F TF
f T g µE T h µF
while (hT ◦ gT ) ◦ fT is given by
C TD T2
E T3
F T2
F TF.
f T g T 2
h T µF µF
It suffices to show that they are already equal when leaving the first two
components out.
For this, observe that there is a diagram
T2
E T3
F T2
F
TE T2
F TF
µE
T 2
h
µT F
T µF
µF
T h µF
where both squares commute by naturality of µ. The outer square gives
precisely the equation that we want.
As for unitality, let us define the identity on CT as the morphism ηC :
C → TC. For one side, need to verify that the composite
C TD T2
D TD
f T ηD µD
46
equals f, which follows directly by one of the unitality axioms of T. For
the other side, we need to verify that the composite
C TC T2
D TD
ηC T f µD
equals f, which follows by observing that Tf ◦ ηC = ηT C ◦ f by naturality
of η, and then applying the other unitality axiom of T.
Exercise Show that there is an adjunction FT : C CT : GT where
FT sends f : C → D to ηD ◦ f : C → TD;
GT sends fT : CT → DT to µD ◦ Tf : TC → TD.
Solution We will only show the bijection between homsets, leaving naturality as a
routine computation. Observe that, when considering only their actions
on objects, FT is the identity and GT corresponds with T. Now compute
CT (FT C, D) ∼= CT (C, D) ∼= C(C, TD) ∼= C(C, GT D).
Exercise Show that, whenever there is an adjunction L : C D : R whose induced
monad on C is T, then there is a unique comparison functor H : CT → D
such that in the diagram
CT D
C
GT
H
RFT
L
the two triangles comprising respectively both left adjoints and both right
adjoints commute.
Solution Since, FT is the identity on objects, the condition HFT = L forces the
assignment H : CT → LC. Since RL = T, we also have RH(C) =
RL(C) = T(C) = GT (CT ), so the other triangle commutes on objects.
Now suppose that H has been defined, and look at the following diagram
CT (CT , DT ) D(LC, LD)
C(RLC, RLD) C(C, RLD)
H
GT
R
η∗
C
which commutes by remembering that RH = GT . Note that the adjunctions
FT GT and L R have the same unit η, so by general
properties of adjunctions we have that the composite η∗
C ◦ GT transposes
morphisms with respect to the former, while the composite η∗
C ◦ R transposes
morphisms with respect to the latter. In other words, the functor
H must preserve transpositions. This forces the action of H on morphisms
as follows. A morphism fT : FT C = CT → DT is the transpose of
f : C → TD = GT D, therefore H must send it to the transpose of f with
respect to the other adjunction, that is, to the composite
47
LC LRLD LD.
Lf εLD
Another routine argument will show that this is indeed functorial, and
we already saw that RH = GT . We need to show that HFT = L also
on morphisms. But the left-hand side, when computed on a morphism
f : C → D, gives
LC LD LRLD LD
Lf LηD εLD
so the result follows by one of the triangular identities.
Week 13
Exercise Let StrMon be the category of strict monoidal categories (the associators
and unitors are identities) and strict monoidal functors. There is a
forgetful functor U : StrMon → Cat. Prove that it has a left adjoint.
Solution One can use the adjoint functor theorem with a direct check, taking all
strict monoidal categories of the same size as one given category as its
solution set.
More explicit, one can define the free strict monoidal category SM(C) on a
category C as follows: its objects are finite ordered sequences of objects of
C. A morphism from (C0, . . . , Cn) to (D0, . . . , Dm) is an order-preserving
map α : n → m with morphisms Ci → Dα(i), for each i = 0, . . . , n. The
tensor product is given by concatenation. The reflection C → SM(C)
sends every morphism f : C → D to f : (C) → (D).
Since strict monoidal functors must strictly preserve tensor products, a
functor C → M where M is strictly monoidal determines a unique assignment
SM(C) → M on objects. Moreover, since morphisms in SM(C)
are determined by morphisms in C, a whole functor SM(C) → M is thus
already determined, and it is unique with the property that the diagram
C M
SM(C)
commutes.
Example Similarly, we can define a free weak monoidal category functor. This
time, an object in WM(C) will be a finite planar binary tree T (where
every branch splits into at most two subbranches and there is a total
ordering on the set of leaves) with a map leaf(T) → ob(C). Morphisms
are generated by the ones described above, with α : leaf(T) → leaf(S),
plus unique morphisms (which are necessarily isomorphisms) whenever
there is a commutative triangle
48
leaf(T) leaf(S)
ob(C)
∼=
with the horizontal arrow being an order-preserving map. The proof that
this is the correct definition is similar to the one above but slightly more
complicated.
Example In a yet similar way, it is possible to define a free weak symmetric monoidal
category functor. Keeping in mind the construction above, we modify it by
instead freely adding to it unique morphisms (necessarily isomorphisms)
whenever there are diagrams
leaf(T) leaf(S)
ob(C)
∼=
where the horizontal map is no longer required to preserve the order rela-
tion.
Example A key example of closed symmetric monoidal category is the category
CGHaus of compactly generated Hausdorff spaces. A topological space
X is compactly generated when a subspace A ⊆ X is closed precisely if
its intersection A ∩ K with every compact subspace K ⊆ X is compact.
The category of compactly generated Hausdorff spaces corrects the ill behavior
or Top in this respects: under the product-exponential adjunction
of underlying sets
Map(X × Y, Z) ∼= Map(X, ZY
)
continuous maps do not in general transpose to continuous maps in either
direction. Therefore, Top is not Cartesian closed.
A lengthy proof shows that, in addition to being complete, cocomplete
and coreflective in Haus, the category CGHaus is Cartesian closed. The
exponential ZY
is given as follows: the underlying set is Top(Y, Z), and
a subbase for the topology is given by all sets N(K, U), where K ⊆ Y is
compact, U ⊆ Z is open and N(K, U) is the set of all maps f : Y → Z
such that f(K) ⊆ U.
Weak Yoneda lemma Recall that the underlying category C0 of C is given by taking the same
objects and V(1, C(C, D)) as morphisms between C and D. Moreover,
there is a functor (−)0 = V(1, −) : V → Set.
Let F : C → V be a V-functor. Then for every object C ∈ C there is a
bijection
(FC)0
∼= V − Nat(C(C, −), F).
49
Remark Although this bijection is natural in C, we have no way yet to say that
it is natural in F, because we haven’t defined enriched functor categories.
What we lack for the moment is a V-object of natural transformations, in
that we only have a way to define a set of such.
Moreover, this version of the enriched Yoneda lemma only gives a bijection
of sets, so it still relies on the structure of ordinary underlying categories
and thus does not employ the full power of the enrichment.
In what follows, we will fix these two problems in one shot, by defining
V-objects of natural transformations and by giving a stronger version of
the enriched Yoneda lemma that solely stands on the enriched structure
of our objects.
Definition Let C and D be categories, and let S, T : Cop
× C → D be two functors.
A dinatural transformation S → T is an assignment of a morphism αC :
S(C, C) → T(C, C) for every object C ∈ C in such a way that for every
morphism f : C → C there is a commutative diagram
S(C, C) T(C, C)
S(C , C) T(C, C )
S(C , C ) T(C , C ).
αC
T (1,f)S(f,1)
S(1,f)
αC
T (f,1)
Example If the two functors ignore either the first or the second variable, then we
are reduced to a natural transformation of covariant and contravariant
functors respectively.
Example Suppose that S is the constant functor at D ∈ D. Then the dinaturality
diagrams above reduces to a family of maps (αC : D → T(C, C))C∈C such
that the diagrams
D T(C, C)
T(C , C ) T(C, C )
αC
αC T (1,f)
T (f,1)
are commutative. This is sort of a two-variable version of a cone, and it
is known as a wedge on T with vertex D.
Definition Let T : Cop
× C → D be a functor. We say that an end of T is a wedge on
T which is final among such wedges. We write it as
C∈C
T(C, C).
It does not always exist, but it is of course unique whenever it does.
50
Remark We might be tempted to write an end of a functor as a limit of some sort.
In fact, this is always possible in the following way. Define the twisted
category Tw(C) of C as the category having for objects the set of symbols
C♣
for every object C ∈ C and f♣
for every morphism f ∈ C. The only
morphisms in Tw(C) are the identities plus morphisms
C♣
→ f♣
← D♣
for every morphism f : C → D.
Now let us define a functor T♣
: Tw(C) → D as
C♣
f♣
D♣
T(C, C) T(C, D) T(D, D).
T (1,f) T (f,1)
A direct verification will yield that C∈C
T(C, C) ∼= lim T♣
.
Example We use the description above in a very specific case. Consider the homfunctor
D(−, −) : Dop
×D → Set and, furthermore, consider two functors
F, G : C → D. Precomposing the functor Fop
× G to the hom-functor
gives D(F−, G−) : Cop
× C → Set. Remembering the construction above
and the explicit construction of limits in Set, we obtain that there is an
isomorphism
C∈C
D(FC, GC) ∼= Nat(F, G).
This motivates the following definition in the case of enriched categories.
Definition Let V be a closed symmetric monoidal category, and let C and D be Vcategories.
Then we can define the V-enriched functor category Fun(C, D)
in the following way.
An object is a V-functor F : CtoD. Given two such V-functors F and G,
the V-object of natural transformations from F to G is given as the end
of the composite functor
Cop
× C Dop
× D V.
F op
×G D(−,−)
In other words, we define
Nat(F, G) := C∈C
D(FC, GC)
and composition is given by universal property of ends.
Strong Yoneda lemma Let F : C → V be a V-functor. Then for every C ∈ C there is a natural
isomorphism
FC ∼= Nat(C(C, −), F)
which is natural in both C and F.
51