Category Theory - Cambridge III notes

Category Theory
Daniel Naylor

1Definitions and Examples
2The Yoneda Lemma
3Adjunctions
4Limits
5Monads
6Filtered Colimits
7Regular Categories
Index

1 Definitions and Examples

Definition 1.1 (Category). A category $C$ consists of:

(a)
a collection $ob C$ of objects $A, B, C, \dots$ .
(b)
a collection $mor C$ of morphisms $f, g, h, \dots$ .
(c)
two operations $dom$ , $cod$ from $mor C$ to $ob C$ : we write $f : A \to B$ for “ $f$ is a morphism and $dom f = A$ and $cod f = B$ ”.
(d)
an operation from $ob C$ to $mor C$ sending $A$ to $1_{A} : A \to A$ .
(e)
a partial binary operation $(f, g) \mapsto f g$ on $mor C$ , such that $f g$ is defined if and only if $dom f = cod g$ , and in this case we have $dom f g = dom g$ and $cod f g = cod f$ .

These are subject to the axioms:

(f)
$f 1_{A} = f$ and $1_{A} g = g$ when the composites are defined.
(g)
$f (g h) = (f g) h$ whenever $f g$ and $g h$ are defined.

Remark 1.2.

(a) $ob C$ and $mor C$ needn’t be sets. If they are, we call $C$ a small category.
(b) We could formalise the definition without mentioning objects, but we don’t.
(c) $f g$ means “first $g$ , then $f$ ”.

Example 1.3.

(a) $S e t =$ category of all sets and the functions between them. (Formally, a morphism of $S e t$ is a pair $(f, B)$ where $f$ is a set-theoretic function, and $B$ is its codomain.)
(b) We have categories:
- $G r o u p$ of groups and group homomorphisms
- $R n g$ of rings and homomorphisms
- ${V e c t}_{k}$ of vector spaces over a field $k$
- and so on
(c) We have categories
- $T o p$ of topological spaces and continuous maps
- $M e t$ of metric spaces and non-expansive maps (i.e. $f$ such that $d (f (x), f (y)) \leq d (x, y)$ )
- $M f d$ of smooth manifolds and $C^{\infty}$ maps
Also $T o p G p$ for topological groups and continuous homomorphisms, etc...
(d) We have a category $H t p y$ with the same objects as $T o p$ , but morphisms $X \to Y$ are homotopy classes of continuous maps.
In general, given $C$ and an equivalence relation $\equiv$ on $mor C$ such that
$f \equiv g ⟹ dom f = dom g and cod f = cod g$

and
$f \equiv g ⟹ f g \equiv g h and k f \equiv k g when the composites are defined$

we can form a quotient category $C ∕ \equiv$ .
(e) The category $R e l$ has the same objects as $S e t$ , but morphisms $A \to B$ are relations $R \subseteq A \times B$ , with composition defined by
$R \circ S = {(a, c) | (\exists b) (a, b) \in S \land (b, c) \in R} .$

We can also define the category $P a r t$ of sets with partial functions.
(f) For any category $C$ , the opposite category $C^{o p}$ has the same objects and morphisms as $C$ but $dom$ and $cod$ are interchanged and composition is reversed.
This yields a duality principle: if $P$ is a true statement about categories, so is $P^{*}$ obtained by reversing arrows in $P$ .
(g) A (small) category with one object $*$ is a monoid (a semigroup with an identity). In particular, a group is a $1 -$ object small category whose morphisms are all isomorphisms.
(h) A groupoid is a category whose morphisms are all isomorphisms. For example, the fundamental groupoid $π_{1} (X)$ of a topological space $X$ has points of $X$ as objects, and morphisms $x \to y$ are homotopy classes of paths from $x$ to $y$ (c.f. the fundamental group $π_{1} (X, x)$ ).
(i) A discrete category is one whose only morphisms are identities. If $C$ is such that for any pair of objects $(A, B)$ there is at most one morphism $A \to B$ then $mor C$ becomes a reflexive, transitive relation on $ob C$ . We call such a $C$ a preorder. In particular, a poset is a small preorder whose only isomorphisms are identities.
(j) Given a field $k$ , the category ${M a t}_{k}$ has natural numbers as objects, and morphisms $n \to p$ are $p \times n$ matrices, with entries from $k$ , and composition is matrix multiplication.

Definition 1.4 (Functor). Let $C$ and $D$ be categories. A functor $F : C \to D$ consists of mappings $F : ob C \to ob D$ and $F + mor C \to mor D$ such that:

$F (dom f) = dom F f$
$F (cod f) = cod F f$
$F (1_{A}) = 1_{F A}$
$F (f g) = (F f) (F g)$ whenever $f g$ is defined.

We write $Cat$ for the category of small categories and the functors between them.

Example 1.5.

(a) We have forgetful functors $G p \to S e t$ , $R n g \to S e t$ , $T o p \to S e t$ , … or slightly more interestingly, $R n g \to A b G p$ , $M e t \to T o p$ , $T o p G p \to T o p$ , $T o p G p \to G p$ , …
(b) The construction of free groups is a functor $S e t \to G p$ : given a set $A$ , $F A$ is the group freely generated by $A$ , such that every mapping $A \to G$ where $G$ has a group structure extends uniquely to a homomorphism $F A \to G$ . Given $A \overset{f}{\to} B$ , we define $F f : F A \to F B$ to be the unique homomorphism extending $A \overset{f}{\to} B ↪ F B$ . If we also have $B \overset{g}{\to} C$ , $F (g f)$ and $(F g) (F f)$ are both homomorphisms extending $A \overset{f}{\to} B \overset{g}{\to} C ↪ F C$ .
(c) Given a set $A$ , we define $P A$ to be the set of subsets of $A$ . Given $f : A \to B$ , we define $P f : P A \to P B$ by $P f (A^{'}) = f (a) | a \in A^{'} \subseteq B$ . So $P$ is a functor $S e t \to S e t$ .
(d) But we also have a functor $P^{*} : {S e t}^{o p} \to S e t$ (or $S e t \to {S e t}^{o p}$ ): $P^{*} A = P A$ and, for $A \overset{f}{\to} B$ , $G^{*} f : P B \to P A$ is given by $P^{*} f (B^{'}) = a i n A | f (a) \in B^{'}$ . We use the term “contravariant functor $C \to D$ ” for a functor $C \to D^{o p}$ .
(e) Given a vector space $V$ over $k$ , we write $V^{*}$ for the space of linear maps $V \to k$ . Given $f : V \to W$ , we write $f^{*} : W^{*} \to V^{*}$ for the mapping $𝜃 \mapsto 𝜃 f$ . This defines a functor ${(∙)}^{*} : {V e c t}_{k}^{o p} \to {V e c t}_{k}$ .
(f) The mapping $C \mapsto C^{o p}$ , $F \mapsto F$ defines a functor $C a t \to C a t$ .
(g) A functor between monoids is a monoid homomorphism; a functor between posets is a monotone map.
(h) Given a group $G$ , a functor $G \to S e t$ is given by a set $A$ equipped with a $G$ -action $(g, a) \mapsto g \cdot a$ , i.e. a permutation representation of $G$ . Similarly, a functor $G \to {V e c t}_{k}$ is a $k$ -linear representation of $G$ .
(i) The fundamental group construction is a functor $Π_{1} : {T o p}_{*} \to G p$ , where ${T o p}_{*}$ is the category of topological spaces with basepoints, and morphisms being the continuous maps which preserve the basepoints.

Definition 1.6 (Natural transformation). Given categories $C$ and $D$ , and two functors $C ⇉_{G}^{F} D$ , a natural transformation $α : F \to G$ assigns to each $A \in ob C$ a morphism $α_{A} : F A \to G A$ in $D$ , such that for any $A \overset{f}{\to} B$ in $C$ , the square

commutes (we call this square the naturality square for

α

f

). Given

α

as above, and

β : G \to H

, we define

β α : F \to H

{(β α)}_{A} = β_{A} α_{A}

. We write

[C, D]

for the category of functors

C \to D

and natural transformations between them.

Example 1.7.

(a) Given a vector space $V$ , we have a linear map $α_{V} : V \to V^{* *}$ sending $v \in V$ to the linear form $𝜃 \mapsto 𝜃 (v)$ on $V^{* *}$ . These maps define a natural transformation $1_{{V e c t}_{k}} \to {(∙)}^{* *}$ .
(b) There is a natural transformation $α : 1_{S e t} \to U F$ , where $F$ is the free group functor and $U$ is the forgetful functor $G p \to S e t$ , whose value at $A$ is the inclusion $A ↪ U F A$ . The naturality square
commutes by the definition of $F f$ .
(c) For any $A$ , we have a mapping $η_{A} : A \to P A$ given by $A η_{A} (a) = {a}$ . This is a natural transformation $1_{S e t} \to P$ since $P f ({a}) = {f (a)}$ for any $a \in A$ .
(d) Given order-preserving maps $P ⇉_{g}^{f} Q$ between posets, there exists a unique natural transformation $f \to g$ if and only if $f (p) \leq g (p)$ for all $P \in P$ .
(e) Given two group homomorphisms $G ⇉_{v}^{u} H$ , a natural transformation $u \to v$ is given by $h \in H$ such that $h u (g) = v (g) h$ for all $g \in G$ , or equivalently $u (g) = h^{- 1} v (g) h$ , i.e. $u$ and $v$ are conjugate homomorphisms. In particular, the group of natural transformations $u \to u$ is the centraliser of the image of $u$ .
(f) If $A$ and $B$ are $G$ -sets considered as functors $G \to S e t$ , a natural transformation $f : A \to B$ is a $G$ -invariant map, i.e. $f : A \to B$ such that $g f (a) = f (g a)$ for all $a \in A$ , $g \in G$ .
(g) The Hurewicz homomorphism links the homotopy and homology groups of a space $X$ . Elements of $π_{n} (X, x)$ are homotopy classes of basepoint-preserving maps $S^{n} \overset{f}{\to} X$ . If we think of $S^{n}$ as $\partial Δ^{n + 1}$ , $f$ defines a singular $n$ -cycle on $X$ and homotopic maps differ by an $n$ -boundary, so we get a well-defined map $π_{n} (X, x) \overset{h_{n}}{\to} H_{n} (X)$ . $h_{n}$ is a homomorphism, and it’s a natural transformation $π_{n} \to H_{n} U$ , where $U$ is the forgetful functor ${T o p}_{*} \to T o p$ .

We have isomorphisms of categories: e.g. $F : R e l \to {R e l}^{o p}$ defined by $F A = A$ , $F R = R^{o} = {(b, a) | (a, b) \in R}$ is its own inverse.

But we have a weaker notion of equivalence of categories.

Lemma 1.8. Assuming that:

$α : F \to G$ is a natural transformation between functors $C ⇉_{}^{} D$

Then

α

is an isomorphism in

[C, D]

if and only if

α_{A}

is an isomorphism in

D

for each

A

Proof.

$\Rightarrow$ Obvious since composition in $[C, D]$ .
$\Leftarrow$ Suppose each $α_{A}$ has an inverse $β_{A}$ . Given $A \overset{f}{\to} B$ in $C$ , in the diagram
we have $β_{B} (G f) = β_{B} (G f) α_{A} β_{A} = β_{B} α_{B} (F f) β_{A} = (F f) β_{A}$ . □

Definition 1.9 (Equivalence of categories). Let $C$ and $D$ be categories. An equivalence between $C$ and $D$ consists of functors $F : C \to D$ and $G : D \to C$ together with natural isomorphisms $α : 1_{C} \to G F$ , $β : F G \to 1_{D}$ . We write $C \equiv D$ if there exists an equivalence between $C$ and $D$ .

We say $P$ is a categorical property if

(C has P and C \equiv D) ⟹ D has P .

Example 1.10.

(a) The category

P a r t

of sets and partial functions is equivalent to

{S e t}_{*}

(the category of pointed sets). We define

F : {S e t}_{*} \to P a r t

F (A, a) = A ∖ {a}

and if

f : (A, a) \to (B, b)

, with

(F f) (x) = f (x)

f (x) \neq b

and undefined otherwise. Then define

G : P a r t \to {S e t}_{*}

G (A) = (A \cup {A}, A)

and if

f : A ⇁ B

, then

G f (x) = {\begin{matrix} f (x) & if x \in A and f (x) is defined \\ B & otherwise \end{matrix} .

Then $F G = 1_{P a r t}$ ; $G F \neq 1_{{S e t}_{*}}$ , but there is an isomorphism $1_{{S e t}_{*}} \to G F$ . Note that $P a r t ⁄ ≅ {S e t}_{*}$ .

(b) We have an equivalence ${f d V e c t}_{k} \equiv {f d V e c t}_{k}^{o p}$ : both functors are ${(∙)}^{*}$ , and both isomorphisms are $α : 1_{{f d V e c t}_{k}} \to {(∙)}^{* *}$ .
(c) We have an equivalence ${f d V e c t}_{k} \equiv {M a t}_{k}$ : we define $F : {M a t}_{k} \to {f d V e c t}_{k}$ by $F (n) = k^{n}$ , $F (n \overset{A}{\to} p)$ is the linear map $k^{n} \to k^{p}$ represented by $A$ (with respect to standard bases). TO define $G$ , choose a basis for each $V$ , and define $G (V) = \dim V$ ,
$G (V \overset{f}{\to} W) = matrix representing f with respect to chosen bases .$

$G F = 1_{{M a t}_{k}}$ ; the choice of bases yields isomorphisms $k^{\dim V} \to V$ for each $V$ , which form a natural transformation $F G \to 1_{{f d V e c t}_{k}}$ .

Definition 1.11 (Faithful / full / essentially surjective). Let $F : C \to D$ be a functor.

(a)
We say $F$ is faithful if, given $f$ and $g$ in $mor C$ , $(F f = F g$ , $dom f = dom g$ , $cod f = cod g) ⟹ f = g$ .
(b)
We say $F$ is full if, for every $g : F A \to F B$ in $D$ , there exists $f : A \to B$ in $C$ with $F f = g$ .
(c)
We say $F$ is essentially surjective if, for any $B \in ob D$ , there exists $A \in ob C$ with $F A ≅ B$ .

Note that if $F$ is full and faithful, it’s essentially injective: given $F A \to_{≅}^{g} F B$ in $D$ , the unique $A \overset{f}{\to} B$ with $F f = g$ is an isomorphism.

We say $D \subseteq C$ is a full subcategory if the inclusion $D \to C$ is a full functor.

Lemma 1.12. Assuming that:

$F : C \to D$

Then

F

is part of an equivalence

C \equiv D

if and only if

F

is full, faithful, essentially surjective.

Proof.

$\Rightarrow$ Suppose give $G$ , $α$ and $β$ as in Definition 1.9. Then $β_{B} : F G B \to B$ witnesses the fact that $F$ is essentially surjective. If $A ⇉_{g}^{f} B$ satisfy $F g = F g$ , then $G F f = G F g$ ; but $f = α_{B}^{- 1} (G F f) α_{A}$ , so $f = g$ . Suppose given $F A \overset{g}{\to} F B$ ; then $f = α_{B}^{- 1} (G g) α_{A}$ satisfies $G F f = G f$ but $G$ is faithful for the same reason as $F$ , so $F f = g$ .
$\Leftarrow$ For each $B \in ob D$ , chose $G B \in ob C$ and an isomorphism $β_{B} : F G B \to B$ . Given $B \overset{g}{\to} C$ , define $G g : G B \to G C$ to be the unique morphism such that $F G g = β_{C}^{- 1} g β_{B}$ . Functoriality follows from uniqueness, and naturality of $β$ . We define $α_{A} : A \to G F A$ to be the unique morphism such that $F α_{A} = β_{F A}^{- 1} : F A \to F G F A$ . $α_{A}$ is an isomorphism, and naturality squares for $α$ are mapped by $F$ to naturality squares for $β^{- 1}$ , so they commute. □

Definition 1.13 (Skeleton). By a skeleton of a category $C$ , we mean a full subcategory containing just one object from each isomorphism class.

We say $C$ is skeletal if it’s a skeleton of itself.

Example. ${M a t}_{k}$ is a skeletal category; it’s isomorphic to the skeleton of ${f d V e c t}_{k}$ consisting of the spaces $k^{n}$ .

However, working with skeletal categories involves heavy use of the axiom of choice.

Definition 1.14 (Monomorphism / epimorphism). Let $f : A \to B$ be a morphism in a category $C$ . We say $f$ is a monomorphism (or monic) if, given $C ⇉_{h}^{g} A$ , $f g = f h ⟹ g = h$ . We say $f$ is an epimorphism (or epic) if it’s a monomorphism in $C^{o p}$ .

We write $A \overset{f}{↣} B$ to indicate that $f$ is monic, and $A \overset{f}{↠} B$ to indicate that it’s epic.

We say $C$ is balanced if every arrow which is monic and epic is an isomorphism.

We will call a monic morphism $e$ split if it has a left inverse (and similarly we may define the notion of split epic).

Example 1.15.

(a) In $S e t$ , monic $⟺$ injective ( $\Leftarrow$ obvious; for $\Rightarrow$ consider morphisms ${*} \to A$ ). Also, epic $⟺$ surjective ( $\Leftarrow$ obvious; for $\Rightarrow$ consider morphisms $B \to {0, 1}$ ).
(b) In $G p$ , monic $⟺$ injective (for $\Rightarrow$ consider homomorphisms $ℤ \to G$ ), and epic $⟺$ surjective (but $\Rightarrow$ is quite non-trivial – it uses free products with amalgamation).
(c) In $R n g$ , monic $⟺$ injective, but epic does not imply surjective (for example, consider $ℤ ↪ ℚ$ ).
(d) In $T o p$ , monic $⟺$ injective and epic $⟺$ surjective (as in $S e t$ ) but $T o p$ isn’t balanced.
(e) In preorder, all morphisms are monic and epic, so a preorder is balanced if and only if it’s an equivalence relation.

2 The Yoneda Lemma

Definition 2.1 (Locally small). We say a category $C$ is locally small if, for any two objects $A$ and $B$ , the morphisms $A \to B$ in $C$ are parameterised by a set $C (A, B)$ .

If $A$ is an object of a locally small category $C$ , we have a functor $C (A, ∙) : C \to S e t$ sending $B$ to $C (A, B)$ and a morphism $B \overset{g}{\to} C$ to the mapping $(f \mapsto g f) : C (A, B) \to C (A, C)$ (this is functorial since composition in $C$ is associative).

Dually, we have $C (∙, B) : C^{o p} \to S e t$ .

Lemma 2.2 (Yoneda). Assuming that:

$C$ is a locally small category
$A \in ob C$
$F : C \to S e t$ a functor

Then

(i) There is a bijection between natural transformations $C (A, ∙) \to F$ and elements of $F A$ .
(ii) Moreover, this bijection is natural in $A$ and $F$ .

Proof.

(i) Given $α : C (A, ∙) \to F$ , we define $Φ (α) = α_{A} (1_{A}) \in F A$ .
Given $x \in F A$ , we define $Ψ (x) : C (A, ∙) \to F$ by $Ψ {(x)}_{B} (f : A \to B) = F f (x) \in F B$ . This is natural in $B$ since $F$ is a functor: given $g : B \to C$ we have
$(F g) Ψ {(x)}_{B} (f) = (F g) (F f) (x) = F (g f) (x) = Ψ {(x)}_{C} (g f) .$

For any $x$ , $Φ Ψ (x) = Ψ {(x)}_{A} (1_{A}) = F 1_{A} (x) = x$ .

For any $α$ , $Ψ Φ {(α)}_{B} (f) = F f (α_{A} (1_{A})) = α_{B} (C (A, f) (1_{A}) = α_{B} (f)$ for all $f : A \to B$ . So $Ψ Φ (α) = α$ .
(ii) Later. Seeing examples of usage of (i) is interesting first. □

Corollary 2.3. Assuming that:

$C$ a locally small category

Then

A \mapsto C (A, ∙)

is a full and faithful functor

C^{o p} \to [C, S e t]

Proof. Substitute $C (B, ∙)$ for $F$ in Lemma 2.2(i): we have a bijection from $C (B, A)$ to the collection of natural transformations $C (A, ∙) \to C (B, ∙)$ .

For a given $f$ , the natural transformation $C (f, ∙)$ sends $g : B \to C$ to $g f$ , so this is functorial by associativity of composition $C$ .

Similarly, we have a full and faithful functor $C \to [C^{o p}, S e t]$ sending $A$ to $C (∙, A)$ . We call this the Yoneda embedding: it allows us to regard any locally small category $C$ as a full subcategory of a $S e t$ -valued functor category. □

Compare with Cayley’s Theorem in group theory (every group is isomorphic to a subgroup of a permutation group) and ‘Dedekind’s Theorem’ (every poset is isomorphic to a sub-poset of a power set).

Definition 2.4 (Representable). We say a functor $F : C \to S e t$ is representable if it’s isomorphic to a $C (A, ∙)$ for some $A$ . By a representation of $F$ , we mean a pair $(A, x)$ where $x \in F A$ is such that $Φ (x)$ is an isomorphism. We call $x$ a universal element of $F$ .

Corollary 2.5. Suppose $(A, x)$ and $(B, y)$ are both representations of $F$ . Then there is a unique isomorphism $A \overset{f}{\to} B$ such that $(F f) (x) = y$ .

Proof. $(F f) (x) = g$ is equivalent to saying that

commutes, so

f

must be the unique isomorphism, whose image under Yoneda is

Φ {(x)}^{- 1} Φ (y)

. □

Proof of Yoneda(ii).

Suppose for the moment that

C

is small, so that

[C, S e t]

is locally small. Given two functors

C \times [C, S e t] \to S e t

: the first sends an object

(A, F)

F A

, and a morphism

(A \overset{f}{\to} A^{'}, F \overset{α}{\to} F^{'})

to the diagonal of

The second is the composite

C \times [C, S e t] \overset{Y \times 1}{\to} {[C, S e t]}^{o p} \times [C, S e t] \overset{[C, S e t] (∙, ∙)}{\to} S e t

where $Y$ is a Yoneda embedding. Then $Φ$ and $Ψ$ define a natural isomorphism between these two.

In elementary terms, this says that if $x \in F A$ , and $x^{'} \in F^{'} A^{'}$ is its image under the diagonal, then $Ψ (x^{'})$ is the composite

C (A^{'}, ∙) \overset{C (f, ∙)}{\to} C (A, ∙) \overset{Ψ (x)}{\to} F \overset{α}{\to} F^{'} .

This makes sense without the assumption that $C$ is small, and it’s true since the composite maps

1_{A^{'}} \mapsto f \mapsto (F f) (x) \mapsto α_{A^{'}} (F f) (x) . □

Example 2.6.

(a) The forgetful functor $G p \to S e t$ is represented by $(ℤ, 1)$ , $R n g \to S e t$ is represented by $(ℤ [X], X)$ , $T o p \to S e t$ is represented by $({*}, *)$ .
(b) The functor $P^{*} : {S e t}^{o p} \to S e t$ is represented by $({0, 1}, {1})$ . This is the bijection between subsets of $A$ and functions $A \overset{f}{\to} {0, 1}$ , and it’s natural. But $P : S e t \to S e t$ is not representable, since $P ({*})$ isn’t a singleton.
(c) The functor $Ω : {T o p}^{o p} \to S e t$ sending $X$ to the set of open subsets of $X$ , and $X \overset{f}{\to} Y$ to $f^{- 1} : Ω (Y) \to Ω (X)$ is representable by the Sierpinski space $Σ = {0, 1}$ with ${1}$ open but ${0}$ not open. This works since continuous maps $X \to Ω$ are the characteristic functions of open subsets of $X$ .
(d) The functor ${(∙)}^{*} : {V e c t}_{k} \to {V e c t}_{k}$ isn’t representable, but its composite with ${V e c t}_{k} \to S e t$ is represented by $k$ .
(e) For a group $G$ considered as a $1$ -object category, the unique representable functor $G \to S e t$ is the Cayley representation: $G$ acting on itself by multiplication.
(f) Given two objects $A, B$ in a locally small category $C$ , we have a functor $C^{o p} \to S e t$ sending $C$ to $C (C, A) \times C (C, B)$ . If this functor is representable, we call the representing object a categorical product $A \times B$ and write $(π_{1} : A \times B \to A, π_{2} : A \times B \to B)$ for the universal element. Its defining property is that given any pair $(f : C \to A, g : C \to B)$ , there is a unique isomorphism $h : C \to A \times B$ such that $π_{q} h = f$ and $π_{2} h = g$ .
Dually, we have the notion of coproduct $A + B$ with coprojections $γ_{1} : A \to A + B$ , $γ_{2} : B \to A + B$ .
(g) Given a parallel pair $A ⇉_{g}^{f} B$ in a locally small category $C$ , we have a functor $F : C^{o p} \to S e t$ sending $C$ to ${h : C \to A | f h = g h}$ and defined on morphisms in the same way as $C (∙, A)$ .
A representation of this functor is called an equaliser of $(f, g)$ : it consists of $E \overset{e}{\to} A$ satisfying $f e = g e$ , and such that any $h$ with $f h = g h$ factors uniquely as $e k$ . Note that $e$ is monic; we call a monomorphism regular if it occurs as an equaliser.

Dually, we have the notions of coequaliser and regular epi.

In $S e t$ , products are just cartesian products (also in $G p$ , $R n g$ , $T o p$ , …). coproducts in $S e t$ are disjoint unions $A ∐ B = (A \times {0}) \cup (B \times {1})$ . In $G p$ , coproducts are free products $G * H$ .

In $S e t$ , the equaliser of $A ⇉_{g}^{f} B$ is the inclusion of ${a \in A | f (a) = g (a)}$ and the coequaliser of $(f, g)$ is the quotient of $B$ by the smallest equivalence relation containing ${(f (a), g (a)) | a + A}$ .

Note that in $S e t$ , all monomorphisms and all epimorphisms are regular, but in $T o p$ , a monomorphism $X \overset{f}{\to} Y$ is regular if and only if $X$ is topologised as a subspace of $Y$ . An epimorphism $X \overset{f}{\to} Y$ is regular if and only if $Y$ is topologised as a quotient of $X$ .

Note that if $f$ is both regular monic and regular epic, then it’s an isomorphism since the pair $(g, h)$ of which its equaliser must satisfy $g = h$ .

Warning. The following terminology is not standard. These are usually (both!) referred to as “generating”, but to avoid confusion, in this course we will refer to them with separate names.

Definition 2.7 (Separating / generating family). Let $G$ be a family of objects of a locally small category $C$ .

(a)
We say $G$ is a separating family if the functors $C (G, ∙)$ , $G \in G$ are jointly faithful, i.e. given a parallel pair $A ⇉_{g}^{f} B$ , the equations $f h = g h$ for all $h : G \to A$ with $G \in G$ imply $f = g$ .
(b)
We say $G$ is a detecting family if the $G (G, ∙)$ jointly reflect isomorphisms, i.e. given $A \overset{f}{\to} B$ , if every $G \overset{g}{\to} B$ with $G \in G$ factors uniquely through $f$ , then $f$ is an isomorphism.

If $G = {G}$ , we call $G$ a separator or a detector.

Lemma 2.8.

(i)
If $C$ has equalisers (i.e. every pair of parallel arrows has an equaliser), then any detecting family in $C$ is separating.
(ii)
If $C$ is balanced, then any separating family in $C$ is detecting.

Proof.

(i) Suppose $G$ is a detecting family, and suppose $A ⇉_{g}^{f} B$ satisfy the hypothesis of Definition 2.7(a). Let $E \overset{e}{\to} A$ of $(f, g)$ : then any $G \overset{h}{\to} A$ with $G \in G$ factors uniquely through $e$ , so $e$ is an isomorphism, so $f = g$ .
(ii) Suppose $G$ is separating, and $A \overset{f}{\to} B$ satisfies the hypothesis of Definition 2.7(b). If $C ⇉_{h}^{g} A$ satisfy $f g = f h$ , then any $G \overset{k}{\to} C$ with $G \in G$ satisfies $g k = h k$ , since both are factorisations of $f g k$ through $f$ . So $g = h$ ; hence $f$ is monic.
Similarly, if $B ⇉_{m}^{l} D$ satisfy $l f = m f$ , then any $G \overset{n}{\to} B$ satisfies $l n = m n$ , since it factors through $f$ , so $l = m$ and hence $f$ is epic. Since $C$ is balanced, $f$ is an isomorphism. □

Example 2.9.

(a) In $S e t$ , $1 = {*}$ is a separator and a detector, since $S e t (1, ∙)$ is isomorphic to the identity functor. Also, $2 = {0, 1}$ is a coseparator and a codetector, since it represents $P^{*} : {S e t}^{o p} \to S e t$ .
(b) In $G p$ (respectively $R n g$ ), $ℤ$ (respectively $ℤ [X]$ ) is a separator and a detector, since it represents the forgetful functor.
But $G p$ has no coseparator or codetector set: given any set $G$ of groups, there is a simple group $H$ with $card H > card G$ for all $G \in G$ , so the only homomorphisms $H \to G$ with $G \in G$ are trivial.
(c) For any small category $C$ , the set ${C (A, ∙) | A \in ob C}$ is separating and detecting in $[C, S e t]$ . This uses Yoneda and Lemma 1.8 (for the detecting case).
(d) In $T o p$ , $1$ is a separator since it represents $U : T o p \to S e t$ . But $T o p$ has no detecting set of objects: given a set $G$ of spaces, choose $κ > card X$ for all $X \in G$ , and let $Y$ and $Z$ be a set of $card κ$ . Give $Y$ the discrete topology and for $Z$ , we set the closed sets be $Z$ plus all the subsets of $card κ$ . The identity $Y \to Z$ is continuous, but not a homeomorphism, but its restriction to any subset of $card < κ$ is a homeomorphism, so $G$ can’t detect the fact that $f$ isn’t an isomorphism.
(e) Let $G$ be the category whose objects are the ordinals, with identities plus two morphisms $α ⇉_{g}^{f} β$ whenever $α < β$ with composition defined by $f f = f g = g f = g g = f$ .
Then $0$ is a detector for $C$ : it can tell that $0 ⇉_{g}^{f} α$ aren’t isomorphisms since neither factors through the other, and if $0 < α < β$ it can tell that $α ⇉_{g}^{f} β$ aren’t isomorphisms since $0 \overset{g}{\to} β$ doesn’t factor through either.

But $C$ has no separating set: if $G$ is any set of ordinals, choose $α > β$ for all $β \in G$ and then $G$ can’t separate $α ⇉_{g}^{f} α + 1$ .

By definition, the functors $C (A, ∙) : C \to S e t$ preserve monomorphisms, but they don’t always preserve epimorphisms.

Definition 2.10 (Projective). We say an object $P$ in a locally small category $C$ is projective if $C (P, ∙)$ preserves epimorphisms, i.e. if given

there exists

h : P \to Q

with

g h = f

. Dually,

P

is injective if it’s projective in

C^{o p}

If $P$ satisfies this condition for all $g$ in some class $E$ of epimorphisms, we call it $E$ -projective.

In $[C, S e t]$ , we consider the class of pointwise epimorphisms, i.e. those $α$ such that $α_{A}$ is surjective for all $A$ .

Corollary 2.11. functors of the form $C (A, ∙)$ are pointwise projective in $[C, S e t]$ .

Proof. Immediate from Yoneda; given

with

β

pointwise epic,

Φ (α) \in R A

β_{A} (y)

for some

y \in Q A

, so

β Ψ (y) = α

. □

“ $[C, S e t]$ has enough pointwise projectives”:

Proposition 2.12. Assuming that:

$C$ is small
$F : C \to S e t$

Then there exists a pointwise epimorphism

P ↠ F

where

P

is pointwise projective.

Proof. Set $P = ∐_{(A, x)} C (A, ∙)$ where the disjoint union is over all pairs $(A, x)$ with $A \in ob C$ and $x \in F A$ . A morphism $P \to Q$ is uniquely determined by a family of morphisms $C (A, ∙) \to Q$ . . Hence $P$ is pointwise projective, since all the $C (A, ∙)$ are. But we have $α : P \to F$ whose $(A, x)$ -th component is $Ψ (x) : C (A, ∙) \to F$ and this is pointwise epic since any $x \in F A$ appears as $Ψ (x) (1_{A})$ . □

3 Adjunctions

Definition 3.1 (Adjunction, D. Kan 1958). Let $C$ and $D$ be categories. An adjunction between $C$ and $D$ consists of functors $F : C \to D$ and $G : D \to C$ together with, for each $A \in ob C$ and $B \in ob D$ , a bijection between morphisms $F A \to B$ in $D$ and morphisms $A \to G B$ in $C$ , which is natural in $A$ and $B$ . (If $C$ and $D$ are locally small, this means that $D (F ∙, ∙)$ and $C (∙, G ∙)$ are naturally isomorphic functors $C^{o p} \times D \to S e t$ .)

We say $F$ is left adjoint to $G$ , or $G$ is right adjoint to $F$ , and we write $(F ⊣ G)$ .

Example 3.2.

(a) The free functor $F : S e t \to G p$ is left adjoint to the forgetful functor $G p \overset{U}{\to} S e t$ . By definition, homomorphisms $F A \to G$ correspond to functions $A \to U G$ ; naturality in $A$ was built into the definition of $F$ in Example 1.5(b) and naturality in $G$ is immediate.
(b) The forgetful functor $U : T o p \to S e t$ has a left adjoint $D$ , which equips a set $A$ with its discrete topology since any function $A \to U X$ is continuous as a map $D A \to X$ . $U$ also has a right adjoint $I$ given by the ‘ìndiscrete’ topology.
(c) The functor $ob : C a t \to S e t$ has a left adjoint $D$ given by discrete categories, and a right adjoint $I$ : $I A$ is the category with objects $A$ and morphisms $a \to b$ for each $(a, b)$ . $D$ also has a left adjoint $π_{0}$ : $π_{0} C$ is the set of connected components of $C$ , i.e. the quotient of $ob C$ by the smallest equivalence relation which identifies $dom f$ with $cod f$ for all $f \in mor C$ .
(d) Given a set $A$ , we can regard $(∙) \times A$ as a functor $S e t \to S e t$ . It has a right adjoint, namely $S e t (A, ∙)$ . Given $f : B \times A \to C$ we can regard it as a function $λ f : B \to S e t (A, C)$ by $λ f (b) (a) = f (b, a)$ .
We call a category $C$ cartesian closed if it has binary products as defined in Example 2.6(f) and each $(∙) \times A$ has a right adjoint ${(∙)}^{A}$ . For example, $C a t$ is cartesian clsosed, with $D^{C}$ taken to be the $[C, D]$ .
(e) Let $M = {1, e}$ be the $2$ -element monoid with $e^{2} = e$ (and identity $1$ ). We have a functor $F : S e t \to [M, S e t]$ sending $A$ to $(A, 1_{A})$ and a functor $G : [M, S e t] \to S e t$ sending $(A, e)$ to ${a \in A | e a = a}$ .
We have $(F ⊣ G ⊣ F)$ : $(F ⊣ G)$ since any $f : M \to (B, e)$ takes values in $G (B, e)$ and any $g : (B, e) \to F A$ is determined by its restriction to $G (B, e)$ since $g (b) = g (e, b)$ . However, note that this is not an equivalence of categories.
(f) Let $1$ be the category with one object and one morphism (which must the identity on the only object). A left adjoint for the unique functor $C \to 1$ picks out an initial object of $C$ , i.e. an object such that there is a unique $I \to A$ for each $A \in ob C$ . Dually, a right adjoint for $C \to 1$ ‘is’ a terminal object of $C$ (a terminal object is an initial object in $C^{o p}$ ).
Again, the example of $G p$ shows that these two can coincide.
(g) Suppose given $A \overset{f}{\to} B$ in $S e t$ . We have order-preserving mappings $P f : P A \to P B$ and $P^{*} f : P B \to P A$ , and $(P f ⊣ P^{*} f$ since $A^{'} \subseteq f^{- 1} B^{'} ⟺ f (A^{'}) \subseteq B^{'}$ .
(h) Suppose given a relation $R \subseteq A \times B$ . We define ${(∙)}^{r} : P A \to P B$ and ${(∙)}^{l} : P B \to P A$ by $\begin{array}{l} {(S)}^{r} & = {b \in B | (\forall a \in S) ((a, b) \in R)} \\ {(T)}^{l} & = {a \in A | (\forall b \in T) ((a, b) \in R)} \end{array}$
These are contravariant functors and $S \subseteq T^{l} ⟺ S \times T \subseteq R ⟺ T \subseteq S^{r}$ . We say ${(∙)}^{r}$ and ${(∙)}^{l}$ are adjoint on the right.
(i) $P^{*} : {S e t}^{o p} \to S e t$ is self-adjoint on the right, since functions $A \to P B$ and functions $B \to P A$ both correspond to relations $R \subseteq A \times B$ .
(j) ${(∙)}^{*} : {V e c t}_{k}^{*} \to {V e c t}_{k}$ is self-adjoint on the right, since linear maps $V \to W^{*}$ and $W \to V^{*}$ both correspond to bilinear maps $V \times W \to k$ .

Theorem 3.3. Assuming that:

$G : D \to C$ is a functor
for $A \in ob C$ , let $(A ↓ G)$ be the category whose objects are pairs $(B, f)$ where $B \in ob D$ and $f : A \to G B$ , and whose morphisms $(B, f) \to (B^{'}, f^{'})$ are morphisms $g : B \to B^{'}$ making
commute.

Then specifying a left adjoint for

G

is equivalent to specifying an initial object of

(A ↓ G)

for each

A

Proof. First suppose $(F ⊣ G)$ . For each $A \in ob C$ , let $η_{A} : A \to G F A$ be the morphism corresponding to $1_{F A} : F A \to F A$ . Then $(F A, η_{A})$ is an initial object of $(A ↓ G)$ : given any $f : A \to G B$ , the diagram

commutes if and only if

g

corresponds to

f

under the adjunction, by naturality of the adjunction bijection.

So there’s a unique morphism $(F A, η_{A}) \to (B, f)$ in $(A ↓ G)$ .

Conversely, suppose given in initial object $(F A, η_{A})$ in $(A ↓ G)$ for each $A$ . We make $F$ into a function $C \to D$ : given $A \overset{f}{\to} B$ , $F f$ is the unique morphism $(F A, η_{A}) \to (F B, η_{B} f)$ in $(A ↓ G)$ . Functoriality comes from uniqueness: given $B \overset{g}{\to} C$ , $(F g) (F f)$ and $F (g f)$ are both morphisms $(F A, η_{A}) \to (F C, η_{C} g f)$ in $(A ↓ G)$ . The adjunction bijection sends $A \overset{f}{\to} G B$ to the unique morphism $(F A, η_{A}) \to (B, f)$ in $(A ↓ G)$ , with inverse sending $F A \overset{g}{\to} B$ to $(G g) η_{A} : A \to G B$ . This is natural in $A$ since $η$ is a natural transformation $1_{C} \to G F$ and natural in $B$ since $G$ is functorial. □

Corollary 3.4. Assuming that:

$F$ and $F^{'}$ are both left adjoint to $G : D \to C$

Then there is a canonical natural isomorphism

α : F \to F^{'}

Proof. $(F A, η_{A})$ and $(F^{'} A, η_{A}^{'})$ are both initial in $(A ↓ G)$ , so there’s a unique isomorphism $α_{A}$ between them. $α$ is natural: given $A \overset{f}{\to} B$ , $(F^{'} f) α_{A}$ and $α_{B} (F f)$ are both morphisms $(F A, η_{A}) \to (F^{'} B, η_{B}^{'} f)$ in $(A ↓ G)$ , so they’re equal. □

As a result of this, we will often talk about “the” left adjoint of a functor (when it exists), because we don’t usually care about which one in the isomorphism class we use.

Lemma 3.5. Assuming that:

$C ⇄_{G}^{F} D ⇄_{K}^{H} E$
$(F ⊣ G)$ and $(H ⊣ K)$

Then

(H F ⊣ G K)

Proof. Given $A \in ob C$ , $C \in ob E$ , we have bijections between morphisms $H F A \to C$ , morphisms $F A \to K C$ , and morphisms $A \to G K C$ which are both natural in $A$ and $C$ , $D$ . □

Corollary 3.6. Assuming that:

the diagram
is a commutative square of categories and functors
all the functors have left adjoints

Then the square of left adjoints commutes up to natural isomorphism.

Proof. By Lemma 3.5, both ways round are left adjoint to $H F = K G$ , so by Corollary 3.4 they’re isomorphic. □

We saw in Theorem 3.3 that an adjoint $(F ⊣ G)$ gives rise to a natural transformation $η : 1_{C} \to G F$ , called the unit of the adjunction. Dually, we have $𝜀 : F G \to 1_{D}$ , the counit of $(F ⊣ G)$ .

Theorem 3.7. Assuming that:

$F : C \to D$ and $G : D \to C$ are functors

Then specifying an adjunction

(F ⊣ G)

is equivalent to specifying a natural transformation

η : 1_{C} \to G F

and

𝜀 : F G \to 1_{D}

satisfying the two commutative diagrams:

Proof. Suppose $(F ⊣ G)$ . We defined $η$ in the proof of Theorem 3.3, and $𝜀$ is defined dually. Since $𝜀_{F A}$ corresponds to $1_{G F A}$ , the composite $𝜀_{F A} (F η_{A})$ corresponds to $1_{G F A} η_{A} = η_{A}$ . But by definition $1_{F A}$ corresponds to $η_{A}$ . The other identity is dual.

Conversely, suppose given $η$ and $𝜀$ satisfying the triangular identities. Given $F A \overset{f}{\to} B$ , we define $Φ (f) = (G f) η_{A} : A \to G F A \to G B$ . Dually, given $A \overset{g}{\to} G B$ , we define $Ψ (g) = 𝜀_{B} (F g)$ . Then $Ψ Φ (f) = Ψ ((G f) η_{A}) = 𝜀_{B} (F G f) F η_{A} = f (𝜀_{F A}) (F η_{A}) = f$ , and dually $Φ Ψ (g) = g$ . Naturality of $Φ$ and $Ψ$ follows from naturality of $η$ and $𝜀$ . □

In Definition 1.9, we had natural isomorphisms $α : 1_{C} \to G F$ and $β : F G \to 1_{D}$ . These look like the unit and counit of an adjunction $(F ⊣ G)$ : do they satisfy the triangular identities? No, but we can always change them:

Proposition 3.8. Assuming that:

$F : C \to D$ , $G : D \to C$ , $α : 1_{C} \to G F$ and $β : F G \to 1_{D}$ be an equivalence of categories as defined in Definition 1.9

Then there exist isomorphisms

α^{'} : 1_{C} \to G F

and

β^{'} : F G \to 1_{D}

satisfying the triangular identities. In particular,

(F ⊣ G ⊣ F)

Proof. We define $α^{'} = α$ and take $β^{'}$ to be the composite

F G \overset{{(F G β)}^{- 1}}{\to} F G F G \overset{{(F α_{G})}^{- 1}}{\to} F G \overset{β}{\to} 1_{D} .

Note that $F G β = β_{F G}$ , since

commutes by naturality of

β

, and

β

is monic. Similarly,

G F α = α_{G F}

To verify the triangular identities, consider

F FGF FGF GF

F FGF

F1(F((1βαFβF−αFβFFFG1α)FG−)F1−)−11=(FGFα)−1 F

which commutes by naturality of

β^{- 1}

For the second triangular identity, we have

G GF G GF GF G

G GF G

α1(α((1GGGG−GGGβF1FβGα)−βG1))−−11= (αGFG)−1 G β
G

Hence by Theorem 3.7 we have

(F ⊣ G)

. But

{(β^{'})}^{- 1}

and

α^{- 1}

also satisfy the triangular identities for and adjunction

(G ⊣ F)

. □

Lemma 3.9. Assuming that:

$(F : C \to D ⊣ G : D \to C)$ an adjunction with counit $𝜀$

Then

(i) $G$ is faithful if and only if $𝜀$ is pointwise epic
(ii) $G$ is full and faithful if and only if $𝜀$ is an isomorphism

Proof.

(1) Given $g : B \to C$ in $D$ , $g 𝜀_{B}$ corresponds to $G g$ under the adjunction. So $𝜀_{B}$ epic if and only if $G$ acts injectively on morphisms with domain $B$ and specified codomain. Hence $𝜀_{B}$ epic for all $B$ if and only if $G$ is faithful.
(2) Similarly, $G$ full and faithful if and only if for all $B$ and $C$ composition with $𝜀_{B}$ is a bijection $D (B, C) \to D (F G B, C)$ . This happens if and only if $𝜀_{b} : F G B \to B$ is an isomorphism for all $B$ . □

Definition 3.10 (Reflection). By a reflection, we mean an adjunction such that the right adjoint is full and faithful (equivalently: the counit is an isomorphism). We say $D \subseteq C$ is a reflective subcategory if it’s full and the inclusion $D \to C$ has a left adjoint.

Example 3.11.

(a) $A b G p$ is reflective in $G p$ : the left adjoint to the inclusion sends $G$ to $G ∕ G^{'}$ where $G^{'}$ is the subgroup generated by commutators. Any homomorphism $G \to A$ with $A$ abelian factors uniquely through the quotient map $G \to G ∕ G^{'}$ .
(b) Recall that a group $G$ is torsion if all elements have finite order, and torsion free if its only element of finite order is $1$ . In an abelian group $A$ , the torsion leements form a subgroup $A_{t}$ , and $A \mapsto A_{t}$ is right adjoint to the inclusion $t A b G p \to A b G p$ , since any homomorphism $B \to A$ whose $B$ is torsion takes values in $A_{t}$ . Similarly, $A \mapsto A ∕ A_{t}$ defines a left adjoint to the inclusion $t f A b G p \to A b G p$ .
(c) Let $K H a u s \subseteq T o p$ be the full subcategory of compact Hausdorff spaces. $K H a u s$ is reflective in $T o p$ : the left adjoint is the Stone-Čech compactification $β$ .
(d) Let $S e q \subseteq T o p$ be the full subcategory of sequential spaces, i.e. those in which all sequentially closed sets are closed. The inclusion $S e q \to T o p$ has a right adjoint sending $X$ to $X_{s}$ , the same set as $X$ with all sequentially closed sets declared to be closed. The identity mapping $X_{s} \to X$ is (continuous, and) the counit of the adjunction.
(e) The category $P r e o r d$ of preordered sets is reflective in $C a t$ : the reflection sends $C$ to $C ∕ ≃$ where $≃$ is the congruence identifying all paralell pairs in $C$ .
(f) Given a topological space $X$ , the poset $Ω (X)$ of open subsets of $X$ is coreflective in $P (X)$ , since if $U$ is open and $A \subseteq X$ is arbitrary, we have $U \subseteq A$ if and only if $U \subseteq A^{\circ}$ (recall $^{\circ}$ denotes interior). Dually, the poset of closed subsets is reflective in $P (X)$ .

4 Limits

Definition 4.1 (Diagram). Let $J$ be a category (almost always small, and often finite). By a diagram of shape $J$ in a category $C$ , we mean a functor $D : J \to C$ . The objects $D (j)$ , $j \in ob J$ are called vertices of $D$ , and morphisms $D (α)$ , $α \in mor J$ are called edges of $D$ .

For example, if $J$ is the category

a diagram of shape

J

is a commutative square in

C

If $J$ is instead

then a diagram of shape

J

is a not-necessarily-commutative square.

Definition 4.2 (Cone, limit). Let $D : J \to C$ be a diagram. A cone over $D$ consists of an object $A$ (its apex) together with morphisms $λ_{j} : A \to D (j)$ for each $j \in ob J$ (the legs of the cone) such that

commutes for each

α : j \to j^{'}

J

A morphism of cones $(A, (λ_{j} | j \in ob J)) \to (B, (μ_{j} | j \in ob J))$ is a morphism $f : A \to B$ such that $μ_{j} f = λ_{j}$ for all $j$ . We have a category $C o n e (D)$ of cones over $D$ ; a limit for $D$ is a terminal object of $C o n e (D)$ .

Dually, a colimit for $D$ is an initial cone under $D$ .

If $Δ : C \to [J, C]$ is the functor sending $A$ to the constant diagram with all vertices $A$ then a cone over $D$ is a natural transformation $Δ A \to D$ .

Also, $C o n e (D)$ is another name for $(Δ ↓ D)$ , defined as in Theorem 3.3 $^{o p}$ .

So by Theorem 3.3, $C$ has limits for all diagrams of shape $J$ if and only if $Δ$ has a right adjoint.

Example 4.3.

(a) Suppose $J = \emptyset$ . If $D : \emptyset \to C$ , then $C o n e (D) ≅ C$ , so a limit for $D$ is a terminal object.
(b) If $J = ∙ ∙$ , a diagram of shape $J$ is a pair $A, B$ , and a cone over it is a span
A limit for it is a categorical coproduct
Dually, a colimit for it is a coproduct
(c) If $J$ is a (small) discrete category, a (co)limit for $(A_{j} | j \in J)$ is a (co)product $\prod_{j \in J} A_{j}$ ( $\sum_{j \in J} A_{j}$ ).
(d) If $J$ is $∙ ⇉_{}^{} ∙$ , then a diagram of shape $J$ is a parallel pair $A ⇉_{g}^{f} B$ . A cone over it consists of
satisfying $f h = k = g h$ , or equivalently of $C \overset{h}{\to} A$ satisfying $f h = g h$ . So a limit for $A ⇉_{g}^{f} B$ is an equaliser for $(f, g)$ , as defined in Example 2.6(g).
(e) If $J$ is
then a diagram of shape $J$ is a cospan
A cone over it has $3$ legs, but if we omit the (redundant) middle one, it’s a span
completing the cospan to a commutative square.
A limit for
is called a pullback for $(f, g)$ . If $C$ has binary products and equalisers, we can construct pullbacks by forming the equaliser $A \times B ⇉_{g π_{2}}^{f π_{1}} C$ . Dually, colimits of shape $J^{o p}$ are called pushouts.
(f) If $M = {1, e}$ is the $2$ -element with $e^{2} = e$ , a diagram of shape $M$ is an object $A$ equipped with an idempotent $A \overset{e}{\to} A$ . A limit (respectively colimit) for $(A, e)$ is the monic (respectively epic) part of a splitting of $e$ .
Note that the functor $S e t \overset{F}{\to} [M, S e t]$ in Example 3.2(e) is $Δ$ , so this explains the coincidence of left and right adjoints.

(g) Suppose

J = ℕ

is the ordered set of natural numbers. A diagram of shape

ℕ

is a direct sequence

A_{0} \to A_{1} \to A_{2} \to A_{3} \to \dots,

and a colimit for it is called a direct limit $A_{\infty}$ .

Dually, we have inverse sequences

\dots \to A_{2} \to A_{1} \to A_{0},

and their limits are called inverse limits.

For example in topology, an infinite dimensional CW-complex $X$ is the direct limit of its $n$ -skeletons $X_{n}$ . In algebra, the ring of $p$ -adic integers is the limit of the inverse sequence

\dots \to ℤ ∕ p^{3} ℤ \to ℤ ∕ p^{2} ℤ \to ℤ ∕ p ℤ \to {0}

in $R n g$ .

Proposition 4.4. Assuming that:

$C$ a category

Then

(i) If $C$ has equalisers and all small products (including empty product), then $C$ has all small limits.
(ii) If $C$ has equalisers and all finite products (including empty product), then $C$ has all finite limits.
(iii) If $C$ has pullbacks and a terminal object, then $C$ has all finite limits.

Proof.

(i) & (ii) Let $D : J \to C$ be a diagram. Form the products $\begin{array}{l} P & = \prod_{j \in ob J} D (j) \\ Q & = \prod_{α \in mor J} D (cod α) \end{array}$
We have morphisms $P ⇉_{g}^{f} Q$ defined by $π_{α} f = π_{cod α}$ and $π_{α} g = D (α) π_{dom α}$ for all $α$ . Let $e \overset{e}{\to} P$ be an equaliser for $(f, g)$ . The morphisms $λ_{j} = π_{j} e : E \to P \to D (j)$ form a cone over $D$ , since for any $α : j \to j^{'}$ we have
$D (α) λ_{j} = D (α) π_{j} e = π_{α} g e = π_{α} f e = π_{j^{'}} e = λ j^{'} .$

It is a limit: given any cone $(A, (μ_{j} | j \in ob J))$ over $D$ , the $μ_{j}$ form a cone over the discrete diagram with vertices $D (j)$ , so they induce a unique $μ : A \to P$ . Then $f μ = g μ$ since the $μ_{j}$ s form a cone over $D$ , so $μ$ factors uniquely as $e ν$ , and $ν$ is the unique factorisation of $(μ_{j} | j \in ob J)$ through $(λ_{j} | j \in ob J)$ .
(iii) If $1$ is a terminal object of $C$ , then we can construct $A \times B$ as the pullback of
Then we can construct $\prod_{i = 1}^{n} A_{i}$ as $A_{1} \times (A_{2} \times (\dots \times A_{n}) \dots))$ .
To form an equaliser of $A ⇉_{g}^{f} B$ , consider the pullback of
Any cone
over this has $h = k = π_{1} (1_{A}, g) k = π_{1} (1_{A}, f) h$ . So a limit cone has the universal property of an equaliser for $(f, g)$ . □

Definition 4.5 (Limit preserving / reflecting / creating). Let $F : C \to D$ be a functor.

(a)
We say $F$ preserves limits of shape $J$ if, given $D : J \to C$ and a limit cone $(L, (λ_{j} | j \in ob J))$ for it, $(F L, (F λ_{j} | j \in ob J))$ is a limit for $F D : J \to D$ .
(b)
We say $F$ reflects limits of shape $J$ if given $D : J \to C$ , any cone over $D$ which maps to a limit cone in $D$ is a limit in $C$ .
(c)
We say $F$ creates limits of shape $J$ if, given $D : J \to C$ and a limit cone $(L, (λ_{j} | j \in ob J))$ over $F D$ , there exists a cone over $D$ whose image under $F$ is $≅ (L, (λ_{j}))$ , and any such cone is a limit in $C$ .

We say a category $C$ is complete if it has all small limits.

Corollary 4.6. In each of the statements of Proposition 4.4, we may replace ‘ $C$ has’ by either ‘ $D$ has and $G : D \to C$ preserves’ or ‘ $C$ has and $D \to C$ creates’.

Proof. Exercise. □

Example 4.7.

(a) The functor $G p \to S e t$ creates all small limits: given a family of groups ${G_{i} | i \in I}$ , there’s a unique structure on $\prod_{i \in I} G_{i}$ making the projections into homomorphisms, and it’s a product in $G p$ . Similarly for equalisers. But $G p \to S e t$ doesn’t preserve or reflect coproducts.
(b) The forgetful functor $T o p \to S e t$ preserves small limits and colimits, but doesn’t reflect them.
(c) The inclusion $A b G p \to G p$ reflects coproducts, but doesn’t preserve them.
A coproduct $A * B$ in $G p$ is nonabelian if both $A$ and $B$ are nontrivial. So the only cones in $A b G p$ thot could map to coproduct cones in $G p$ are those where either $A$ or $B$ is trivial. But if $A = {1}$ then $A \times B ≅ B$ in either category.
(d) If $D$ is a reflective subcategory of $C$ , the inclusion $D \to C$ creates any limits which exist.
Given $D : J \to D$ and a limit cone $(L, (x_{j} | j \in ob J))$ for it in $C$ , the morphisms $F L \overset{F x_{j}}{\to} F D (j) \overset{η_{D (j)}^{- 1}}{\to} D (j)$ (where $F$ is the left adjoint, and $η$ is the unit) form a cone over $D$ , so they induce a unique $u : F L \to L$ . Now $u η_{L} : L \to L$ is $1_{L}$ since it’s a factorisation of the limit through itself. So $η_{L} u η_{L} = η_{L}$ , i.e. $η_{L} u$ is a factorisation of $η_{L}$ through itself, so $η_{L} u = 1_{F L}$ . So the $η_{D (j)}^{- 1} (F λ_{j})$ form a limit cone in $C$ , and hence in $D$ .
(e) If $D$ has limits of shape $J$ , so does $[C, D]$ for any $C$ , and the forgetful functor $[C, D] \to D^{ob C}$ creates them (strictly).
Given $D : J \to [C, D]$ , we can regard it as a functor $J \times C \to D$ . For each $A \in ob C$ , $D (∙, A)$ is a diagram of shape $J$ in $D$ , so has a limit $(L A, (λ_{j, A} : L A \to D (j, A) | j \in ob J))$ . Given $f : A \to B$ in $C$ , the composites $L A \overset{λ_{j, A}}{\to} D (j, A) \overset{D (j, f)}{\to} D (j, B)$ form a cone over $D (∙, B)$ , so induce a unique $L f : L A \to L B$ . Functoriality of $L$ follows fro uniqueness, and this is the unique way of making $L$ into a functor which lifts the $λ_{j, ∙}$ to a cone in $[C, D]$ .

The fact that it’s a limit cone is straightforward.

Remark 4.8. In any category, $A \overset{f}{\to} B$ is monic if and only if

is a pullback. Hence, if

D

has pullbacks, then any monomorphism in

[C, D]

is pointwise monic, since its pullback along itself is contsructed pointwise.

Lemma 4.9. Assuming that:

$G : D \to C$ has a left adjoint

Then

G

preserves all limits which exist in

D

Proof 1. Suppose $(F ⊣ G)$ , and suppose $C$ and $D$ have limits of shape $J$ . Then the diagram

commutes, and all the functors in it have right adjoints, so

commutes up to isomorphism by Corollary 3.6. □

Proof 2. Suppose given $D : J \to D$ and a limit cone $(L, (λ_{j} | j \in ob J))$ over it. Give a cone $(A, (μ_{j} : A \to G D (j)))$ over $G D$ , the transposes $\bar{μ_{j}} : F A \to D (j)$ form a cone over $D$ by naturality of the adjunction, so induce a unique $\bar{μ} : F A \to L$ such that $λ_{j} \bar{μ} = \bar{μ_{j}}$ for all $j$ .

Then $μ : A \to G L$ is the unique morphism satisfying $(G λ_{j}) μ = μ_{j}$ for all $j$ . □

Lemma 4.10. Assuming that:

$J$ a diagram shape
$D$ has all limits of shape $J$
$G : D \to C$ preserves all limits of shape $J$

Then for each

A \in ob C

(A ↓ G)

has limits of shape

J

and the forgetful functor

(A ↓ G) \overset{U}{\to} D

creates them.

Proof. Suppose given $D : J \to (A ↓ G)$ ; write $D (j) = (U D (j), f_{j} : A \to G U D (j))$ and let $(L, (λ_{j} | j \in ob J))$ be a limit for $U D$ . Since the edges of $D$ are morphisms in $(A ↓ G)$ , the $f_{j}$ form a cone over $G U D$ , so there’s a unique $f : A \to G L$ satisfying $(G λ_{j}) f = f_{j}$ for all $j$ .

So $(L, f)$ is the unique lifting of $L$ to an object of $(A ↓ G)$ which makes the $λ_{j}$ into morphisms $(L, f) \to (U D (j), f_{j})$ in $(A ↓ G)$ . The fact that these morphisms form a limit cone is straightforward. □

Can we represent an initial object as a limit?

Lemma 4.11. Assuming that:

$C$ a category

Then specifying an initial object of

C

is equivalent to specifying a limit for

1_{C} : C \to C

Proof. First suppose $I$ is initial. The unique morphisms $I \to A$ , $A \in ob C$ , form a cone over $1_{C}$ , and it’s a limit cone since if $(A, (f_{B} : A \to B | B \in ob C))$ is any cone over $1_{C}$ , then $f_{I}$ is its unique factorisation through the one with apex $I$ .

Conversely, suppose given a limit $(I, (f_{A} : I \to A | A \in ob C))$ for $1_{C}$ . Then $I$ is weakly initial (i.e. it admits morphisms to every object of $C$ ); and if $g : I \to A$ then $g f_{I} = f_{A}$ . In particular, $f_{A} f_{I} = f_{A}$ for all $A$ , so $f_{I}$ is a factorisation of the limit cone through itself, so $f_{I} = 1_{I}$ and $I$ is initial. □

The ‘primitive’ Adjoint Functor Theorem follows from Lemma 4.10, Lemma 4.11 and Theorem 3.3. But it only applies to preorders (see Example Sheet).

Theorem 4.12 (General Adjoint Functor Theorem). Assuming that:

$D$ is complete and locally small

Then

G : D \to C

has a left adjoint if and only if

G

preserves small limits and satisfies the solution-set condition: for every

A \in ob C

, there’s a set

{(B_{i}, f_{i}) | i \in I}

of objects of

(A ↓ G)

which is collectively weakly initial.

Proof.

$\Rightarrow$ $G$ preserves limits by Lemma 4.9, and ${(F A, η_{A})}$ is a singleton solution-set for each $A$ .
$\Leftarrow$ By Lemma 4.10, the categories $(A ↓ G)$ are complete, and they’re locally small since $D$ is.
So we need to show: if $A$ is complete and locally small, and has a weakly initial set ${A_{i} | i \in I}$ , then it has an initial object. First form $P = \prod_{i \in I} A_{i}$ ; then $P$ is weakly initial. Now form the limit of the diagram with vertices $P$ and $P^{'}$ , with the morphisms $P \to P^{'}$ being all endomorphisms of $P$ .

Writing $I \overset{i}{\to} P$ for this, $I$ is still weakly initial. Suppose given $I ⇉_{g}^{f} B$ ; let $E \overset{e}{\to} I$ be their equaliser. There exists some $h : P \to E$ . Now $i e h : P \to P$ , but we also have $1_{P} : P \to P$ , so $i = 1_{P} i = i e h i$ . But $i$ is monic, so we get $e h i = 1_{I}$ , so $e$ is split epic, and hence $f = g$ . □

Example 4.13.

(a) Consider the forgetful functor $U : G p \to S e t$ . $G p$ has and $U$ preserves all small limits by Example 4.7(a), and $G p$ is locally small. Given $A$ , any $A \overset{f}{\to} U G$ factors through $A \to U G^{'}$ where $G^{'}$ is the subgroup generated by ${f (a) | a \in A}$ . Also $card G^{'} \leq \max {ℵ_{0}, card A}$ . Let $B$ be a set of this cardinality: considering all subsets $B^{'} \subseteq B$ , all group structures on $B^{'}$ and all functions $A \to B^{'}$ , we get a solution-set at $A$ .
(b) Let $C L a t$ be the category of complete lattices (posets with all joins and all meets). $U : C L a t \to S e t$ creates limits just like $U : G p \to S e t$ .
In 1965, A. Hales showed that there exist arbitrarily large complete lattices generated by 3 element subsets, so the solution-set condition fails for $A = {a, b, c}$ .

Now also that $C L a t$ doesn’t have a coproduct for 3 copies of ${0, a, 1}$ .

Definition 4.14 (Subobject). By a subobject of $A \in ob C$ , we mean a monomorphism $A^{'} ↣ A$ . We order subobjects by $(A^{'} ↣ A) \leq (A^{″} ↣ A)$ if there exists

We write

{Sub}_{C} (A)

for this preorder.

We say $C$ is well-powered if every ${Sub}_{C} (A)$ is equivalent to a small poset.

For example, $S e t$ is well-powered since the inclusions $A^{'} \subseteq A$ form a representative set of subobjects of $A$ . It is well-copowered since isomorphism classes of epimorphisms $A ↠ B$ correspond to equivalence relations on $A$ .

Lemma 4.15. Assuming that:

a pullback diagram
where $f$ is monic

Then

k

is monic.

Proof. Suppose given $D ⇉_{m}^{l} P$ with $k l = k m$ . Then $f h l = g k l = g k m = f h m$ , but $f$ is monic so $h l = h m$ . So $l$ and $m$ are both factorisations of

through the pullback, and hence

l = m

. □

Theorem 4.16 (Special Adjoint Functor Theorem). Assuming that:

$C$ and $D$ are locally small
$D$ is complete and well-powered
$D$ has a coseparating set of objects

Then

G : D \to C

has a left adjoint if and only if it preserves all small limits.

Proof.

$\Rightarrow$ is Lemma 4.9.
$\Leftarrow$ Let $A \in ob C$ . As in Theorem 4.12, $(A ↓ G)$ inherits completeness and locally smallness from $D$ : it also inherits well-poweredness since subobjects of $(B, f)$ in $(A ↓ G)$ are those $B^{'} \overset{m}{↣} B$ in $D$ such that $f$ factors through $G B^{'} \overset{G m}{↣} G B$ . (Note that the forgetful functor $(A ↓ G) \to D$ preserves monomorphisms by Remark 4.8). And if ${S_{i} | i \in I}$ is a coseparating set for $D$ , then ${(S_{i}, f) | i \in I, f \in C (A, G S_{i})}$ is a coseparating set for $(A ↓ G)$ .
So we need to show: if $A$ is complete, locally small and well-powered and has a coseparating set ${S_{i} | i \in I}$ , then $A$ has an initial object. First form $P = \prod_{i \in I} S_{i}$ ; now consider the limit of the diagram
whose edges are a representative set of subobjects of $P$ .

If $I$ is the apex of the limit cone, the legs $I \to P^{'}$ of the limit cone are all monic by the argument of Lemma 4.15, and in particular $I \to P$ is monic, and it’s a least subobject of $P$ .

If we had $I ⇉_{g}^{f} A$ , their equaliser $E \to I$ would be a subobject of $P$ contained in $I ↣ P$ , so $E \to I$ is an isomorphism, and hence $f = g$ .

Given any $A \in ob A$ form the product $Q = \prod_{(i, f)} S_{i}$ over all pairs $(i, f)$ with $f_{i} A \to S_{i}$ and the morphism $g : A \to Q$ with $π_{(i, f)} g = f$ for all $(i, f)$ . Since the $S_{i}$ are coseparating, $g$ is monic. We also have $h : P \to Q$ defined by $π_{(i, f)} h = π_{i}$ for all $(i, f)$ .

Form the pullback
then $l$ is monic by Lemma 4.15, so $I ↣ P$ factors as $I \to B \overset{l}{↣} P$ and hence we have $I \to B \overset{k}{\to} A$ . So $I$ is initial. □

Example 4.17. Consider the inclusion $K H a u s \overset{I}{\to} T o p$ . Tychonoff’s Theorem says $K H a u s$ is closed under (small) products in $T o p$ . It’s closed under equalisers, since equalisers of pairs in $K H a u s$ are closed inclusions.

So $K H a u s$ is complete, and $I$ preserves limits. $K H a u s$ and $T o p$ are locally small, and $K H a u s$ is well-powered since subobjects of $X$ is isomorphic to inclusions of closed subspaces. And $K H a u s$ has a coseparator $[0, 1]$ , by Uryson’s Lemma.

So by Theorem 4.16, $I$ has a left adjoint $β$ .

Remark 4.18.

(a) The construction in Theorem 4.16 is closely parallel to Čech’s original construction of $β$ .
Given a space, Čech constructs $P = \prod_{f : x \to [0, 1]} [0, 1]$ and the map $g : X \to P$ defined by $π_{f} g = f$ . Then he takes $β X$ to be the closure of the image of $g$ , i.e. the smallest subobject of $(P, g)$ in $(X ↓ I)$ .
(b) We could have constructed $β$ using Theorem 4.12: to get a solution-set for $I$ at an object $X$ of $T o p$ , note that any continuous $f : X \to I Y$ factors as $X \to I Y^{'} \to I Y$ where $Y^{'}$ is the closure of the image of $f$ , and then since $Y^{'}$ has a dense subspace of cardinality $\leq card X$ , we have $card Y^{'} \leq 2^{2^{card X}}$ .

5 Monads

Suppose we have $C ⇄_{G}^{F} D$ , $(F ⊣ G)$ . How much of the adjunction can we describe in terms of $C$ (supposing we can’t know anything about $D$ , or know very little about it)?

We have:

The functor $T = G F : C \to C$ .
The unit $η : 1_{C} \to T$ .
The natural transformation $μ = G 𝜀_{F} : T T \to T$ .

From the triangular identities of Theorem 3.7, we obtain the commutative triangles:

and from naturality of

𝜀

we obtain

Definition 5.1 (Monad). A monad on a category $C$ is a triple $(T, η, μ) = 𝕋$ where $T : C \to C$ , and $η : 1_{C} \to T$ and $μ : T T \to T$ satisfy the commutative diagrams

Example 5.2.

(a) Let $M$ be a monoid. The functor $M \times (∙) : S e t \to S e t$ has a monad structure: $η_{A} : A \to M \times A$ is $a \mapsto (1, a)$ and $μ_{A} : M \times M \times A \to M \times A$ sends $(m, m^{'}, a)$ to $(m m^{'}, a)$ . The three diagrams ‘are’ the unit and associative laws in $M$ .
(b) The functor $P : S e t \to S e t$ has a monad structure: the unit $η_{A} : A \to P A$ is the mapping $a \mapsto {a}$ (Example 1.7(c)) and the multiplication $μ_{A} : P P A \to P A$ sends a set of subsets of $A$ to their union.

Does every monad come from an adjunction?

Answered by Eilenberg-Moore and by Kleisli (1965).

Note that the monad of Example 5.2(a) is induced by $S e t ⇄_{U}^{M \times (∙)} [M, S e t]$ and that of Example 5.2(b) is induced by $S e t ⇄_{U}^{P} C S L a t t$ , where $C S L a t t$ is the category of complete semilattices (posets, with arbitrary joins). The free complete semilattice on $A$ is $P (A)$ : every $f : A \to U S$ extends uniquely to $\bar{f} : P (A) \to S$ where $\bar{f} (A^{'}) = \lor {f (a) | a \in A^{'}}$ .

An $M$ -set (respectively a complete semilattice) is a set $A$ equipped with a suitable mapping $M \times A \to A$ (respectively $P (A) \overset{\lor}{\to} A$ ).

Definition 5.3 (Eilenberg-Moore algebra). Let $𝕋 = (T, η, μ)$ be a monad on $C$ . By an Eilenberg-Moore algebra for $𝕋$ we mean a pair $(A, α)$ where $A \in ob C$ and $α : T A \to A$ satisfies

A TA TTA T A

(4) : ηA1Aα A(5) : TμαααA TA A

A homomorphism

f : (A, α) \to (B, β)

is a morphism

f : A \to B

satisfying

We write

C^{𝕋}

for the category of

𝕋

-algebras and homomorphisms.

Proposition 5.4. Assuming that:

$C$ a category
$𝕋$ a monad

Then the forgetful functor

C^{𝕋} \overset{G^{𝕋}}{\to} C

has a left adjoint

F^{𝕋}

, and the adjunction induces the monad

𝕋

Proof. We define $F^{𝕋} A = (T A, μ_{A})$ (an algebra by (2) and (3)) and $F^{𝕋} (A \overset{f}{\to} B) = T f$ (a homomorphism by naturality of $μ$ ). Clearly, $F^{𝕋}$ is functorial and $G^{𝕋} F^{𝕋} = T$ .

We establish the adjunction using Theorem 3.7: its unit is $η$ , and the counit $𝜀_{(A, α)}$ is just $α$ (a homomorphism $F^{𝕋} A \to (A, α)$ , by (5), and natural by (6)).

The triangular identity

is just (1), and

is (4).

Finally, $G 𝜀_{F^{𝕋} A} = μ$ by definition of $F^{𝕋} A$ . So the adjunction induces $(T, η, μ)$ . □

Note: $C ⇄_{G}^{F} D$ induces $𝕋$ , we can replace $D$ by its full subcategory on objects $F A$ .

So in trying to construct $D$ , we may assume $F$ is surjective (indeed, bijective) on objects. The morphisms $F A \to F B$ in $D$ must correspond to morphisms $A \to G F B = T B$ in $C$ .

Definition 5.5 (Kleisli category). Let $𝕋$ be a monad on $C$ . The Kleisli category $C_{𝕋}$ is defined by $ob C_{𝕋} = ob C$ , morphsims $A \overset{f}{\to} B$ in $C_{𝕋}$ are morphisms $A \overset{f}{\to} T B$ in $C$ . The identity $A \overset{}{\to} A$ is $A \overset{η_{A}}{\to} T A$ , and the composite of $A \overset{f}{\to} B \overset{g}{\to} C$ is $A \overset{f}{\to} T B \overset{T g}{\to} T T C \overset{μ_{C}}{\to} T C$ .

For the unit and associative laws, consider the diagrams

A TB TTC TT TD T TD

fTTμTμμTμgTCμTDhDhDD TC TT D T D

Proposition 5.6. Assuming that:

$C$ a category
$𝕋$ a monad

Then there is an adjunction

C ⇄_{G_{𝕋}}^{F_{𝕋}} C_{𝕋}

inducing the monad

𝕋

Proof. We define $F_{𝕋} A = A$ and $F_{𝕋} (A \overset{f}{\to} B) = A \overset{f}{\to} B \overset{η_{B}}{\to} T B$ . $F_{𝕋}$ preserves identities by definintion, and preserves composition by

A B TB

C TC T TC

fg1gTηT1μfBgC1TCCC T C

We define

G_{𝕋} A = T A

, and

G_{𝕋} (A \overset{f}{\to} B) = T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B

G_{𝕋}

preserves identities by (1), and preserves composites by

T A TT B T TTC T TC

TTμTμμTμfTBμTCgCgCC TB T TC T C

We verify the adjunction using Theorem 3.7:

G_{𝕋} F_{𝕋} (f) = T f

by (1) so

G_{𝕋} F_{𝕋} = T

and we take

η

as unit of the adjunction.

We define $T A \overset{𝜀_{A}}{\to} A$ to be $T A \overset{1_{T A}}{\to} T A$ . To verify the naturality square

the lower composite is

T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B

and the upper one is

T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B \overset{η_{T B}}{\to} T T B \overset{μ_{B}}{\to} T B

, which agree since (2) tells us that

μ_{B} η_{T B} = 1_{B}

The triangular identities become

F𝜀𝕋FηAFA 𝕋A F= GF A FA ηTηT1TηTATTATAAA TTA TTT A TT A

and

Finally,

G_{𝕋} 𝜀_{F_{𝕋} A} = μ_{A}

, so

(F_{𝕋} ⊣ G_{𝕋})

induces the monad

𝕋

. □

Given a monad $𝕋$ on $C$ , we write $Adj (𝕋)$ for the category whose objects are adjunctions $(C ⇄_{G}^{F} D)$ inducing $𝕋$ , and morphisms $(C ⇄_{G}^{F} D) \to (C ⇄_{G^{'}}^{F^{'}} D^{'})$ are functors $D \overset{K}{\to} D^{'}$ satisfying $K F = F^{'}$ and $G^{'} K = G$ .

Theorem 5.7. The Kleisli adjunction $(C ⇄_{}^{} C_{𝕋})$ is an initial object of $Adj (𝕋)$ , and the Eilenberg-Moore adjunction $(C ⇄_{}^{} C^{𝕋}$ is terminal.

Proof. Suppose given $(C ⇄_{G}^{F} D)$ in $Adj (𝕋)$ . We define $K : D \to C^{𝕋}$ by $K B = (G B, G 𝜀_{B})$ (an algebra by one of the triangular identities for $η$ and $𝜀$ , and naturality of $𝜀$ ), $K (B \overset{g}{\to} B^{'}) = G g$ (a homomorphism by naturality of $𝜀$ ). $K$ is functorial since $G$ is, $G^{𝕋} K = G$ is obvious, and $K F A = (G F A, G 𝜀_{F A}) = (T A, μ_{A}) = F^{𝕋} A$ .

So $K$ is a morphism of $Adj (𝕋)$ .

Suppose $K^{'} : D \to C^{𝕋}$ is another such: then we must have $K^{'} B = (G B, β_{B})$ where $β : G F G \to G$ is a natural transformation since $K^{'} g = G g$ is a homomorphism $K^{'} B \to K^{'} B^{'}$ for all $g : B \to B^{'}$ . Also, since $K^{'} F = F^{𝕋}$ , we have $β_{F A} = μ_{A} = G 𝜀_{F A}$ for all $A$ .

For any $B$ , we have naturality squares

GF GF GB GF GB

GGβGβGF𝜀F𝜀B𝜀GFGBB𝜀GBBBGF GB GB

whose left edges are equal, and whose top edge is split epic, so we obtain

G 𝜀_{B} = β_{B}

for all

B

. So

K^{'} = K

We define $H : C_{𝕋} \to D$ by $H A = F A$ and $H (A \overset{f}{\to} B) = F A \overset{F f}{\to} F G F B \overset{𝜀_{F B}}{\to} F B$ . $H$ preserves identities and satisfies $H F_{𝕋} = F$ , by the first triangular identity for $η$ and $𝜀$ .

$H$ preserves the composite $A \overset{f}{\to} B \overset{g}{\to} C$ by

F A FGF B FGF GF C F GF C

FF𝜀F𝜀𝜀F𝜀fGFGFFgFFB𝜀GCCFFgCC FB FGF C F C

Also

G H A = G F A = T A = G_{𝕋} A

and

G H (A \overset{f}{\to} B) = (T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B) = G_{𝕋} (A \overset{f}{\to} B) .

So $H$ is a morphism of $Adj (𝕋)$ . Note that $H$ is full and faithful, since it sends $A \overset{f}{\to} G F B$ to its traspose across $(F ⊣ G)$ .

If $H^{'} : C_{𝕋} \to D$ is any morphism of $Adj (𝕋)$ , we must have $H^{'} A = F A = H A$ for all $A$ , and since $G H^{'} = G_{𝕋}$ and the adjunctions have the same unit, $H^{'}$ must send the transpose $A \overset{f}{\to} B$ of $A \overset{f}{\to} G F B$ to its transpose across $(F ⊣ G)$ . So $H^{'} = H$ . □

$C_{𝕋}$ has coproducts if $C$ does, but has few other limits or colimits. In contrast, we have:

Proposition 5.8. Assuming that:

$𝕋$ a monad on $C$

Then

(i) The forgetful functor $G^{𝕋} : C^{𝕋} \to C$ creates all limits which exist in $C$ .
(ii) If $C$ has colimits of shape $J$ , then $G^{𝕋}$ creates colimits of shape $J$ if and only if $T$ preserves them.

Proof.

(i) Suppose given $D : J \to C^{𝕋}$ ; write $D (j) = (G D (j), δ_{j})$ , and let $(L, (λ_{j} : L \to G D (j) | j \in ob J))$ be a limit for $G D$ . The composites $T L \overset{T λ_{j}}{\to} T G D (j) \overset{δ_{j}}{\to} G D (j)$ form a cone over $G B$ . So they induce a unique $λ : T L \to L$ . And $λ$ is a $𝕋$ -algebra structure on $L$ , since the identities $λ η_{L} = 1_{L}$ and $λ (T λ) = λ μ_{L}$ follow from uniqueness of factorisations through limits and it’s the unique lifting of the limit cone in $C$ to a cone in $C^{𝕋}$ . The fact that it’s a limit cone is straightforward.
(ii) If $G^{𝕋}$ creates colimits then it preserves them, but so does $F^{𝕋}$ since it’s a left adjoint, so $T$ preserves them too.
Conversely, given $D : J \to C^{𝕋}$ and a colimit cone $(G D (j) \overset{λ_{j}}{\to} L | j \in ob J)$ under $G D$ , we need to know that $(T G D (j) \overset{T λ_{j}}{\to} T L | j \in ob J)$ is a colimit cone to obtain $T L \overset{λ}{\to} L$ (and that $T T L$ is a colimit to verify that $λ$ is a $𝕋$ -algebra structure). Otherwise, the argument is as before. □

Given $(C ⇄_{G}^{F} D)$ , $(F ⊣ G)$ , how can we tell when $K : D \to C^{𝕋}$ is part of an equivalence?

Note: $H : C_{𝕋} \to D$ is an equivalence if and only if $F$ is essentially surjective.

We call $(F ⊣ F)$ (or the functor $G$ ) monadic if $K : D \to C^{𝕋}$ is part of an equivalence.

Lemma 5.9. Assuming that:

$C ⇄_{G}^{F} D$ is an adjunction inducing the monad $𝕋$ on $C$
for every $𝕋$ algebra $(A, α)$ , the pair $F G F A ⇉_{𝜀_{F A}}^{F α} F A$ has a coequaliser in $D$

Then

K : D \to C^{𝕋}

has a left adjoint

L

Proof. Write $F A \overset{λ_{(A, α)}}{\to} L (A, α)$ for the coequaliser. For any homomorphism $f : (A, α) \to (B, β)$ the two left hand squares in

FGF A F A L (A, α)

F𝜀FFλFLF𝜀FλαAG(AffβB(BF,,fα)β)FGF B F B L (B, β)

commute, so we get a unique

L f

making the right hand square commute. As usual, uniqueness implies functoriality of

L

For any $B \in ob D$ , morphisms $L (A, α) \to B$ correspond to morphisms $F A \overset{f}{\to} B$ satisfying $f (F α) = f 𝜀_{F A}$ . If $\bar{f} : A \to G B$ is the transpose of $f$ across $(F ⊣ G)$ , then $f (F α)$ transposes to $\bar{f} α : G F A \to G B$ , whereas $f 𝜀_{F A}$ transposes to $G f$ . But we can write $f = 𝜀_{B} (F \bar{f})$ by the proof of Theorem 3.7, so $G f = (G 𝜀_{B}) (G F \bar{f})$ . So $f (F α) = f 𝜀_{F A}$ if and only if

commutes, which happens if and only if

\bar{f} : (A, α) \to K B

C^{𝕋}

Naturality of the bijection follows from that of $f \mapsto \bar{f}$ . □

Note that since $G 𝕋 K = G$ , we have $L F^{𝕋} ≅ F$ by Corollary 3.6, and $L$ preserves coequalisers.

Definition 5.10 (Reflexive / split coequaliser diagram / $G$ -split).

(a)
We say a parallel pair $A ⇉_{g}^{f} B$ is reflexive if there exists $r : B \to A$ with $f r = g r = 1_{B}$ . Note that $F G F A ⇉_{𝜀_{F A}}^{F α} F A$ is reflexive, with common right inverse $F A \overset{F η_{A}}{\to} F G F A$ .
(b)
By a split coequaliser diagram, we mean a diagram
satisfying $h f = h g$ , $h s = 1_{C}$ , $g t = 1_{B}$ and $f t = s h$ . If these hold, then $h$ is a coequaliser of $(f, g)$ since if $B \overset{k}{\to} D$ satisfies $k f = k g$ then $k = k g t = k f t = k s h$ , so $k$ factors through $h$ , and the factorisation is unique since $h$ is (split) epic. Note that any functor preserves split coequalisers.
(c)
Given $G : D \to C$ , we say a pair $A ⇉_{g}^{f} B$ in $D$ is $G$ -split if there’s a split coequaliser diagram
in $C$ . The pair $(F α, 𝜀_{F A})$ in Lemma 5.9 is $G$ -split, since
is a split coequaliser diagram in $C$ .

Theorem 5.11 (Precise Monadicity Theorem). A functor $G : D \to C$ is monadic if and only if $G$ has a left adjoint and creates coequaliser of $G$ -split pairs in $D$ .

Theorem 5.12 (Crude Monadicity Theorem). Assuming that:

$G : D \to C$ preserves reflexive coequalisers
$G$ has a left adjoint
$G$ reflects isomorphisms

Then

G

is monadic.

Proof.

(5.11, $\Rightarrow$ ) Necessity of $F ⊣ G$ is obvious. For the other condition, it’s enough to show that $G^{𝕋} : C^{𝕋} \to C$ creates coequalisers of $G^{𝕋}$ -split pairs. This is a re-run of Proposition 5.8(ii): if $(A, α) ⇉_{g}^{f} (B, β)$ are such that
is a split coequaliser diagram, the coequaliser is preserved by $T$ and by $T T$ , so $C$ acquires a unique algebra structure $T C \overset{γ}{\to} C$ making $h$ a homomorphism, and $h$ is a coequaliser in $C^{𝕋}$ .
(5.11 $\Leftarrow$ and 5.12) Either set of hypotheses implies that $D$ has the coequalisers needed for Lemma 5.9, so $K$ has a left adjoint $L$ . So we need to show that the unit and counit of $(L ⊣ K)$ are isomorphisms.
The unit $(A, α) \to K L (A, α)$ is the factorisation of $G λ_{(A, α)} : G F A \to G L (A, α)$ through the ( $G^{𝕋}$ -split) coequaliser $G F A \overset{α}{\to} A$ of $G F G F A ⇉_{G 𝜀_{F A}}^{G F α} G F A$ . But either set of hypothesis implies that $G$ preserves the equaliser of $(F α, 𝜀_{F A})$ , so this factorisation is an isomorphism.

The counit $L K B \to B$ is the factorisation of $F G B \overset{𝜀_{B}}{\to} B$ through the coequaliser of $F G F G B ⇉_{𝜀_{F G B}}^{F G 𝜀_{B}} F G B$ . The hypotheses of Theorem 5.11 imply that $𝜀_{B}$ is a coequaliser of this pair, so the counit is an isomorphism. Those of Theorem 5.12 imply that the factorisation is mapped to an isomorphism by $G$ , so it’s an isomorphism. □

Remark 5.13.

(1) Reflexive coequalisers are colimits of shape $J$ , where $J$ is the category
satisfying $f r = g r = 1_{}$ , $r f = s$ and $r g = t$ .
(2) All colimits can be constructed from coproducts and reflexive coequalisers. This was proved in Proposition 4.4: the pair $P ⇉_{g}^{f} Q$ appearing in that proof is coreflexive with common left inverse $r : Q \to P$ defined by $π_{j} r = π_{1_{j}}$ for all $j$ .
(3) If $A ⇉_{g}^{f} B$ is reflexive, then in any commutative square
we have $h = h f r = k g r = k$ . So a pushout for
is a coequaliser for $A ⇉_{g}^{f} B$ .
(4) In $S e t$ , or more generally in a cartesian closed category, if $A_{i} ⇉_{g_{i}}^{f_{i}} B_{i} \overset{h_{i}}{\to} C_{i}$ ( $i = 1, 2$ ) are reflexive coequalisers, then $A_{1} \times A_{2} ⇉_{g_{1} \times g_{2}}^{f_{1} \times f_{2}} B_{1} \times B_{2} \overset{h_{1} \times h_{2}}{\to} C_{1} \times C_{2}$ is also a coequaliser. To see this, consider
in which all rows and columns are coequalisers. Then the lower right square is a pushout; but if $B_{1} \times B_{2} \overset{k}{\to} D$ coequalises $A_{1} \times A_{2} ⇉_{g_{1} \times g_{2}}^{f_{1} \times f_{2}} B_{1} \times B_{2}$ , then is also coequalises $A_{1} \times B_{2} ⇉_{}^{} B_{1} \times B_{2}$ and $B_{1} \times A_{2} ⇉_{}^{} B_{1} \times B_{2}$ , so if factors through the top and left edges of the lower right square, and hence through $B_{1} \times B_{2} \overset{h_{1} \times h_{2}}{\to} C_{1} \times C_{2}$ .

Example 5.14.

(a) The forgetful functor $G p \to S e t$ is monadic, and satisfies the hypotheses of Theorem 5.12. If $G ⇉_{g}^{f} H$ is a reflexive pair in $G p$ , with coequaliser $H \overset{h}{\to} K$ in $S e t$ , then $G \times G ⇉_{}^{} H \times H \to K \times K$ is a coequaliser, so the multiplication $H \times H \to H$ induces a binary operation $K \times K \to K$ , which is the unique group multiplication on $K$ making $h$ a homomorphism, and it makes $h$ into a coequaliser in $G p$ .
The same argument works for $A b G p$ , $R n g$ , $L a t$ , $D L a t$ , ….

It doesn’t work for categories like $C S L a t$ or $C L a t$ , but here we can use Theorem 5.11 provided the forgetful functor has a left adjoint.
(b) Any reflection is monadic: this can be proved using Theorem 5.11. If $D \subseteq C$ is a reflective subcategory, and $A ⇉_{g}^{f} B$ is a pair in $D$ for which there exists
in $C$ satisfying the equaitions of Definition 5.10(b), then $t \in mor D$ since $D$ is full, so $f t = s h$ is in $D$ , but $D$ is closed under splittings of idempotents by Example 4.7(d), so $h$ belongs to it.
(c) Consider the composite adjunction
where $(L ⊣ I)$ is the adjunction of Example 3.11(b). The two factors are monadic, but the composite isn’t since free abelian groups are torsion free, so $G I L F ≃ G F$ and its category of algebras is $≅ A b G p$ .
(d) The contravariant power-set functor $P^{*} : {S e t}^{o p} \to S e t$ is monadic, and satisfies the hypotheses of Theorem 5.12. Its left adjoint is $P^{*} : S e t \to {S e t}^{o p}$ by Example 3.2(i), and it reflects isomorphisms by Example 2.9(a).
Let $E \overset{e}{\to} A ⇉_{g}^{f} B$ be a coreflexive equaliser diagram in $S e t$ . Then
is a pullback by Remark 5.13(c), so
commutes. But we also have $(P^{*} e) (P e) = 1_{P E}$ and $(P^{*} f) (P f) = 1_{P B}$ since $e$ and $f$ are injective, so
is a split coequaliser diagram.
(e) The fogetful functor $T o p \overset{U}{\to} S e t$ is not monadic; the monad on $S e t$ induced by $(D ⊣ U)$ is $(1_{S e t}, 1_{1_{S e t}}, 1_{1_{S e t}})$ so its category of algebras is $≅ S e t$ .
(f) The composite adjunction
is monadic. We’ll prove this using Theorem 5.11: suppose given $X ⇉_{g}^{f} Y$ in $K H a u s$ and a split coequaliser
in $S e t$ . The quotient topology on $Z$ is the unique topology making $h$ into a coequaliser in $T o p$ , and it’s compact, so $h$ will be a coequaliser in $K H a u s$ provided $Z$ is Hausdorff. It is also the unique topology that could make $h$ into a morphism of $K H a u s$ .
But, given an equivalence relation $S$ on a compact Hausdorff space $Y$ , $Y ∕ S$ is Hausdorff if and only if $S$ is closed in $Y \times Y$ .

In our case, if $(y_{1}, y_{2}) \in S$ (i.e. $h (y_{1}) = h (y_{2})$ ) then $x_{1} = t (y_{1})$ and $x = t (y_{2})$ satisfy $g (t_{1}) = y_{1}$ , $g (x_{2}) = y_{2}$ and $f (x_{1}) = f (x_{2})$ .

Conversely, if we have $x_{1}$ and $x_{2}$ as above, then $h (y_{1}) = h (y_{2})$ , so $S = g \times g (R)$ where $R \subseteq X \times X$ is ${(x_{1}, x_{2}) | f (x_{1}) = f (x_{2})}$ . But $R$ is closed in $X \times X$ since it’s the equaliser of $X \times X ⇉_{f π_{2}}^{f π_{1}} Y$ . So $R$ is compact, so $S$ is compact, so $S$ is closed in $Y \times Y$ .

Definition 5.15 (Monadic tower). Let $C ⇄_{G}^{F} D$ be an adjunction where $D$ has reflexive coequalisers. The monadic tower of $(F ⊣ G)$ is the diagram

where

𝕋

is the monad induced by

(F ⊣ G)

, and

K

and

L

are as in Theorem 5.7 and Lemma 5.9, and

𝕊

is the monad induced by

(L ⊣ K)

and so on.

We say $(F ⊣ G)$ has monadic length $n$ if we reach an equivalence after $n$ steps.

6 Filtered Colimits

Definition 6.1 (Filtered). We say a category $C$ is filtered if every finite diagram $D : J \to C$ has a cone under it.

Lemma 6.2. $C$ is filtered if and only if:

(i)
$C$ is nonempty.
(ii)
Given $A, B \in ob C$ , there exists a cospan $A \to C \leftarrow B$ .
(iii)
Given $A ⇉_{g}^{f} B$ in $C$ , there exists $B \overset{h}{\to} C$ with $h f = h g$ .

Proof.

$\Rightarrow$ Since each of (i) - (iii) is a special case of Definition 6.1.
$\Leftarrow$ (i) deals with the empty diagram.
Given $D : J \to C$ with $J$ finite and non-empty, by repeated use of (ii) we can find $A$ with morphisms $D (j) \to A$ for all $j$ . Then by repeated use of (ii) we can find $A \to B$ coequalising
for each $α \in mor J$ . □

For preorders, we say directed instead of filtered.

Definition 6.3 (Has filtered colimits). We say $C$ has filtered colimits if every $D : J \to C$ , where $J$ is small and filtered, has a colimit.

Note that direct limits as in Example 4.3(g) are directed colimits.

Lemma 6.4. Assuming that:

$C$ has finite colimits
$C$ has directed colimits

Then

C

has all small colimits.

Proof. By Proposition 4.4(i), enough to show $C$ has all small coproducts.

Given a set-indexeud family $(A_{j} | j \in J)$ of objects, the finite coproducts $\sum_{j \in F} A_{j}$ , for $F \subseteq J$ finite, form the vertices of a diagram of shape $P_{f} J = {F \subseteq J | F finite}$ whose edges are coprojections. $P_{f} J$ is directed, and a colimit for this diagram has the universal property of a coproduct $\sum_{j \in J} A_{j}$ . □

Suppose given a $D : I \times J \to C$ , where $C$ has limits of shape $I$ and colimits of shape $J$ .

L(j) L(j′) colimJ L

limI M

D (i,j) D(i,j′) M (i)

LDDDMD(β(i(α(α(α(i),β,,)′,D)j)j′β))(i′,j) D(i′,j′) M (i′)

We can form

L (j) = \lim_{I} (D (∙, j) : I \to C)

, by Example 4.7(e) these are the vertices of a diagram

L : J \to C

, and we can form

{colim}_{J} L

Similarly, the colimits $M (i) = {colim}_{J} D (i, ∙)$ form a diagram of shape $I$ , and we can form $\lim_{I} M$ . We get an induced morphism ${colim}_{J} L \to \lim_{I} M$ ; if this is an isomorphism for all $D : I \times J \to C$ , we say colimits of shape $J$ commute with limits of shape $I$ in $C$ .

Equivalently, ${colim}_{J} : [J, C] \to C$ preserves limits of shape $I$ , or $\lim_{I} : [I, C] \to C$ preserves colimits of shape $J$ .

In Remark 5.13(d) we saw that reflexive coequalisers commute with finite products in $S e t$ .

Theorem 6.5. Assuming that:

$J$ a small category

Then colimits of shape

J

commute with all finite limits in

S e t

if and only if

J

is filtered.

Proof.

$\Rightarrow$ Let $D : I \to J$ be a diagram with $I$ finite. We have a diagram $E : I^{o p} \times J \to S e t$ defined by $E (i, j) = J (D (i), j)$ .
For each $i$ , $({colim}_{J} E) (i)$ is a singleton since every $D (i) \to j$ is identified with $1_{D (i)}$ in the colimit, so $\lim_{I} {colim}_{J} E$ is a singleton.

But elements of $\lim_{I} E (∙, j)$ are cones under $D$ with apex $j$ , so if ${colim}_{J} \lim_{I} E$ is nonempty there must be such a cone for some $j$ .
$\Leftarrow$ Suppose given $D : I \times J \to S e t$ where $I$ is finite and $J$ is filtered. In general, the colimitof $E : J \to S e t$ is the quotient of $∐_{j \in ob J} E (j)$ by the smallest equivalence relation identifying $x \in E (j)$ with $D (α) (x) \in E (j^{'})$ for all $α : j \to j^{'}$ in $J$ . For filtered $J$ , this identifies $x \in E (j)$ with $x^{'} \in E (j^{'})$ if and only if there exists $j \overset{α}{\to} j^{″} \overset{α^{'}}{\leftarrow} j^{'}$ with $E (α) (x) = E (α^{'}) (x^{'})$ , and moreover if $j = j^{'}$ we may assume $α = α^{'}$ .
Now, given an element $x$ of $\lim_{I} {colim}_{J} D$ , we can write it as $(x_{i} | i \in ob I)$ where $x_{i} \in {colim}_{J} D (i, ∙)$ is an equivalence class of elements $x_{i j} \in D (i, j)$ . If $α : i \to i^{'}$ in $I$ , then $D (α, j) (x_{i} j)$ and $x_{i^{'} j^{'}}$ represent the same element of ${colim}_{J} D (i^{'}, ∙)$ so by repeated use of Lemma 6.2(ii) we can choose representatives in $D (i, j_{0})$ for some fixed $j_{0}$ , and by repeated use of Lemma 6.2(iii) we can assume that these representatives define an element of $\lim_{I} D (∙, j_{0})$ . This defines an element of ${colim}_{J} \lim_{I} D$ mapping to the given element of $\lim_{I} {colim}_{J} D$ .

The proof of injectivity is similar: if two elements $x, y$ of ${colim}_{J} \lim_{I} D$ have the same image in $\lim_{I} {colim}_{J} D$ we can choose representatives $x_{j}, y_{j}$ in $\lim_{I} D (∙, j)$ and then find $j \to j^{'}$ so that each of the components $x_{i j}$ and $y_{i j}$ map to the same element of $D (i, j^{'})$ under $j \to j^{'}$ . So $x = y$ in ${colim}_{J} \lim_{I} D$ . □

Corollary 6.6. Assuming that:

$C$ a category of finitary algebras as in Example 5.14(a)

Then

(i) The forgetful functor $U : C \to S e t$ creates filtered colimits.
(ii) Filtered colimits commute with finite limits in $C$ .

Proof.

(i) This is just like Example 5.14(a): Given a filtered diagram $D : J \to C$ and a colimit for $U D$ with apex $L$ , then $L^{n}$ is the colimit of $U D^{n}$ for all $n$ , so each $n$ -ary operation on the $D (j)$ ’s induces an $n$ -ary operation on $L$ , and $L$ also inherits all the equations defining $C$ , so there’s a unique lifting of the colimit cone under $U D$ to a colimit cone for $D$ .
(ii) Follows from (i) and Theorem 6.5, since $U$ also creates finite limits (and reflects isomorphisms). □

Similar results hold for categories such as $C a t$ .

Example 6.7. Consider the diagram

of shape

ℕ^{o p} \times 2

S e t

. The inverse limit of the top row is

\emptyset

, but that of the bottom row is

1

. So

\lim_{ℕ^{o p}} [ℕ^{o p}, S e t] \to S e t

doesn’t preserve epimorphisms; equivalently

{colim}_{ℕ} : [ℕ, {S e t}^{o p}] \to {S e t}^{o p}

doesn’t preserve monomorphisms. Thus by Remark 4.8, directed colimits don’t commute with pullbacks in

{S e t}^{o p}

Given a functor $F : C \to S e t$ , the category of elements of $F$ is $(1 ↓ F)$ : its objects are pairs $(A, x)$ with $x \in F A$ and morphisms $(A, x) \to (B, y)$ are morphisms $f : A \to B$ such that $(F f) (x) = y$ .

Proposition 6.8. Assuming that:

$C$ a small category
$C$ has finite limits
$F : C \to S e t$ a functor

Then the following are equivalent:

(i)
$F$ preserves finite limits.
(ii)
$(1 ↓ F)$ is cofiltered.
(iii)
$F$ is expresible as a filtered colimit of representable functors.

Proof.

(i) $\Rightarrow$ (ii) By Lemma 4.10, $(1 ↓ F)$ has finite limits so ${(1 ↓ F)}^{o p}$ is filtered.
(ii) $\Rightarrow$ (iii) Consider the diagram ${(1 ↓ F)}^{o p} \overset{U}{\to} C^{o p} \overset{Y}{\to} [C, S e t]$ where $U$ is the forgetful functor and $Y$ is the Yoneda embedding. A cone under this diagram (with apex $G$ , say) yields a family of morphisms $C (A, ∙) \overset{λ_{(A, x)}}{\to} G$ for each $x \in F A$ , subject to compatibility conditions which say that $(G f) Φ (λ_{(A, x)}) = Φ (λ_{(B, y)})$ for every $f : (A, x) \to (B, y)$ in $(1 ↓ F)$ , i.e. such that $x \mapsto Φ (λ_{(A, x)})$ is a natural transformation $F \to G$ . So the cone $(C (A, ∙) \overset{Ψ (x)}{\to} F | (A, x) \in ob (1 ↓ F))$ has the universal property of a colimit for the diagram.
(iii) $\Rightarrow$ (i) Functors of the form $C (A, ∙)$ preserve any limits which exist, so this follows from Theorem 6.5 plus the fact that colimits in $[C, S e t]$ are computed pointwise. □

Given a category $C$ with filtered colimits, we say $F : C \to D$ is finitary if it preserves filtered colimits. If $C = S e t$ , then a finitary $F$ is determined by its restriction to ${S e t}_{f}$ , since any set is the directed union of its finite subsets.

In fact the restriction functor $[S e t, D] \to [{S e t}_{f}, D]$ has a left adjoint (the left Kan extension functor) and the finitary functors are those in the image of this left adjoint (up to isomorphism).

For a category $C$ as in Example 5.14(a) or Corollary 6.6, the corresponding monad $𝕋$ on $S e t$ is finitary. From now on, ${S e t}_{f}$ will denote the skeleton of the category of finite sets whose objects are the sets $[n] = {1, 2, \dots, n}$ .

Definition 6.9 (Lawvere theory). By a Lawvere theory, we mean a small category $T$ together with a functor ${S e t}_{f} \to T$ which is bijective on objects and preserves finite coproducts. A model of a Lawvere theory $T$ in any category $C$ with finite products is a functor $M : T^{o p} \to C$ preserving finite products.

For example, if $𝕋$ is a monad on $S e t$ , the full subcategory of ${S e t}_{𝕋}$ whose objects are the sets $[n]$ is a Lawvere theory.

Lemma 6.10. Assuming that:

$T$ a Lawvere theory

Then the category of

T

-models in

S e t

is (equivalent to) a finitary algebra category in the sense of Example 5.14(a).

Proof. Given a model $M : T^{o p} \to S e t$ , we have $M [n] ≅ M {[1]}^{n}$ for all $n$ . Also, any morphism $M {[1]}^{n} \to M {[1]}^{p}$ induced by a morphism $[p] \to [n]$ in $T$ is determined by its composites with the projections $M {[1]}^{p} \to M [1]$ , so specifying $M$ on morphisms is determined by its effect on morphisms with domain $[1]$ .

So, given a set $A$ , specifying a model $M$ with $M [1] = A$ is equivalent to specifying operations $α_{A} : A^{n} \to A$ for each $α : [1] \to [n]$ in $T$ , subject to ${(v_{i})}_{A} (a_{1}, \dots, a_{n}) = a_{i}$ whenever $v_{i} : [1] \to [n]$ is the $i$ -th coprojection, and

commutes whenever

commutes. □

Note that the characterisation of $T$ -models in any category with finite products. Note also that the equations of Lemma 6.10 allow us to reduce any compound operation $α (β_{1} (x \dots), β_{2} (x \dots), \dots, β_{n} (x \dots))$ to a single operation $γ$ .

Theorem 6.11. Assuming that:

$C$ a category

Then the following are equivalent:

(i)
$C$ is equivalent to a finitary algebraic category in the sense of Example 5.14(a). (Recall that these categories are those whose objects are sets with finitary operations satisfying some equations, and morphisms are homomorphisms between them.)
(ii)
$C$ is equivalent to the category of $S e t$ -models of a Lawvere theory.
(iii)
$C ≃ {S e t}^{𝕋}$ for a finitary monad $𝕋$ on $S e t$ .

Proof.

(ii) $\Rightarrow$ (i) Let $T$ be the full subcategory of $C$ on the free algebras $F [n]$ , for $n \in ℕ$ . Then $T$ is a Lawvere theory, and for every object $A$ of $C$ , the functor $C (∙, A)$ restricted to $T$ preserves finite products, so it’s a model of $T$ . This defines a functor $T - M o d (S e t) \overset{Y}{\leftarrow} {S e t}^{𝕋}$ ; but $T - M o d (S e t) ≃ {S e t}^{𝕋^{'}}$ for some finitary monad $𝕋^{'}$ on $S e t$ , so we get a functor ${S e t}^{𝕋} \overset{Y}{\to} {S e t}^{𝕋^{'}}$ which is the identity on underlying sets.
In this situation, $Y$ is induced by a morphism of monads $𝕋^{'} \to 𝕋$ , i.e. a natural transformation $𝜃 : T^{'} \to T$ commuting with the units and multiplications. (Clearly, such a $𝜃$ induces a functor ${S e t}^{𝕋} \to {S e t}^{𝕋^{'}}$ sending $(A, α)$ to $(A, α 𝜃_{A})$ ).

But we know $𝜃_{[n]}$ is bijective for all $n$ , since elements of the free algebras on $[n]$ are just morphisms $[1] \to [n]$ in $T$ . But both functors are finitary, so $𝜃_{A}$ is bijective for all $A$ , i.e. it’s an isomorphism of monads. □

For a general monad $𝕋$ on $S e t$ , this construction produces a finitary monad $𝕋^{'}$ which is the coreflection of $𝕋$ in the category of finitary monads.

For example:

For $𝕋 = (double power-set)$ , we obtain $𝕋^{'} = {Boolean algebras}$ .
For $𝕋 = Stone-Čech$ , we obtain the trivial monad $(1_{S e t}, 1_{1_{S e t}}, 1_{1_{S e t}})$ .

7 Regular Categories

Definition 7.1 (Image, cover). We say a category $C$ has images if, for every $A \overset{f}{\to} B$ in $C$ , there exists a least $m : B^{'} ↣ B$ in $Sub (B)$ through which $f$ factors. We call $m$ the image of $f$ , and we say $f$ is a cover if its image is $1_{B}$ .

We write $A \overset{f}{⇾} B$ to indicate that $f$ is a cover.

Lemma 7.2. Any strong epimorphism is a cover. The converse holds if $C$ has equalisers and pullbacks.

Proof. If $f$ is strong epic, applying the definition to commutative squares of the form

shows that

f

is a cover.

For the converse, a cover $A \overset{f}{\to} B$ is epic since it can’t factor through the equaliser of any $B ⇉_{h}^{g} C$ with $g \neq h$ . To verify the other condition, suppose given

then the pullback of

m

along

h

is monic by Lemma 4.15, and

f

factors through it, so it’s an isomorphism. So we get

B \to C

by composing with the top edge of the pullback square. □

Here, if $C$ has images, image facorisation defines a functor $[2, C] \to [3, C]$ : given

if we form the image factorisations

we get a unique

I \to J

making both squares commute.

Definition 7.3 (Regular category). We say $C$ is regular if it has finite limits and images, and image factorisations are stable under pullback, i.e. if the left hand square above is a pullback then so are both right hand squares. (This is equivalent to saying that covers are stable under pullback).

Example 7.4.

(a) $S e t$ is regular and coregular: all monomorphisms and epimorphisms are strong, and so the two factorisations coincide and epimorphisms (respectively monomorphisms) are stable under pullback (respectively pushout).
(b) If $C$ is regular, so is any $[D, C]$ with images constructed pointwise (they’re stable under pushout since pullbacks are also constructed pointwise).
(c) If $C$ is regular, then so $C^{𝕋}$ for any monad $𝕋$ whose underlying functor $T$ preserves covers. If $f : (A, α) \to (B, β)$ is a morphism of $C^{𝕋}$ and $A ⇾ I ↣ B$ is the image factorisation of $f$ in $C$ , then in
we get a unique $ι$ making both squares commute, making $(I, ι)$ into a $𝕋$ -algebra, and it’s the image of $f$ in $C^{𝕋}$ .
In particular, any category monadic over $S e t$ is regular.
(d) If $C$ is a preorder, every morphism is its own image, and covers are isomorphisms. So $C$ is regular if and only if it has finite meets.
(e) $T o p$ has images and coimages: given $X \overset{f}{\to} Y$ , its image (respectively coimage) is its set-theoretic image topologised as a quotient of $X$ (respectively subspace of $Y$ ). $T o p$ isn’t regular, but it is coregular.

Proposition 7.5. Assuming that:

$C$ a regular

Then covers coincide with regular epimorphisms.

Proof.

$\Leftarrow$ Regular epimorphism implies strong epimorphism by Exercise 21˙4.
$\Rightarrow$ Suppose $A \overset{f}{⇾} B$ is a cover; let $R ⇉_{b}^{a} A$ be its kernel-pair, i.e. the pullback of
Suppose given $g : A \to C$ with $g a = g b$ ; form the image $A \overset{e}{⇾} \overset{(h, k)}{↣} B \times C$ of $A \overset{(f, g)}{\to} B \times C$ . We’ll show $h$ is an isomorphism, so that $k h^{- 1}$ is a factorisation of $g$ through $f$ . $h$ is a cover since $h e = f$ is, so we need to prove $h$ is monic.
Let $D ⇉_{m}^{l} I$ such that $h l = h m$ ; form the pullback
$e \times e$ factors as $A \times A \overset{1 \times e}{⇾} A \times I \overset{e \times 1}{⇾} I \times I$ , so $e \times e$ is a cover, and $p$ is a cover.

Now $f q = h e q = h l p = h m p = h e r = f r$ so $(q, r)$ factors through $(a, b)$ . But $(h, k) e a = (f, g) a = (f, g) b = (h, k) e b$ and $(h, k)$ is monic, so $e a = e b$ , so $e q = e r$ , i.e. $l p = m p$ . Also $p$ is epic, so $l = m$ . □

By a relation $A ↬ B$ in a category $C$ with finite products, we mean an isomorphism class of subobjects $R ↣ A \times B$ .

If $C$ has images, we define the composite of $A \overset{R}{↬} B \overset{S}{↬} C$ by forming the pullback

forming the image of

(a p, d q) : P \to A \times C

This is well-defined up to isomorphism and has the $A \overset{(1_{A}, 1_{A})}{↣} A \times A$ as $2$ -sided identities.

Lemma 7.6. Composition of relations in $C$ is associative if and only if $C$ is regular.

Proof.

$\Rightarrow$ Suppose given $A \overset{f}{\to} B \overset{e}{⇽} C$ . Consider the relations
Composing the right hand pair first, we get
and thus we get
Composing the left hand pair first, we begin by forming the pullback
and we endup with the image of $(p,!_{P}) : P \to A \times 1$ ; so $p$ must be a cover.
$\Leftarrow$ Suppose given relations $A \overset{R}{↬} B \overset{S}{↬} C \overset{T}{↬} D$ . If we form the pullbacks
then both $T \circ (S \circ R)$ and $(T \circ S) \circ R$ are the image of $U \to A \times D$ . □

We write $R e l (C)$ for the category whose objects are those of $C$ and whose morphisms are relations. Note that $R e l (S e t)$ is just $R e l$ as defined in Example 1.3(e).

We have a faithful functor $C \to R e l (C)$ which is the identity on objects and sends $A \overset{f}{\to} B$ to $A \overset{(1, f)}{↣} A \times B$ (for faithfulness, see Exercise 4.22(i)). We write $f_{∙}$ for $(1_{A}, f)$ .

Note that there’s an isomporphism $R e l (C) \to R e l (C^{o p})$ which is the identity on objects and sends $R \overset{(a, b)}{↣} A \times B$ to $R \overset{(b, a)}{↣} B \times A$ ; we denote this by $R^{\circ}$ , and write $f^{∙}$ for ${(f_{∙})}^{\circ}$ .

Also, $R e l (C)$ is enriched over $P o s e t$ (provided $R e l (C)$ is locally small, i.e. $C$ is well-powered), i.e. each $R e l (C) (A, B)$ has a partial order which is preserved by composition.

We say $A \overset{R}{↬} B$ is left adjoint to $B \overset{S}{↬} A$ if $1_{A} \leq S \circ R$ and $R \circ S \leq 1_{B}$ .

Proposition 7.7. $A \overset{R}{↬} B$ is a left adjoint in $R e l (C)$ if and only if it is of the form $f_{∙}$ .

Proof.

$\Leftarrow$ We show $(f_{∙} ⊣ f^{∙})$ : the composite $f^{∙} f_{∙}$ is just the kernel-pair $R \overset{(a, b)}{↣} A \times A$ of $f$ , and $A \overset{(1_{A}, 1_{A})}{↣} A \times A$ factors through it. Also $f_{∙} f^{∙}$ is the image of
so it contains $(1_{B}, 1_{B})$ .
$\Rightarrow$ Conversely, suppose $R \overset{(a, b)}{↣} A \times B$ has a right adjoint $R^{'} \overset{(b^{'}, a^{'})}{↣} B \times A$ . In forming $R^{'} \circ R$ , we take the pullback
So the image of $(a p, a^{'} p^{'})$ contains $A \overset{(1_{A}, 1_{A})}{\to} A \times A$ , so $a p$ factors as a cover followed by a split epimorphism, so $a$ is a cover.
Now, in the pullback
$q$ and $q^{'}$ are covers, but the image of $(b q, b^{'} q)$ is contained in $(1_{B}, 1_{B})$ so $b q = b^{'} q^{'}$ . But $a q = a^{'} q^{'}$ , so $R^{'} = R^{\circ}$ , $a = a^{'}$ , $b = b^{'}$ and $q = q^{'}$ . So $a$ is monic, and hence an isomorphism, so $R = (b a^{- 1})$ . □

P. Freyd developed a theory of allegories which have the structure of categories of relations and axiomatised those allegories $A$ for which the subcategory $A_{l a}$ is regular.

In a regular category $C$ , we say a relation $R : A ↬ A$ is reflexive if $𝟙_{A} \leq R$ , symmetric if $R^{\circ} = R$ , and transitive if $R \circ R \leq R$ . $R$ is an equivalence relation if it has all three properties. For any $A \overset{f}{\to} B$ in $C$ , the kernel-pair $R \overset{(a, b)}{\to} A \times A$ of $f$ is an equivalence relation. We say an equivalence relation $R$ is effective if it occurs as a kernel-pair, and $C$ is effective regular if all equivalence relations are effective.

$t f A b G p$ is regular but not effective regular: ${(m, n) \in ℤ \times ℤ | m \equiv n (m o d 2)}$ is a non-effective equivalence relation on $ℤ$ .

Note that an equivalence relation is idempotent in $R e l (C)$ , and if $A$ is an allegory and $E$ is a class of symmetric idempotents in $A$ then $A [\overset{ˇ}{E}]$ (as defined in Exercise 1.18) is an allegory; and if $A$ is $R e l (C)$ for a regular category $C$ , then:

Proposition 7.8. Assuming that:

$C$ a regular category
$E$ is the class of equivalence relations in $C$

Then

C_{eff} = {(R e l (C) [\overset{ˇ}{E}])}_{l a}

is effective regular, and the embedding

R e l (C) \to R e l (C) [\overset{ˇ}{E}]

restricts to a full and faithful regular functor

C \to C_{eff}

which is universal among regular functors

C \to D

where

D

is effective regular.

Note that if $C$ is effective regular, its equivalence relations are split idempotents in $R e l (C)$ : if $A \overset{R}{↬} A$ is the kernel-pair of $A \overset{f}{⇾} B$ then it splits as $f^{∙} f_{∙}$ (as we saw for $C = S e t$ in Exercise 1.19).

Definition 7.9 (Topos). A topos is a regular category $E$ for which the embedding $E \to R e l (E)$ sending $f$ to $f_{∙}$ has a right adjoint. We write the effect of the right adjoint on objects by $A \mapsto P A$ , and the unit $A \to P A$ as ${}_{A}$ , and the counit $P A ↬ A$ as $\exists_{A} ↣ P A \times A$ .

In $S e t$ , $P A$ is the power-set of $A$ , the unit is the mapping $a \mapsto {a}$ of Example 1.7(c), and $\exists_{A} = {(A^{'}, a) | a \in A^{'}} \subseteq P A \times A$ .

Note that (isomorphism classes of) subobjects of $A$ are in bijection with morphisms $1_{} \to P A$ . C. J. Mikkelses showed that any topos has finite colimits; we’ll give Bob Paré’s proof, which is much simpler.

Proposition 7.10. Assuming that:

$E$ a topos

Then there exists a monadic functor

E^{o p} \to E

. In particular,

E^{o p}

has finite colimits and if

E

has limits of shape

J

then it also has colimits of shape

J^{o p}

Proof. We make the assignment $A \mapsto P A$ into a functor $P : E \to E$ and a functor $P^{*} : E^{o p} \to E$ : given $f : A \to B$ , $P f : P A \to P B$ corresponds to the image of $\exists_{A} ↣ P A \times A \overset{1_{} \times f}{\to} P A \times B$ , and $P^{*} f$ corresponds to the pullback of

Given

C \overset{g}{\to} P A

corresponding to

R ↣ C \times A

(P f) g

corresponds to the image of

R ↣ C \times A \overset{1_{} \times f}{\to} C \times B

and similarly given

S ↣ D \times B

, composing with

P^{*} f

corresponds to pulling back along

D \times A \overset{1_{} \times f}{\to} D \times B

Given a pullback square

E

commutes, since both ways correspond to the image of the left vertical composite in

where both squares are pullbacks.

Now, as in Example 5.14(d), we have that if $E \overset{e}{\to} A ⇉_{g}^{f} B$ is a coreflexive in $E$ , then

is a split coequaliser coequaliser in

E

. Also,

P^{*}

is self-adjoint on the right, and it reflects isomorphisms by Exercise 7.17(v). The second assertion follows from Proposition 5.8(i). □

Definition 7.11 (Support, totally supported, capital).

(a)
By the support of an object $A$ in a regular category, we mean the image of $A \to 1$ . We say $A$ is well-supported if $A \to 1$ is a cover.
(b)
We say a regular category $C$ is totally supported if every object is well-supported. We say $C$ is almost totally supported if every object is either well-supported or a strict initial object, where we cann an object $0$ strict if every $A \to 0$ is an isomorphism. (Given finite limits, a strict object is initial since for any $A$ there exists $0 \overset{π^{- 1}}{\to} 0 \times A \overset{π_{2}}{\to} A$ , and the equaliser of any pair $0 ⇉_{}^{} A$ is $a$ ).
(c)
We say a regular category $C$ is capital if its terminal object $1$ is a detector, i.e. $C (1, ∙)$ reflects isomorphisms.

Example. $G p$ and $A b G p$ are totally-supported since their terminal objects are initial. $S e t$ is almost totally-supported and capital. Note that capital implies almost totally-supported since if $A$ isn’t well-supported there are no morphisms $1 \to A$ .

A representable functor $C (A, ∙)$ always preserves limits, so it’s a regular functor if and only if $A$ is cover-projective (c.f. Definition 2.10).

Lemma 7.12. Assuming that:

$C$ a locally small capital regular category

Then

1

is cover-projective.

Proof. Since covers are stable under pullback, we need to show that every $A ⇾ 1$ is split epic. If $A ≅ 1$ , nothing to prove. If not, the projections $A \times A ⇉_{}^{} A$ aren’t equal (since their coequaliser is $A ⇾ 1$ , by Proposition 7.5). So there exists $1 \to A \times A$ not factoring through their equaliser, so there exists $1 \to A \times A \to A$ . □

If $C$ is regular, the full subcategory $C_{ws}$ of well-supported objects is closed under finite products since

is a pullback, and under pullbacks of covers since if

A ⇾ B

then

A

and

B

have the same support.

We write $C_{tv}$ for the category obtained from $C_{ws}$ by adjoining a strict initial object $0$ : this is regular and almost totally-supported and the functor $C \to C_{tv}$ sending all non-well-supported objects to $0$ is regular (c.f. Exercise 5.19).

Lemma 7.13. Assuming that:

$C$ a small almost totally-supported regular category

Then there exists an isomorphism-reflecting regular functor

I : C \to C^{'}

, where

C^{'}

is also small and almost totally-supported, such that for every well-supported

A \in ob C

there exists a morphism

1 \to I A

C^{'}

not factoring through

I (m)

for any proper subobject

m : A^{'} ↣ A

C

Proof. Recall from Exercise 7.17: $C$ regular implies $C ∕ A$ regular for any $A$ , and for any $f : A \to B$ in $C$ pullback along $f$ defines a regular functor $f^{*} : C ∕ B \to C ∕ A$ , which has a left adjoint $Σ_{f} : C ∕ A \to C ∕ B$ sending $g : C \to A$ to $f g$ . And $f^{*}$ reflects isomorphisms if and only if $f$ is a cover.

We’ll define $C^{'}$ as ${(\hat{C})}_{tv}$ where $\hat{C}$ is easier to describe.

To satisfy the desired conclusion for a single well-supported object $A$ , enough to take ${(!)}_{A}^{*} : C ≅ C ∕ 1 \to C ∕ A$ , since ${(!_{A})}^{*} A = (A \times A \overset{π_{2}}{\to} A)$ acquires a point $Δ : (A \overset{1}{\to} A) \to (A \times A \to A)$ not factoring through $(A^{'} \times A \to A)$ for any proper $A ↣ A$ .

More generally, for any finite list $A_{1}, \dots, A_{n}$ of well-supported objects, we can take $C ∕ \prod_{i = 1}^{n} A_{i}$ .

We define a base to be a finite list $\vec{A} = (A_{1}, \dots, A_{n})$ of distinct well-supported objecs of $C$ . We preorder the set $B$ of bases by $\vec{A} \leq \vec{B}$ if $\vec{B}$ contains all the members of $\vec{A}$ . We write $\prod \vec{A}$ for the product $\prod_{i = 1}^{n} A_{i}$ and if $\vec{A} \leq \vec{B}$ we write $π_{\vec{B}, \vec{A}}$ for the product projection $\prod \vec{B} \to \prod \vec{A}$ . This makes $\vec{A} \mapsto \prod \vec{A}$ into a functor $B^{o p} \to C$ .

Hence the assignment $\vec{A} \to C ∕ \prod \vec{A}$ , $π_{\vec{B}, \vec{A}} \mapsto π_{\vec{B}, \vec{A}}^{*}$ is ‘almost’ a functor $B \to C a t$ .

We now define $\hat{C}$ : its objects are pairs $(\vec{B}, f)$ where $\vec{B}$ is a base and $f : A \to \prod \vec{B}$ is an object of $C ∕ \prod \vec{B}$ . Morphisms $(\vec{B}, f) \to ({\vec{B}}^{'}, f^{'})$ are represented by pairs $(\vec{C}, g)$ where $\vec{C}$ is a base containing $\vec{B}$ and ${\vec{B}}^{'}$ and $g : π^{*} f \to {π^{'}}^{*} f^{'}$ in $C ∕ \prod \vec{C}$ , subject to the relation which identifies $(\vec{C}, g)$ with $({\vec{C}}^{'}, g^{'})$ if $\vec{C} \leq {\vec{C}}^{'}$ and the pullback of $g$ to $C ∕ \prod \vec{C}$ is isomorphic to $g^{'}$ .

Clearly, each $C ∕ \prod \vec{B}$ sits inside $\hat{C}$ as a non-full subcategory; so in particular $C ≅ C ∕ \prod []$ is a subcategory of $\hat{C}$ , $\hat{C}$ is regular, and the inclusions $C ∕ \prod \vec{B} \to \hat{C}$ are isomorphism-reflecting regular functors.

Given a finite diagram in $\hat{C}$ , we can choose $\vec{B}$ such that all edges of the diagram appear as morphisms in $C ∕ \prod \vec{B}$ , and take the limit there, and this is a limit in $\hat{C}$ . Similarly for images.

Also, if a morphism $f$ becomes an isomorphism in $\hat{C}$ , its inverse must live $C ∕ \prod \vec{B}$ for some $\vec{B}$ , hence $f$ is an isomorphism $C ∕ \prod \vec{B}$ .

We define $C^{'} = {(\hat{C})}_{tv}$ : the induced functor $C \to \hat{C} \to C^{'}$ is still isomorphism reflecting since $C$ is almost totally-supported. □

Lemma 7.14. Assuming that:

$C$ a small regular and almost totally-supported category

Then there exists an isomorphism reflecting regular functor

C \to \hat{C}

where

C

is capital. Hence in particular, there is an isomorphism-reflecting regular functor

C \to S e t

Proof. Consider the sequence

C = C_{0} \to C_{1} \to C_{2} \to \dots,

where each $C_{n + 1}$ is obtained from $C_{n}$ by the construction of Lemma 7.13.

We define $\hat{C}$ to be the pseudo-colimit of this sequence: objects are pairs $(n, A)$ where $A \in ob C_{n}$ , and morphisms $(n, A) \to (m, B)$ are represented by pairs $(p, f)$ where $p \geq \max {m, n}$ and $F : I A \to I^{'} B$ in $C_{p}$ , modulo the identification of $(p, f)$ with $(p^{'}, f^{'})$ if $p \leq p^{'}$ and $f^{'} = I f$ .

The proof that $C$ is regular, and that the embeddings $C_{n} \to \hat{C}$ are isomorphism-reflecting regular functors, is as in Lemma 7.13.

Given any non-invertible monomorphism $A^{'} ↣ A$ in $\hat{C}$ , it lives in $C_{n}$ for some $n$ , so there exists $1 \to A$ in $C_{n + 1}$ not factoring through $A^{'} ↣ A$ .

But if $A \overset{f}{\to} B$ isn’t monic in $\hat{C}$ , the legs $R ⇉_{b}^{a} A$ of its kernel-pair aren’t equal, so there exists $1 \overset{r}{\to} R$ not factoring through their equation, so $1 ⇉_{b r}^{a r} A$ are distinct but have the same composite with $f$ .

So $\hat{C} (1, ∙)$ reflects monomorphisms and hence reflects isomorphisms. □

Theorem 7.15. Assuming that:

$C$ small and regular

Then there exists a set

I

and an isomorphism-reflecting regular functor

C \to {S e t}^{I}

Proof. Let $I$ be a representative set of subobjects of $1$ in $C$ , and for each $U \in I$ consider the composite

C \overset{{(!_{U})}^{*}}{\to} C ∕ U \to {(C ∕ U)}_{tv} \to \hat{{(C ∕ U)}_{tv}} \to S e t,

where the third factor is the functor of Lemma 7.14 and the fourth is represented by $1$ .

Given any non-invertible morphism $A \overset{f}{\to} B$ in $C$ , if $U$ is the support of $B$ then ${(!)}_{H}^{*} f$ remains non-invertible in $C ∕ U$ and its codomain is well-supported there, so it remains non-invertible in ${(C ∕ U)}_{tv}$ and hence in $S e t$ .

So these functors collectively reflect isomorphisms. □

Remark 7.16.

(a) Barr’s original embedding theorem produces a full and faithful regular functor $C \to [D, S e t]$ for some small category $D$ . Moreover if $C$ is almost totally-supported we can take $D$ to be a monoid.
(b) Theorem 7.15 yields a ‘meta theorem’ saying that ‘anything we can prove in $S e t$ is true in all regular categories’.
For example to prove Proposition 7.5 (cover implies regular epic), given a cover $A \overset{f}{⇾} B$ in a regular category $C$ , and a $A \overset{g}{\to} C$ having equal composites with the kernel-pair $R ⇉_{}^{} A$ of $f$ , we can cut down to a small subcategory $C^{'}$ containing $f$ and $g$ and closed under finite limits and images, and then show that the first component of $I \overset{(h, k)}{↣} A \times C$ becomes an isomorphism in ${S e t}^{I}$ .
(c) Abelian categories are regular categories enriched over $A b G p$ (i.e. for any two objects $A$ and $B$ , $A (A, B)$ has an abelian group structure and composition distributes over addition).
Abelian categories are totally-supported since their terminal objects are initial, so for any small abelian $A$ we get an isomorphism-reflecting regular functor $A \to S e t$ and hence an isomorphism-reflecting functor $A ≅ A b G p (A) \to A b G p (S e t) = A b G p$ .