Category Theory

Remaining TODOs: 54

This document contains notes for, and (not necessarily correct) solutions for exercises from Mac Lane, S. (1997), Categories For the Working Mathematician (2nd ed.).

I Categories, functors, and natural transformations

I.1 Axioms for categories

No exercises

I.2 Categories

Definition I.2.1

A directed graph is a set

𝑂

of objects, a set

𝐴

of arrows, and two functions

dom, cod : 𝐴 \to 𝑂

Definition I.2.2

In a directed graph, the set of composable pairs of arrows is the set

𝐴 \times {}_{𝑂}𝐴 ≔ {⟨ 𝑔, 𝑓 ⟩ | 𝑔, 𝑓 \in 𝐴, dom 𝑔 = cod 𝑓} .

Definition I.2.3

A category is a directed graph with two addition functions, $id : 𝑂 \to 𝐴; 𝑐 \mapsto {id}_{𝑐}$ and $\circ : 𝐴 \times {}_{𝑂}𝐴 \to 𝐴; ⟨ 𝑔, 𝑓 ⟩ \mapsto 𝑔 \circ 𝑓$ such that

dom (id 𝑎) = 𝑎 = cod (id 𝑎), dom (𝑔 \circ 𝑓) = dom 𝑓, cod (𝑔 \circ 𝑓) = cod (𝑔)

for all objects $𝑎 \in 𝑂$ and all composable pairs of arrows $⟨ 𝑔, 𝑓 ⟩ \in 𝐴 \times {}_{𝑂}𝐴$ , and such that the associativity and unit axioms hold.

For a category $𝒞︀$ , we write $Ob (𝒞︀) = 𝑂, Ar (𝒞︀) = 𝐴$ , and $𝑐 \in 𝒞︀, 𝑓 \in 𝒞︀$ to mean $𝑐 \in Ob (𝒞︀), 𝑓 \in Ar (𝒞︀)$ respectively.

Definition I.2.4

Given a category $𝒞︀$ and two objects $𝑏, 𝑐 \in 𝒞︀$ , the hom-set

{hom}_{𝒞︀} (𝑏, 𝑐) ≔ {𝑓 | 𝑓 \in 𝒞︀, dom 𝑓 = 𝑏, cod 𝑓 = 𝑐}

is the set of arrows from

𝑏

𝑐

𝒞︀

Example I.2.5

$𝟎$: is the empty category.
$𝟏$: is the category with one object and one (identity) arrow.
$𝟐$: is the category with two objects $𝑎, 𝑏$ , and one arrow $𝑓 : 𝑎 \to 𝑏$ (plus the identity arrows)
$𝟑$: is the category with three objects $𝑎, 𝑏, 𝑐$ with non-identity arrows from $𝑓 : 𝑎 \to 𝑏, 𝑔 : 𝑏 \to 𝑐$ and $𝑔 \circ 𝑓 : 𝑎 \to 𝑐$ .

Definition I.2.6

A category is discrete if every arrow is an identity.

Definition I.2.7

A monoid is a category with just one object.

Remark I.2.8

Arrows can be parallel - that is, given objects

𝑎, 𝑏

, there can be several distinct arrows between

𝑎

and

𝑏

Example I.2.9

A group is a monoid in which every arrow has a two-sided inverse under composition.

Definition I.2.10

For a commutative ring

𝐾

, the category

Matr𝐾 has objects

ℕ_{0}

and

hom (𝑛, 𝑚) = {ℳ︀}_{𝑚 \times 𝑛} (𝐾)

, with composition the usual matrix product.

Definition I.2.11

For

𝑉

a family of sets, the category

Ens𝑉 has object set

𝑉

, and arrows all functions between them, with composition the usual function composition.

Definition I.2.12

A preorder is a category in which, for each pair of objects $𝑝, 𝑝^{'}$ , there is at most one arrow $𝑝 \to 𝑝^{'}$ .

We define a binary operation $\leq$ on a preorder $𝒫︀$ such that $𝑝 \leq 𝑝^{'}$ iff there is an arrow $𝑝 \to 𝑝^{'}$ in $𝒫︀$ .

Remark I.2.13

Partial orders are preorder with antisymetry.

TODO more examples?

I.3 Functors

Definition I.3.1

For categories $ℬ︀, 𝒞︀$ , a functor $𝑇 : ℬ︀ \to 𝒞︀$ consists of an object function which assigns to each object $𝑏 \in ℬ︀$ an object $𝑇 𝑏 \in 𝒞︀$ , and an arrow function which assigns to each arrow $𝑓 \in ℬ︀$ an arrow $𝑇 𝑓 \in 𝒞︀$ , such that the functor axioms

𝑇 (1_{𝑐}) = 1_{𝑇 𝑐}, 𝑇 (𝑔 \circ 𝑓) = 𝑇 𝑔 \circ 𝑇 𝑓

are satisfied.

Example I.3.2

The power set functor

𝒫︁ :

Set→Set assigns to each object

𝑋

the usual power set

𝒫︁ 𝑋

, and sends each arrow

𝑓 : 𝑋 \to 𝑌

𝒫︁ 𝑓 : 𝒫︁ 𝑋 \to 𝒫︁ 𝑌

such that, for each

𝑆 \subseteq 𝑋

(𝒫︁ 𝑓) 𝑆 = 𝑓 𝑆

Remark I.3.3

Functors can be composed by composing object and arrow functions respectively.

Remark I.3.4

For each category

𝒞︀

there is an identity functor

𝐼_{𝒞︀}

which acts as an identity under functor composition.

Definition I.3.5

An isomorphism between categories

ℬ︀, 𝒞︀

is a functor

𝑇 : ℬ︀ \to 𝒞︀

which is a bijection. (Equivalently,

𝑇

has a two-sided sided inverse).

Definition I.3.6

A forgetful functor is one that simply “forgets” some or all of the structure of an algebraic object.

Definition I.3.7

A functor $𝑇 : ℬ︀ \to 𝒞︀$ is full when, for each $𝑏, 𝑏^{'} \in ℬ︀$ , $𝑔 : 𝑇 𝑏 \to 𝑇 𝑏^{'} \in 𝒞︀$ , there is an arrow $𝑓 : 𝑏 \to 𝑏^{'} \in ℬ︀$ such that $𝑇 𝑓 = 𝑔$ .

That is, for each pair of objects $𝑐, 𝑐^{'}$ in the image of $𝑇$ , every arrow between $𝑐$ and $𝑐^{'}$ is also in the image of $𝑇$ .

Definition I.3.8

A functor

𝑇 : ℬ︀ \to 𝒞︀

is faithful, or an embedding, when for each

𝑏, 𝑏^{'} \in ℬ︀

and parallel arrows

𝑓_{1}, 𝑓_{2} : 𝑏 \to 𝑏^{'}

𝑇 𝑓_{1} = 𝑇 𝑓_{2}

implies

𝑓_{1} = 𝑓_{2}

Exercise I.3.1

TODO quotients, Lie algebras

Exercise I.3.2

TODO

Exercise I.3.3

TODO functor interpretation in special categories

Exercise I.3.4

TODO prove no functor sending groups to centres

Exercise I.3.5

TODO find two different functors on Grp with object function the identity

I.4 Natural transformations

Definition I.4.1

Given categories $ℬ︀, 𝒞︀$ and functors $𝑆, 𝑇 : ℬ︀ \to 𝒞︀$ , a natural transformation $𝜏 : 𝑆 \dot{\to} 𝑇$ is a function that assigns to each object $𝑏 \in ℬ︀$ an arrow $𝜏_{𝑏} \in 𝒞︀$ from $𝑇 𝑏 \to 𝑆 𝑏$ such that, for any objects $𝑏, 𝑏^{'} \in ℬ︀$ and arrow $𝑓 : 𝑏 \to 𝑏^{'}$ , $𝑇 𝑓 \circ 𝜏_{𝑏} = 𝜏_{𝑏^{'}} \circ 𝑆 𝑓$ . That is, for any such $𝑏, 𝑏^{'}, 𝑓$ , the following diagram commutes:

Remark I.4.2

Despite the notation, a natural transformation isn’t a morphism between functors. It is an assignment from objects to (preexisting!) arrows - and the arrows are ‘natural’ in the sense that they are just arrows that would be pointing from

𝑆 𝑏

𝑇 𝑏

anyway. The only ‘interesting’ part of a natural transformation is choosing which arrows to assign in the case of there being parallel arrows, in order to make each square as above commute.

Example I.4.3

Figure I.1: An example of a natural transformation,

𝜏 : 𝑆 \dot{\to} 𝑇

for functors

𝑆, 𝑇 : 𝟑 \to 𝒞︀

Definition I.4.4

A natural isomorphism is a natural transformation for which each

𝜏_{𝑏}

is invertible in

𝒞︀

. Then we write

𝜏 : 𝑆 ≅ 𝑇

Definition I.4.5

An equivalence between categories

𝒞︀

and

𝒟︀

is a pair of functors

𝑆 : 𝒞︀ \to 𝒟︀, 𝑇 : 𝒟︀ \to 𝒞︀

such that

𝐼_{𝒞︀} ≅ 𝑇 \circ 𝑆

and

𝐼_{𝒟︀} ≅ 𝑆 \circ 𝑇

Exercise I.4.1

Let $𝑆$ be a fixed set, and $𝑋^{𝑆}$ the set of all functions $ℎ : 𝑆 \to 𝑋$ . Show that $𝑋 \mapsto 𝑋^{𝑆}$ is the object function of a functor Set→Set, and that evaluation $𝑒_{𝑋} : 𝑋^{𝑆} \times 𝑆 \dot{\to} 𝑋$ , defined by $𝑒 (ℎ, 𝑠) = ℎ (𝑠)$ , the value of the function $ℎ$ at $𝑠 \in 𝑆$ , is a natural transformation.

Solution. Denote such a functor $𝑇 :$ Set→Set. Let the arrow function of $𝑇$ be $𝑇 (𝑓 : 𝑋 \to 𝑋^{'}) : 𝑋^{𝑆} \to 𝑋^{' 𝑆} ≔ 𝑓 \circ -$ defined by $(𝑓 \circ -) ℎ = 𝑓 \circ ℎ$ .

We can verify that this satisfies the functor axioms:

\begin{aligned} 𝑇 (1_{𝑋}) & = 1_{𝑋} \circ - \\ = 1_{𝑋^{𝑆}} \end{aligned}

and, for all $ℎ \in 𝑋^{𝑆}$ ,

\begin{aligned} 𝑇 (𝑓) \circ 𝑇 (𝑔) ℎ & = ((𝑓 \circ -) \circ (𝑔 \circ -)) ℎ \\ = (𝑓 \circ -) (𝑔 \circ ℎ) \\ = 𝑓 \circ (𝑔 \circ ℎ) \\ = (𝑓 \circ 𝑔) \circ ℎ \\ = ((𝑓 \circ 𝑔) \circ -) ℎ \\ = 𝑇 (𝑓 \circ 𝑔) ℎ \end{aligned}

so $𝑇 (𝑓 \circ 𝑔) = 𝑇 (𝑓) \circ 𝑇 (𝑔)$ .

Then note that

\begin{aligned} (𝑓 \circ 𝑒_{𝑋}) (ℎ, 𝑠) & = 𝑓 (ℎ (𝑠)) \\ = (𝑓 \circ ℎ) 𝑠 \\ = 𝑒_{𝑋^{'}} (𝑓 \circ ℎ, 𝑠) \\ = (𝑒_{𝑋^{'}} \circ (𝑓 \circ -)) (ℎ, 𝑠) & = (𝑒_{𝑋^{'}} \circ (𝑇 (𝑓) \times 1_{𝑆})) (ℎ, 𝑠), \end{aligned}

i.e. $𝑓 \circ 𝑒_{𝑋} = 𝑒_{𝑋^{'}} \circ (𝑇 (𝑓) \times 1_{𝑆})$ .

Therefore the following diagram commutes for any $𝑓 : 𝑋 \to 𝑋^{'}$ :

so $𝑒$ is a natural transformation that assigns to each set $𝑋$ an arrow $𝑒_{𝑋}$ .

Exercise I.4.2

Show that, if $𝐻$ is a fixed group, then $𝐺 \mapsto 𝐻 \times 𝐺$ defines a functor $𝐻 \times - :$ Grp→Grp, and each morphism $𝑓 : 𝐻 \to 𝐾$ of groups defines a natural transformation $𝐻 \times - \dot{\to} 𝐾 \times -$ .

Solution.

For a fixed group $𝐻$ , define the functor $𝐻 \times - :$ Grp→Grp by

(𝐻 \times -) 𝐺 \mapsto 𝐻 \times 𝐺

and

(𝐻 \times -) 𝑔 \mapsto 1_{𝐻} \times 𝑔

for any group homomorphism $𝑔$ .

We can verify that this definition satisfies the functor axioms:

\begin{aligned} (𝐻 \times -) 1_{𝐺} & = 1_{𝐻} \times 1_{𝐺} \\ = 1_{𝐻 \times 𝐺} \\ = 1_{(𝐻 \times -) 𝐺} \end{aligned}

and

\begin{aligned} (𝐻 \times -) (𝑔_{1} \circ 𝑔_{2}) & = 1_{𝐻} \times (𝑔_{1} \circ 𝑔_{2}) \\ = (1_{𝐻} \times 𝑔_{1}) \circ (1_{𝐻} \times 𝑔_{2}) \\ = ((𝐻 \times -) 𝑔_{1}) \circ ((𝐻 \times -) 𝑔_{2}) . \end{aligned}

Then for any morphism $𝑓 : 𝐻 \to 𝐾$ of groups, for any groups $𝐺_{1}, 𝐺_{2}$ , and for any group homomorphism $𝑔 : 𝐺_{1} \to 𝐺_{2}$ , the following diagram commutes:

where $𝑔_{𝐺} : 𝐺 \times 𝐺_{1} \to 𝐺 \times 𝐺_{2} ≔ 1_{𝐺} \times 𝑔$ and $𝑓_{𝐺} : 𝐻 \times 𝐺 \to 𝐾 \times 𝐺 ≔ 𝑓 \times 1_{𝐺}$ .

This commutes because

\begin{aligned} 𝑔_{𝐾} \circ 𝑓_{𝐺_{1}} & = (1_{𝐾} \times 𝑔) \circ (𝑓 \times 1_{𝐺_{1}}) \\ = (1_{𝐾} \circ 𝑓) \times (𝑔 \circ 1_{𝐺_{1}}) \\ = (𝑓 \circ 1_{𝐻}) \times (1_{𝐺_{2}} \circ 𝑔) \\ = 𝑓_{𝐺_{2}} \times 𝑔_{𝐻} . \end{aligned}

Hence $𝑓$ defines a natural transformation that assigns $𝑓_{𝐺}$ as above for every object $𝐺$ .

Exercise I.4.3

If $𝐺$ and $𝐻$ are groups (regarded as categories with one object each), and $𝑆, 𝑇 : 𝐺 \to 𝐻$ are functors (group homomorphisms), then there is a natural transformation $𝑆 \dot{\to} 𝑇$ iff $𝑆$ and $𝑇$ are conjugate, i.e. $\exists ℎ \in 𝐻$ s.t, $𝑇 𝑔 = ℎ (𝑆 𝑔) ℎ^{- 1}$ for all $𝑔 \in 𝐺$ .

Solution.

“ $⟹$ ”:

Since there is a natural transformation $𝜏 : 𝑆 \dot{\to} 𝑇$ , for every $𝑔 \in 𝐺$ , the following diagram commutes:

Figure I.4: The natural transformation

𝜏 : 𝑆 \to 𝑇

with $𝜏_{*_{𝐺}} ≕ ℎ$ for $ℎ \in 𝐻$ .

Then for every $𝑔 \in 𝐺$ ,

\begin{aligned} 𝜏_{*_{𝐺}} \circ (𝑆 𝑔) = (𝑇 𝑔) \circ 𝜏_{*_{𝐺}} \\ so & ℎ (𝑆 𝑔) = (𝑇 𝑔) ℎ \\ so & 𝑇 𝑔 = ℎ (𝑆 𝑔) ℎ^{- 1} . \end{aligned}

“ $⟸$ ”:

Suppose that there exists some $ℎ \in 𝐻$ s.t. for all $𝑔 \in 𝐺$ , $𝑇 𝑔 = ℎ (𝑆 𝑔) ℎ^{- 1}$ .

Then $(𝑇 𝑔) ℎ = ℎ (𝑆 𝑔)$ for all $𝑔 \in 𝐺$ , so Figure I.4 commutes for all $𝑔 \in 𝐺$ . Hence the assignment $𝜏_{*_{𝐺}} = ℎ$ defines a natural transformation $𝜏 : 𝑆 \dot{\to} 𝑇$ .

Exercise I.4.4

TODO (involves preorders)

Exercise I.4.5

Show that:

Every natural transformation $𝜏 : 𝑆 \dot{\to} 𝑇$ defines a function (also called $𝜏$ ) which sends each arrow $𝑓 : 𝑐 \to 𝑐^{'}$ of $𝒞︀$ to an arrow $𝜏 𝑓 : 𝑆 𝑐 \to 𝑇 𝑐^{'}$ of $ℬ︀$ in such a way that $𝑇 𝑔 \circ 𝜏 𝑓 = 𝜏 (𝑔 𝑓) = 𝜏 𝑔 \circ 𝑆 𝑓$ for each composable pair $⟨ 𝑔, 𝑓 ⟩$ .
Conversely, every such function $𝜏$ comes from a unique natural transformation with $𝜏_{𝑐} = 𝜏 (1_{𝑐})$ .

Solution.

Given a natural transformation $𝜏 : 𝑆 \dot{\to} 𝑇$ , the following diagram commutes for each $𝑓 : 𝑐 \to 𝑐^{'}$ of $𝐶$ :
where $𝜏 𝑓 = 𝜏_{𝑐^{'}} \circ 𝑆 𝑓 = 𝑇 𝑓 \circ 𝜏_{𝑐}$ .
Then taking a composable pair $⟨ 𝑔 : 𝑐^{'} \to 𝑐^{″}, 𝑓 : 𝑐 \to 𝑐^{'} ⟩$ ,
$\begin{aligned} 𝑇 𝑔 \circ 𝜏 𝑓 & = 𝑇 𝑔 \circ (𝑇 𝑓 \circ 𝜏_{𝑐}) \\ = (𝑇 𝑔 \circ 𝑇 𝑓) \circ 𝜏_{𝑐} \\ = 𝑇 (𝑔 \circ 𝑓) \circ 𝜏_{𝑐} \\ = 𝜏 (𝑔 𝑓) \\ = 𝜏_{𝑐^{″}} \circ 𝑆 (𝑔 \circ 𝑓) \\ = 𝜏_{𝑐^{″}} \circ (𝑆 𝑔 \circ 𝑆 𝑓) \\ = (𝜏_{𝑐^{″}} \circ 𝑆 𝑔) \circ 𝑆 𝑓 \\ = 𝜏 𝑔 \circ 𝑆 𝑓 . \end{aligned}$

b) Consider such a function $𝜏$ , then we construct a natural transformation $𝜏$ , assigning $𝜏_{𝑐} ≔ 𝜏 (1_{𝑐})$ , that defines that function.

Then for any arrow $𝑓 : 𝑐 \to 𝑐^{'}$ ,

\begin{aligned} 𝑇 𝑓 \circ 𝜏 (1_{𝑐}) & = 𝜏 (𝑓 1_{𝑐}) \\ ⟹ 𝑇 𝑓 \circ 𝜏_{𝑐} & = 𝜏 𝑓 \end{aligned}

and

\begin{aligned} 𝜏 (1_{𝑐} 𝑓) & = 𝜏 (1_{𝑐}) \circ 𝑆 𝑓 \\ ⟹ 𝜏 𝑓 & = 𝜏_{𝑐} \circ 𝑆 𝑓, \end{aligned}

hence

𝑇 𝑓 \circ 𝜏_{𝑐} = 𝜏_{𝑐} \circ 𝑆 𝑓,

which satisfies naturality. Moreover, this natural transformation is unique because by the unique definition of $𝜏_{𝑐}$ .

Remark

This gives an “arrows only” description of a natural transformation.

Exercise I.4.6

Let $𝐹$ be a field. Then the category of all finite-dimensional vector spaces over $𝐹$ , with morphisms all linear transformations, FinVect𝐹, is equivalent to the category Matr𝐹 (recalling that Matr𝐹 is the category with objects all positive integers, and arrows from $𝑛$ to $𝑚$ all $𝑚 \times 𝑛$ matrices under $𝐹$ ).

Solution.

STP that there exist functors $𝑆 :$ Matr𝐹→FinVect𝐹 and $𝑇 :$ FinVect𝐹→Matr𝐹 and natural isomorphisms $𝐼_{}$ FinVect𝐹≅𝑇∘𝑆, $𝐼_{}$ Matr𝐹≅𝑆∘𝑇, with $𝐼_{𝐶}$ the identity functor for a category $𝐶$ .

For each vector space $𝑉$ , fix a basis $𝐵_{𝑉}$ . Define $𝑇 𝑉 ≔ dim 𝑉, 𝑇 ℎ ≔ {rep}_{𝐵_{𝑉}, 𝐵_{𝑉}} ℎ$ for each vector space $𝑉$ and linear transformation $ℎ : 𝑉 \to 𝑊$ , and define $𝑆 𝑛 = 𝐹^{𝑛}$ , $𝑆 𝑀 = (\vec{𝑣} \mapsto 𝑀 \vec{𝑣})$ for each $𝑛 \in ℕ$ and $𝑀 \in {ℳ︀}_{𝑚 \times 𝑛}$ .

We can verify that $𝑆, 𝑇$ are functors:

\begin{matrix} 𝑇 (1_{𝑉}) = 𝐼 = 1_{𝑛} = 1_{𝑇 𝑉}; \\ 𝑇 (𝑔 \circ ℎ) = {rep}_{𝐵_{𝑉}, 𝐵_{𝑊}} (𝑔 \circ ℎ) = 𝑇 𝑔 \circ 𝑇 ℎ; \\ 𝑆 (1_{𝑛}) = 1_{𝐹^{𝑛}}; \\ 𝑆 (𝑃 \circ 𝐺) = \vec{𝑣} \mapsto 𝑃 𝑄 \vec{𝑣} = 𝑆 𝑃 \circ 𝑆 𝑄 . \end{matrix}

Then for each vector space $𝑉$ define a vector isomorphism $𝜏_{𝑉} : 𝑉 \to 𝐹^{𝑛}$ defined by $𝑉 \mapsto (𝑇 \circ 𝑆) 𝑉$ , and for each $𝑛 \in ℕ$ define $𝜎_{𝑛} ≔ id$ .

Then the following diagrams commute:

hence $𝐼 ≅ 𝑆 \circ 𝑇$ , $𝐼 ≅ 𝑇 \circ 𝑆$ , so Matr𝐹 and FinVect𝐹 are equivalent.

I.5 Monics, epics, and zeroes

Definition I.5.1

An arrow

𝑒 : 𝑎 \to 𝑏

is invertible in

𝒞︀

if there is an arrow

𝑒^{- 1} : 𝑎 \to 𝑏 \in 𝒞︀

such that

𝑒 \circ 𝑒^{- 1} = 1_{𝑏}

and

𝑒^{- 1} \circ 𝑒 = 1_{𝑎}

Remark I.5.2

If such an

𝑒^{- 1}

exists, it is unique.

Definition I.5.3

Two objects

𝑎, 𝑏 \in 𝒞︀

are isomorphic, written

𝑎 ≅ 𝑏

, if there is an invertible arrow (an isomorphism) between them.

Definition I.5.4

An arrow $𝑚 : 𝑎 \to 𝑏$ is monic in $𝒞︀$ when, for any parallel arrows $𝑓_{1}, 𝑓_{2} : 𝑑 \to 𝑎$ , $𝑚 \circ 𝑓_{1} = 𝑚 \circ 𝑓_{2}$ implies $𝑓_{1} = 𝑓_{2}$ .

That is, $𝑚$ is monic when it is left-cancellable.

Remark I.5.5

In Set and Grp, the monic arrows are precisely the injections/monomorphisms.

Definition I.5.6

An arrow

ℎ : 𝑎 \to 𝑏

is epi in

𝒞︀

when it is right-cancellable; that is, for parallel arrows

𝑔_{1}, 𝑔_{2} : 𝑑 \to 𝑎

𝑔_{1} \circ ℎ = 𝑔_{2} \circ ℎ

implies

𝑔_{1} = 𝑔_{2}

Remark I.5.7

In Set the epi arrows are the surjections/epimorphisms.

Definition I.5.8

For an arrow

ℎ : 𝑎 \to 𝑏

, a section of

ℎ

𝒞︀

is a right-inverse of

ℎ

𝒞︀

(i.e.

𝑟

is section of

ℎ

ℎ \circ 𝑟 = 1_{𝑏}

Proposition I.5.9

If $ℎ$ has a section, it is epi.

Proof. TODO (not given in MacLane)⁠ $□$

Remark I.5.10

The converse (that an epi arrow has a section) is true in Set but not Grp. (TODO: proof?)

Definition I.5.11

A retraction is a left-inverse.

Remark I.5.12

Sections and retractions are not necessarily unique.

Definition I.5.13

If we have arrows

𝑔, ℎ

with

𝑔 \circ ℎ = 1

, then

𝑔

is a split epi, and

ℎ

a split monic.

Definition I.5.14

An arrow

𝑓 : 𝑏 \to 𝑏

is idempotent if

𝑓 \circ 𝑓 = 𝑓

Proposition I.5.15

𝑔 \circ ℎ = 1

, then

𝑓 = ℎ \circ 𝑔

is defined and is idempotent (

𝑓 \circ 𝑓 = 𝑓

Definition I.5.16

We say that an idempotent

𝑓

splits when there exists arrows

𝑔, ℎ

with

𝑓 = ℎ 𝑔

and

𝑔 ℎ = 1

Definition I.5.17

An object

𝑡

is terminal in

𝒞︀

if, for every object object

𝑎 \in 𝒞︀

, there is exactly one arrow

𝑎 \to 𝑡

𝒞︀

Proposition I.5.18

Any two terminal objects in $𝒞︀$ are isomorphic.

Proof. TODO (not given)⁠ $□$

Definition I.5.19

An object

𝑠

is initial in

𝒞︀

if, for every object

𝑎 \in 𝒞︀

, there is exactly one arrow

𝑠 \to 𝑎

𝒞︀

Definition I.5.20

A null object in

𝒞︀

is one that is both initial and terminal.

Proposition I.5.21

If $𝒞︀$ has a null object, then it is unique up to isomorphism.

Proof. TODO⁠ $□$

Proposition I.5.22

Given a null object $𝑧 \in 𝒞︀$ , for any objects $𝑎, 𝑏 \in 𝒞︀$ , there is a unique arrow $𝑓 = 𝑔 \circ ℎ$ for $𝑔 : 𝑎 \to 𝑧$ and $ℎ : 𝑧 \to 𝑏$ .

Proof. TODO (not given)⁠ $□$

Definition I.5.23

Such an arrow is called the zero arrow from

𝑎

𝑏

Proposition I.5.24

Any composite with a zero arrow is a zero arrow.

Proof. TODO (not given)⁠ $□$

Definition I.5.25

A groupoid is a category in which every arrow is invertible.

Remark I.5.26

Every object $𝑥$ in a groupoid $𝒢︀$ forms a group ${hom}_{𝒢︀} (𝑥, 𝑥)$ .

If there is an arrow $𝑓 : 𝑥 \to 𝑥^{'}$ , then ${hom}_{𝒢︀} (𝑥, 𝑥) ≅ {hom}_{𝒢︀} (𝑥^{'}, 𝑥^{'})$ under conjugation.

Definition I.5.27

A groupoid is connected if there is an arrow joining any two of its objects.

Remark I.5.28

A connected groupoid can be determined up to isomorphism by a group and the set of objects.

Exercise I.5.1

TODO find arrow epi and monic but not invertible

Exercise I.5.2

TODO prove monic compose monic is monic, same for epi

Exercise I.5.3

TODO If

𝑔 \circ 𝑓

is monic, is

𝑔

monic?

Exercise I.5.4

TODO rings

Exercise I.5.5

TODO show epi in Grp is surjection

Exercise I.5.6

TODO show that all idempotents split in Set

Exercise I.5.7

TODO

Exercise I.5.8

TODO

Exercise I.5.9

TODO show that if

𝑇 : 𝐶 \to 𝐵

is faithful and

𝑇 𝑓

monic,

𝑓

monic

I.6 Foundations

TODO

I.7 Large Categories

TODO

I.8 Hom-Sets

TODO

II Constructions on Categories

II.1 Duality

Definition II.1.1

The dual of some statement about categories is the same statement with “codomain” and “domain” swapped, and swapping “

ℎ = 𝑔 \circ 𝑓

” with

ℎ = 𝑓 \circ 𝑔

Remark II.1.2

The dual of the dual of a statement is the original statement.

Remark II.1.3

Duality can be thought of as reversing arrows.

Theorem II.1.4 (duality principle)

If a statement is a consequence of the category theory axioms, then so is its dual.

Example II.1.5

A terminal object, if it exists, is unique; therefore, if an initial object exists, then it too is unique.

Warning

Forming the dual of a statement involving several categories reverses the arrows within those categories, but does not reverse functors.

II.2 Contravariance and Opposites

Definition II.2.1

For a category

𝒞︀

, the opposite category or dual category

{𝒞︀}^{op}

has objects

Ob (𝒞︀)

and arrows

𝑓^{op}

for each

𝑓 \in Ar (𝒞︀)

, with

𝑓 : 𝑎 \to 𝑏 \mapsto 𝑓^{op} : 𝑏 \to 𝑐

Remark II.2.2

The dual category is sometimes written

{𝒞︀}^{*}

Remark II.2.3

A statement is true about

𝒞︀

iff the dual of that statement is true about

{𝒞︀}^{op}

Definition II.2.4

Given a functor

𝑇 : {𝒞︀}^{op} \to {ℬ︀}^{op}

, the opposite functor

𝑇^{op}

is defined by

𝑐 \mapsto 𝑇 𝑐

and

𝑓^{op} \mapsto {(𝑇 𝑓)}^{op}

Remark II.2.5

The assignments

𝒞︀ \mapsto {𝒞︀}^{op}

and

𝑇 \mapsto 𝑇^{op}

defines a functor from

Cat→Cat.

Definition II.2.6

A regular functor is covariant, meaning that, given an arrow

𝑓 : 𝑎 \to 𝑏 \in 𝒞︀

, a functor

𝑇 : 𝒞︀ \to 𝒟︀

maps

𝑓

𝑇 𝑓 : 𝑇 𝑎 \to 𝑇 𝑏 \in 𝒟︀

Definition II.2.7

Given a functor $𝑆 : {𝒞︀}^{op} \to 𝒟︀$ , and we write $\overset{̅}{𝑆} 𝑓 = 𝑆 𝑓^{op}$ , then $\overset{̅}{𝑆}$ is a contravariant functor from $𝒞︀ \to 𝒟︀$ .

A contravariant functor $\overset{̅}{𝑆}$ satisfies

\overset{̅}{𝑆} (1_{𝑐}) = 1_{\overset{̅}{𝑆} 𝑐}, \overset{̅}{𝑆} (𝑓 𝑔) = (\overset{̅}{𝑆} 𝑔) (\overset{̅}{𝑆} 𝑓),

and, given an arrow $𝑓 : 𝑎 \to 𝑏 \in 𝒞︀$ , $\overset{̅}{𝑆}$ sends $𝑓$ to $\overset{̅}{𝑆} 𝑓 : \overset{̅}{𝑆} 𝑏 \to \overset{̅}{𝑆} 𝑎$ .

Definition II.2.8

For a locally small category $𝒞︀$ , we define for each object $𝑎 \in 𝒞︀$ the covariant hom-functor

𝒞︀ (𝑎, -) = hom (𝑎, -) : 𝒞︀ \to

Set,

which sends each object $𝑏$ to the hom-set ${hom}_{𝒞︀} (𝑎, 𝑏)$ , and each arrow $𝑘 : 𝑏 \to 𝑏^{'}$ the function

hom (𝑎, 𝑘) : hom (𝑎, 𝑏) \to hom (𝑎, 𝑏^{'})

defined by $𝑓 \mapsto 𝑘 \circ 𝑓$ for each arrow $𝑓 : 𝑎 \to 𝑏$ .

This function $hom (𝑎, 𝑘)$ is sometimes written $𝑘_{*}$ and called “composition with $𝑘$ on the left” or “the map induced by $𝑘$ ”.

Definition II.2.9

For each $𝑏 \in 𝒞︀$ , we define the contravariant hom-functor

𝒞︀ (-, 𝑏) = hom (-, 𝑏) : {𝒞︀}^{op} \to

Set

that sends each object $𝑎$ to ${hom}_{𝒞︀} (𝑎, 𝑏)$ and each arrow $𝑔 : 𝑎 \to 𝑎^{'}$ to the function

hom (𝑔, 𝑏) : hom (𝑎^{'}, 𝑏) \to hom (𝑎, 𝑏)

defined by

𝑓 \mapsto 𝑓 \circ 𝑔

, sometimes written

𝑔^{*}

and called “composition with

𝑔

on the right”.

Remark II.2.10

For arrows $𝑔 : 𝑎 \to 𝑎^{'}, 𝑘 : 𝑏 \to 𝑏^{'} \in 𝒞︀$ , $𝑘_{*} \circ 𝑔^{*} = 𝑔^{*} \circ 𝑘_{*}$ because the following diagram commutes in Set:

II.3 Products of Categories

Definition II.3.1

For categories $ℬ︀$ , $𝒞︀$ , the product category $ℬ︀ \times 𝒞︀$ has objects $⟨ 𝑏, 𝑐 ⟩$ for each object $𝑏$ of $ℬ︀$ and $𝑐$ of $𝒞︀$ , and arrows $⟨ 𝑓, 𝑔 ⟩$ for each arrow $𝑓$ of $ℬ︀$ and $𝑔$ of $𝒞︀$ , with the composite defined by

⟨ 𝑓, 𝑔 ⟩ \circ ⟨ 𝑔^{'}, 𝑔^{'} ⟩ = ⟨ 𝑓 \circ 𝑓^{'}, 𝑔 \circ 𝑔^{'} ⟩ .

Definition II.3.2

The product category $ℬ︀ \times 𝒞︀$ is equipped with projection functors $𝑃 : ℬ︀ \times 𝒞︀ \to ℬ︀, 𝑄 : ℬ︀ \times 𝒞︀ \to 𝒞︀$ defined by

𝑃 ⟨ 𝑓, 𝑔 ⟩ = 𝑓; 𝑄 ⟨ 𝑓, 𝑔 ⟩ = 𝑔

for objects and arrows $𝑓$ of $ℬ︀$ , $𝑔$ of $𝒞︀$ .

Theorem II.3.3 (universal property of product categories)

For product category $ℬ︀ \times 𝒞︀$ and any category $𝒟︀$ with functors $𝑅 : 𝒟︀ \to ℬ︀, 𝑇 : 𝒟︀ \to 𝒞︀$ , there is a unique functor $𝐹 : 𝒟︀ \to ℬ︀ \times 𝒞︀$ such that the following diagram commutes:

Proposition II.3.4 (Proposition 1 in Mac Lane)

Let $ℬ︀, 𝒞︀, 𝒟︀$ be categories. For all objects $𝑐 \in 𝒞︀$ and $𝑏 \in ℬ︀$ , let

𝐿_{𝑐} : ℬ︀ \to 𝒟︀, 𝑀_{𝑐} : 𝒞︀ \to 𝒟︀

be functors such that $𝑀_{𝑏} (𝑐) = 𝐿_{𝑐} (𝑏)$ for all $𝑏$ and $𝑐$ .

Then there exists a bifunctor $𝑆 : ℬ︀ \times 𝒞︀ \to 𝒟︀$ with $𝑆 (-, 𝑐) = 𝐿_{𝑐}$ for all $𝑐$ and $𝑆 (𝑏, -) = 𝑀_{𝑏}$ for all $𝑏$ , if and only if, for every pair of arrows $𝑓 : 𝑏 \to 𝑏^{'}, 𝑔 : 𝑐 \to 𝑐^{'}$ ,

𝑀_{𝑏^{'}} 𝑔 \circ 𝐿_{𝑐} 𝑓 = 𝐿_{𝑐^{'}} 𝑓 \circ 𝑀_{𝑏} 𝑔 .

These equal arrows in $𝒟︀$ are then the value $𝑆 (𝑓, 𝑔)$ of the arrow function $𝑆$ of $𝑓$ and $𝑔$ .

Proof.

Write $𝑏, 𝑐$ to mean $1_{𝑏}, 1_{𝑐}$ for any objects $𝑏 \in ℬ︀, 𝑐 \in 𝒞︀$ .

Then

⟨ 𝑏^{'}, 𝑔 ⟩ \circ ⟨ 𝑓, 𝑐 ⟩ = ⟨ 𝑏^{'} \circ 𝑓, 𝑔 \circ 𝑐 ⟩ = ⟨ 𝑓 \circ 𝑏, 𝑐^{'} \circ 𝑔 ⟩ = ⟨ 𝑓, 𝑐^{'} ⟩ \circ ⟨ 𝑏, 𝑔 ⟩ .

Suppose that $𝑆$ exists, then applying $𝑆$ to this gives

𝑆 (𝑏^{'}, 𝑔) \circ 𝑆 (𝑓, 𝑐) = 𝑆 (𝑓, 𝑐^{'}) \circ 𝑆 (𝑏, 𝑔)

which is equivalent to (1) by the definition of $𝑆$ .

Conversely, if (1) holds then this defines $𝑆$ satisfying the necessary conditions, and it can be verified that this is a bifunctor.⁠ $□$

Exercise II.3.1

TODO product categories special cases

Exercise II.3.2

TODO preorders

Exercise II.3.3

If ${{𝒞︀}_{𝑖} | 𝑖 \in 𝐼}$ is a family of categories indexed by a set $𝐼$ , describe the product $𝒞︀ = \prod_{𝑖} {𝒞︀}_{𝑖}$ , its projections $𝑃_{𝑖} : 𝒞︀ \to {𝒞︀}_{𝑖}$ , and establish the universal property of these projections.

Solution.

\begin{matrix} Ob (𝒞︀) = {{(𝑐_{𝑖})}_{𝑖 \in 𝐼} | 𝑐_{𝑖} \in Ob ({𝒞︀}_{𝑖})}; \\ Ar (𝒞︀) = {{(𝑓_{𝑖})}_{𝑖 \in 𝐼} | 𝑓_{𝑖} \in Ar ({𝒞︀}_{𝑖})}; \\ 𝑃_{𝑗} ({(𝑐_{𝑖})}_{𝑖 \in 𝐼}) = 𝑐_{𝑗} . \end{matrix}

The universal property of these projections in that, given a category $𝒟︀$ and functors ${𝑆_{𝑖} | 𝑖 \in 𝐼}$ , there exists a unique functor $𝐹 : 𝒟︀ \to 𝒞︀$ such that $𝐹 \circ 𝑃_{𝑖} = 𝑆_{𝑖}$ for each $𝑖 \in 𝐼$ .

Exercise II.3.4

TODO describe opposite of Matr

Exercise II.3.5

TODO topological spaces

II.4 Functor categories

Definition II.4.1

Given categories $ℬ︀, 𝒞︀$ , the functor category ${ℬ︀}^{𝒞︀}$ has objects all functors $𝑇 : 𝒞︀ \to ℬ︀$ and arrows natural transformations between those functors.

For natural transformations $𝜎 : 𝑅 \dot{\to} 𝑆, 𝜏 : 𝑆 \dot{\to} 𝑇$ , we define the composite $(𝜏 \cdot 𝜎) 𝑐 ≔ 𝜏 𝑐 \circ 𝜎 𝑐$ . This is a “vertical” composition, as demonstrated by the following diagram for any $𝑓 : 𝑐 \to 𝑐^{'} \in 𝒞︀$ :

Each parallelogram commutes (since $𝜎$ and $𝜏$ natural), so overall the diagram must commute.

Exercise II.4.1

TODO rings

Exercise II.4.2

Describe ${ℬ︀}^{𝑋}$ , for $𝑋$ a finite set.

Solution. Objects are the functors $𝑋 \to ℬ︀$ ; that is, functors that assign to each $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}$ an object of $ℬ︀$ . That is, the objects are $𝑛$ -tuples of objects of $ℬ︀$ , where $𝑛 = | 𝑋 |$ .

Arrows are natural transformations between such functors; because the only arrows in $𝑋$ are the identities, the naturality constraints just enforce that each natural transformation $𝜏$ is a function between $𝑛$ -tuples of objects of $ℬ︀$ .

Exercise II.4.3

TODO

Abℕ

Exercise II.4.4

For preorders $𝒫︀$ and $𝒬︀$ , describe ${𝒬︀}^{𝒫︀}$ and show that it is a preorder.

Solution. The objects of ${𝒬︀}^{𝒫︀}$ are all monotonic functions $𝑓 : 𝒫︀ \to 𝒬︀$ (see exercise TODO). The arrows of ${𝒬︀}^{𝒫︀}$ are all natural transformations between these functions - in particular by exercise TODO, a natural transformation between such $𝑓, 𝑓^{'}$ exists, and is unique, iff $𝑓 𝑝 \leq 𝑓^{'} 𝑝$ for all $𝑝 \in 𝒫︀$ . Therefore ${𝒬︀}^{𝒫︀}$ is a preorder and there is an arrow $𝜏 : 𝑓 \to 𝑓^{'}$ when $𝑓 \leq 𝑓^{'}$ .

Exercise II.4.5

If $𝐺$ is a finite group, describe Fin𝐺, where Fin is the category of finite sets.

Solution. The objects are all functors $𝑇 : 𝐺 \to$ Fin; because $𝐺$ has a single object $*$ , each object of Fin𝐺 is a finite set $𝑋$ (along with some extra structure).

Therefore Fin𝐺=Fin.

Exercise II.4.6

Let $𝐌$ be the infinite cyclic monoid (with elements $1, 𝑚, 𝑚^{2}, \dots$ ).

Show that, in the functor categories $($ Matr𝐾)2 and $($ Matr𝐾)𝐌, the objects are matrices, and isomorphic objects are exactly equivalent and similar matrices, respectively.

Solution. TODO

Exercise II.4.7

TODO

Exercise II.4.8

TODO

II.5 The category of categories

TODO

Exercise II.5.1

For locally small categories $𝒜︀, ℬ︀, 𝒞︀$ , establish a natural isomorphism

Cat(𝒜︀×ℬ︀,𝒞︀)≅Cat(𝒜︀,𝒞︀ℬ︀).

Solution.

For $𝑇 : 𝒜︀ \times ℬ︀ \to 𝒞︀$ , let $𝜑_{𝒜︀, ℬ︀, 𝒞︀} 𝑇 : 𝒜︀ \to {𝒞︀}^{ℬ︀}$ be defined by

𝑎 \mapsto 𝑆_{𝑎} : ℬ︀ \to 𝒞︀; 𝑓 \mapsto 𝑈_{𝑓} : ℬ︀ \to 𝒞︀,

where we define functors $𝑆_{𝑎}$ and $𝑈_{𝑓}$ by

\begin{matrix} 𝑆_{𝑎} 𝑏 = 𝑇 (𝑎, 𝑏); 𝑆_{𝑎} 𝑔 = 𝑇 (1_{𝑎}, 𝑔); \\ 𝑈_{𝑓} 𝑔 = 𝑇 (𝑓, 𝑔); 𝑈_{𝑓} 𝑏 = 𝑇 (𝑓, 1_{𝑏}) . \end{matrix}

Then given a functor $𝑊 : 𝒜︀ \to {𝒞︀}^{ℬ︀}$ , let $𝜓_{𝒜︀, ℬ︀, 𝒞︀} 𝑊 : 𝒜︀ \times ℬ︀ \to 𝒞︀$ be defined by

(𝑎, 𝑏) \mapsto (𝑊 𝑎) 𝑏; (𝑓, 𝑔) \mapsto (𝑊 𝑓) 𝑔 .

Clearly $𝜑 𝜓 = 𝐼_{𝒜︀ \to {𝒞︀}^{ℬ︀}}$ ; the converse is less obvious but still simple.

\begin{aligned} (𝜓 \circ 𝜑) 𝑇 & = 𝜓 {\begin{cases} 𝑎 \mapsto {\begin{cases} 𝑏 \mapsto 𝑇 (𝑎, 𝑏) \\ 𝑔 \mapsto 𝑇 (1_{𝑎}, 𝑔) \end{cases} \\ 𝑓 \mapsto {\begin{cases} 𝑏 \mapsto 𝑇 (𝑓, 1_{𝑏}) \\ 𝑔 \mapsto 𝑇 (𝑓, 𝑔) \end{cases} \end{cases} \\ = {\begin{cases} (𝑎, 𝑏) \mapsto 𝑇 (𝑎, 𝑏) \\ (𝑓, 𝑔) \mapsto 𝑇 (𝑓, 𝑔) \end{cases} \\ = 𝑇 . \end{aligned}

Hence $𝜓 \circ 𝜑 = 𝐼_{𝒜︀ \times ℬ︀ \to 𝒞︀}$ .

Therefore $𝜓 = 𝜑^{- 1}$ , so $𝜑$ is a bijection.

TODO show naturality

Exercise II.5.2

For categories $𝒜︀, ℬ︀, 𝒞︀$ , establish natural isomorphisms

${(𝒜︀ \times ℬ︀)}^{𝒞︀} ≅ {𝒜︀}^{𝒞︀} \times {ℬ︀}^{𝒞︀}$
${𝒞︀}^{𝒜︀ \times ℬ︀} ≅ {({𝒞︀}^{ℬ︀})}^{𝒜︀}$ .

Solution.

Note that ${(𝒜︀ \times ℬ︀)}^{𝒞︀}, {𝒜︀}^{𝒞︀} \times {(ℬ︀)}^{𝒞︀} : {𝒞︀}^{op} \to$ Cat.
Let $𝜑_{𝒜︀, ℬ︀, 𝒞︀} : {(𝒜︀ \times ℬ︀)}^{𝒞︀} \to {𝒜︀}^{𝒞︀} \times {ℬ︀}^{𝒞︀}$ be defined by
$𝑇 : 𝒞︀ \to 𝒜︀ \times ℬ︀ \mapsto (𝜋_{𝒜︀} \circ 𝑇) \times (𝜋_{ℬ︀} \circ 𝑇),$
and define $𝜓_{𝒜︀, ℬ︀, 𝒞︀} : {𝒜︀}^{𝒞︀} \times {ℬ︀}^{𝒞︀} \to {(𝒜︀ \times ℬ︀)}^{𝒞︀}$ by
$𝑆 \times 𝑈 \mapsto (𝑐 \mapsto (𝑆 𝑐, 𝑈 𝑐))$
for objects and arrows $𝑐$ in $𝒞︀$ .
Clearly(?) $𝜓 = 𝜑^{- 1}$ .
Then in order for $𝜑$ to be natural, we want, for $𝐹 : 𝒜︀ \to {𝒜︀}^{'}, 𝐺 : ℬ︀ \to {ℬ︀}^{'}, 𝐻 : {𝒞︀}^{'} \to 𝒞︀$ ,
to commute.
We have that
$\begin{aligned} ((𝐻^{*} \circ 𝐹_{*}) \times (𝐻^{*} \circ 𝐺_{*})) (𝜑 𝑇) & = ((𝐻^{*} \circ 𝐹_{*}) \times (𝐻^{*} \circ 𝐺_{*})) ((𝜋_{𝒜︀} \circ 𝑇) \times (𝜋_{ℬ︀} \circ 𝑇)) \\ = (𝐻 \circ 𝜋_{𝒜︀} \circ 𝑇 \circ 𝐻) \times (𝐺 \circ 𝜋_{ℬ︀} \circ 𝑇 \circ 𝐻); \\ 𝜑 ((𝐻^{*} \circ (𝐹 \times 𝐺_{*})) 𝑇) & = 𝜑 ((𝐹 \times 𝐺) \circ 𝑇 \circ 𝐻) \\ = (𝜋_{𝒜︀} \circ (𝐹 \times 𝐺) \circ 𝑇 \circ 𝐻) \times (𝜋_{ℬ︀} \circ (𝐹 \times 𝐺) \circ 𝑇 \circ 𝐻) \\ = (𝐹 \circ 𝜋_{𝒜︀} \circ 𝑇 \circ 𝐻) \times (𝐺 \circ 𝜋_{ℬ︀} \circ 𝑇 \circ 𝐻) \end{aligned}$
hence $𝜑$ is natural.
TODO

Exercise II.5.3

TODO

Exercise II.5.4

TODO

Exercise II.5.5

Take $𝑆$ to be a set equipped with binary operations $\cdot, \circ : 𝑆 \times 𝑆 \to 𝑆$ both with unit $𝑒 \in 𝑆$ and satisfying

(𝑎 \cdot 𝑏) \circ (𝑎^{'} \cdot 𝑏^{'}) = (𝑎 \circ 𝑎^{'}) \cdot (𝑏 \circ 𝑏^{'})

for all $𝑎, 𝑎^{'}, 𝑏, 𝑏^{'} \in 𝑆$ .

Show that $\cdot = \circ$ , and that both are commutative.

Solution.

For any $𝑎, 𝑏 \in 𝑆$ ,

\begin{aligned} 𝑎 \circ 𝑏 & = (𝑎 \cdot 𝑒) \circ (𝑒 \cdot 𝑏) \\ = (𝑎 \circ 𝑒) \cdot (𝑒 \circ 𝑏) \\ = 𝑎 \cdot 𝑏, \end{aligned}

hence $\circ = \cdot$ .

Also,

\begin{aligned} 𝑎 \circ 𝑏 & = 𝑎 \cdot 𝑏 \\ = (𝑒 \circ 𝑎) \cdot (𝑏 \circ 𝑒) & = (𝑒 \cdot 𝑏) \circ (𝑎 \cdot 𝑒) \\ = 𝑏 \circ 𝑎, \end{aligned}

therefore $\circ$ (and by equality, $\cdot$ ) is commutative.

Exercise II.5.6

TODO

Exercise II.5.7

If $𝑇 : 𝒜︀ \to 𝒟︀$ is a functor, show that its arrow functions $𝑇_{𝑎, 𝑏} : 𝒜︀ (𝑎, 𝑏) \to 𝒟︀ (𝑇 𝑎, 𝑇 𝑏)$ define a natural transformation between functors ${𝒜︀}^{op} \times 𝒜︀ \to$ Set.

Solution.

Note that $(𝑎, 𝑏) \mapsto 𝑇_{𝑎, 𝑏}$ is a transformation $𝜏 : 𝒜︀ (-, -) \dot{\to} 𝒟︀ (𝑇 -, 𝑇 -)$ .

For $𝜏$ to be natural in both of its arguments, we want that for $𝑎, 𝑏, 𝑎^{'}, 𝑏^{'} \in 𝒜︀$ , $𝑓 : 𝑎 \to 𝑎^{'} \in {𝒜︀}^{op}$ , $𝑔 : 𝑏 \to 𝑏^{'} \in 𝒜︀$ ,

should commute.

For $ℎ : 𝑎 \to 𝑏$ ,

\begin{aligned} (𝒟︀ (𝑇 𝑓, 𝑇 𝑔) \circ 𝜏_{𝑎, 𝑏}) ℎ & = (𝒟︀ (𝑇 𝑓, 𝑇 𝑔) \circ 𝑇_{𝑎, 𝑏}) ℎ \\ = ({(𝑇 𝑓)}_{*} \circ {(𝑇 𝑔)}^{*} \circ 𝑇_{𝑎, 𝑏}) ℎ \\ = ({(𝑇 𝑓)}_{*} \circ {(𝑇 𝑔)}^{*}) (𝑇 ℎ) \\ = (𝑇 𝑓) (𝑇 ℎ) (𝑇 𝑔) \\ = 𝑇 (𝑓 ℎ 𝑔) \\ = 𝑇 ((𝑓_{*} \circ 𝑔^{*}) ℎ) \\ = 𝑇 (𝒜︀ (𝑓, 𝑔) ℎ) \\ = (𝑇_{𝑎, 𝑏} \circ 𝒜︀ (𝑓, 𝑔)) ℎ \\ = (𝜏_{𝑎, 𝑏} \circ 𝒜︀ (𝑓, 𝑔)) ℎ . \end{aligned}

Therefore $𝜏$ defined by $(𝑎, 𝑏) \mapsto 𝑇_{𝑎, 𝑏}$ is a natural transformation.

II.6 Comma categories

Definition II.6.1

For $𝑏 \in 𝒞︀$ , $(𝑏 ↓ 𝒞︀)$ is the category with objects $𝑓 : 𝑏 \to 𝑐$ for each $𝑐 \in 𝒞︀$ , and arrows $ℎ : 𝑓 \to 𝑓^{'}$ , those arrows $ℎ : 𝑐 \to 𝑐^{'} \in 𝒞︀$ where $ℎ \circ 𝑓 = 𝑓^{'}$ .

TODO diagrams

We call this category the category of objects under $𝑏$ .

Remark II.6.2

{(ℎ \circ ℎ^{'})}_{(𝑏 ↓ 𝒞︀)} = {(ℎ \circ ℎ^{'})}_{𝒞︀}

Definition II.6.3

(𝒞︀ ↓ 𝑎)

is the category of objects over

𝑎

, consisting of objects

𝑓 : 𝑐 \to 𝑎

for each

𝑐 \in 𝒞︀

, and arrows

ℎ : 𝑓 \to 𝑓^{'}

for which the corresponding

ℎ : 𝑐 \to 𝑐^{'} \in 𝐶

satisfies

𝑓 = 𝑓^{'} \circ ℎ

Remark II.6.4

𝑡

is terminal in

𝒞︀

, then

(𝒞︀ ↓ 𝑡) ≅ 𝒞︀

(proof in exercise).

Definition II.6.5

In general, for categories $𝒜︀, ℬ︀, 𝒞︀$ and functors $𝑇 : 𝒜︀ \to 𝒞︀, 𝑆 : ℬ︀ \to 𝒞︀$ , the comma category $(𝑇 ↓ 𝑆)$ has objects $𝑓 : 𝑇 𝑎 \to 𝑇 𝑏$ and arrows $⟨ 𝑘, ℎ ⟩ : 𝑓 \to 𝑓^{'}$ those pairs of arrows where $𝑆 ℎ \circ 𝑓 = 𝑓^{'} \circ 𝑇 𝑘$ .

The composite is component-wise.

TODO diagrams

TODO this gets rid of the inclusion of the objects in the definitions of the arrows. Does this matter??

Exercise II.6.1

TODO

Exercise II.6.2

TODO

Exercise II.6.3

Define $𝜋_{ℰ︀}, 𝜋_{𝒟︀}, 𝜋_{{𝒞︀}^{2}}$ on arrows $𝜋_{*}$ s the projections of $(𝑇 ↓ 𝑆)$ for functors $𝑇 : ℰ︀ \to 𝒞︀, 𝑆 : 𝒟︀ \to 𝒞︀$ .

Solution. Define

\begin{aligned} 𝜋_{ℰ︀} ⟨ 𝑘, ℎ ⟩ & = 𝑘; \\ 𝜋_{𝒟︀} ⟨ 𝑘, ℎ ⟩ & = ℎ; \\ 𝜋_{{𝒞︀}^{2}} ⟨ 𝑘, ℎ ⟩ & = ⟨ 𝑇 𝑘, 𝑆 ℎ ⟩ . \end{aligned}

We now show functoriality on $𝜋_{ℰ︀}$ and $𝜋_{{𝒞︀}^{2}}$ ; functoriality of $𝜋_{𝒟︀}$ follows by symmetry.

\begin{aligned} 𝜋_{ℰ︀} ⟨ 1_{𝑒}, 1_{𝑑} ⟩ & = 1_{𝑒} = 1_{𝜋_{ℰ︀} ⟨ 𝑒, 𝑑 ⟩}; \\ 𝜋_{ℰ︀} ⟨ 𝑘 \circ 𝑘^{'}, ℎ \circ ℎ^{'} ⟩ & = 𝑘 \circ 𝑘^{'} = 𝜋_{ℰ︀} ⟨ 𝑘, ℎ ⟩ \circ 𝜋_{ℰ︀} ⟨ 𝑘^{'}, ℎ^{'} ⟩; \\ 𝜋_{{𝒞︀}^{2}} ⟨ 1_{𝑒}, 1_{𝑑} ⟩ & = ⟨ 𝑇 1_{𝑒}, 𝑆 1_{𝑑} ⟩ \\ = ⟨ 1_{𝑇 𝑒}, 1_{𝑆 𝑑} ⟩ \\ = 1_{𝜋_{{𝒞︀}^{2}} ⟨ 𝑒, 𝑑 ⟩}; \\ 𝜋_{{𝒞︀}^{2}} ⟨ 𝑘 \circ 𝑘^{'}, ℎ \circ ℎ^{'} ⟩ & = ⟨ 𝑇 (𝑘 \circ 𝑘^{'}), 𝑆 (ℎ \circ ℎ^{'}) ⟩ \\ = ⟨ 𝑇 𝑘 \circ 𝑇 𝑘^{'}, 𝑆 ℎ \circ 𝑆 ℎ^{'} ⟩ \\ = ⟨ 𝑇 𝑘, 𝑆 ℎ ⟩ \circ ⟨ 𝑇 𝑘^{'}, 𝑆 ℎ^{'} ⟩ \\ = 𝜋_{{𝒞︀}^{2}} ⟨ 𝑘, ℎ ⟩ \circ 𝜋_{{𝒞︀}^{2}} ⟨ 𝑘^{'}, ℎ^{'} ⟩ . \end{aligned}

Exercise II.6.4

Given functors $𝑇, 𝑆 : 𝒟︀ \to 𝒞︀$ , show that a natural transformation $𝜏 : 𝑇 \dot{\to} 𝑆$ is exactly a functor $𝜏 : 𝒟︀ \to (𝑇 ↓ 𝑆)$ such that $𝜋_{𝑇} 𝜏 = 𝜋_{𝑆} 𝜏 = {id}_{𝒟︀}$ , with $𝜋_{𝑇}, 𝜋_{𝑆}$ the projections of $(𝑇 ↓ 𝑆)$ .

Solution.

Given a natural transformation $𝜏 : 𝑇 \dot{\to} 𝑆$ , define $𝐹 : 𝒟︀ \to (𝑇 ↓ 𝑆)$ to be the functor defined by object function $𝑑 \mapsto 𝜏_{𝑑}$ and arrow function $(ℎ : 𝑎 \to 𝑏) \mapsto ⟨ 𝑇 ℎ, 𝑆 ℎ ⟩$ . This satisfies functoriality because, for object $𝑑 \in 𝒟︀$ ,

\begin{aligned} 𝐹 1_{𝑑} & = ⟨ 𝑇 1_{𝑑}, 𝑆 1_{𝑑} ⟩ \\ = ⟨ 1_{𝑇 𝑑}, 1_{𝑆 𝑑} ⟩ \\ = 1_{𝜏_{𝑑}} \\ = 1_{𝐹 𝑑} \end{aligned}

and, for $𝑓 : 𝑎 \to 𝑏, 𝑔 : 𝑏 \to 𝑐 \in 𝒟︀$ ,

\begin{aligned} 𝐹 (𝑔 \circ 𝑓) & = ⟨ 𝑇 (𝑔 \circ 𝑓), 𝑆 (𝑔 \circ 𝑓) ⟩ \\ = ⟨ 𝑇 𝑔 \circ 𝑇 𝑓, 𝑆 𝑔 \circ 𝑆 𝑓 ⟩ \\ = ⟨ 𝑇 𝑔, 𝑆 𝑔 ⟩ \circ ⟨ 𝑇 𝑓, 𝑆 𝑓 ⟩ \\ = 𝐹 𝑔 \circ 𝐹 𝑓 . \end{aligned}

Then we have, for an object $𝑑 \in 𝒟︀$ ,

\begin{aligned} 𝜋_{𝑇} 𝐹 𝑑 & = 𝜋_{𝑇} (𝜏_{𝑑} : 𝑇 𝑑 \to 𝑆 𝑑) = 𝑑; \\ 𝜋_{𝑆} 𝐹 𝑑 & = 𝜋_{𝑆} (𝜏_{𝑑} : 𝑇 𝑑 \to 𝑆 𝑑) = 𝑑; \end{aligned}

and for an arrow $𝑓 : 𝑎 \to 𝑏 \in 𝒟︀$ ,

\begin{aligned} 𝜋_{𝑇} 𝐹 𝑓 & = 𝜋_{𝑇} ⟨ 𝑇 𝑓, 𝑆 𝑓 ⟩ = 𝑓; \\ 𝜋_{𝑆} 𝐹 𝑓 & = 𝜋_{𝑆} ⟨ 𝑇 𝑓, 𝑆 𝑓 ⟩ = 𝑓 . \end{aligned}

Therefore $𝜋_{𝑇} 𝐹 = 𝜋_{𝑆} 𝐹 = {id}_{𝒟︀}$ .

Conversely, suppose we have a functor $𝜏 : 𝒟︀ \to (𝑇 ↓ 𝑆)$ with $𝜋_{𝑇} 𝜏 = 𝜋_{𝑆} 𝜏 = {id}_{𝒟︀}$ . Then given an object $𝑑 \in 𝒟︀$ , $𝜏 𝑑$ is an arrow $𝑇 𝑑 \to 𝑆 𝑑$ . Moreover, given $𝑓 : 𝑑 \to 𝑑^{'} \in 𝒟︀$ ,

𝜏 𝑓 : 𝜏 𝑑 \to 𝜏 𝑑^{'} = ⟨ 𝑓, 𝑓 ⟩;

by the definition of the comma category, this satisfies $𝑆 𝑓 \circ 𝜏 𝑑 = 𝜏 𝑑^{'} \circ 𝑇 𝑓$ , which is precisely the requirement for $𝜏$ to be natural, so $𝜏$ is a natural transformation $𝑇 \dot{\to} 𝑆$ .

Exercise II.6.5

Given any commutative diagram of categories and functors,

show that there is a unique functor $𝐿 : 𝒳︀ \to (𝑇 ↓ 𝑆)$ such that $𝑃_{ℰ︀} = 𝜋_{ℰ︀} 𝐿$ , $𝑃_{𝒟︀} = 𝜋_{𝒟︀} 𝐿$ , and $𝑃_{{𝒞︀}^{2}} = 𝜋_{{𝒞︀}^{2}} 𝐿$ , for $𝜋_{*}$ the projection functors of the comma category $(𝑇 ↓ 𝑆)$ . TODO define what $𝑑_{0}, 𝑑_{1}$ are.

Solution. Define $𝐿$ by

\begin{aligned} 𝑥 & \mapsto \end{aligned}

(𝑓:𝑥→𝑥′)↦=⟨𝑃ℰ︀𝑓,𝑃𝒟︀𝑓⟩.

Then for object $𝑥 \in 𝒳︀$ ,

𝜋_{ℰ︀} 𝐿 𝑥 = 𝜋_{ℰ︀} (

)=𝑃ℰ︀𝑥,

and for arrow $𝑓 : 𝑥 \to 𝑥^{'} \in 𝒳︀$ ,

𝜋_{ℰ︀} 𝐿 𝑓 = 𝜋_{ℰ︀} ⟨ 𝑃_{ℰ︀} 𝑓, 𝑃_{𝒟︀} 𝑓 ⟩ = 𝑃_{ℰ︀} 𝑓 .

Hence $𝜋_{ℰ︀} 𝐿 = 𝑃_{ℰ︀}$ , and by symmetry $𝜋_{𝒟︀} 𝐿 = 𝑃_{𝒟︀}$ .

Moreover,

\begin{aligned} 𝜋_{{𝒞︀}^{2}} 𝐿 𝑥 & = 𝜋_{{𝒞︀}^{2}} ( \end{aligned}

)=𝑃𝒞︀2𝑥;𝜋𝒞︀2𝐿𝑓=𝜋𝒞︀2⟨𝑃ℰ︀𝑓,𝑃𝒟︀𝑓⟩=⟨𝑇𝑃ℰ︀𝑓,𝑆𝑃𝒟︀𝑓⟩=𝑃𝒞︀2𝑓.

Therefore $𝑃_{{𝒞︀}^{2}} = 𝜋_{{𝒞︀}^{2}} 𝐿$ .

We now show that $𝐿$ is the unique functor satisfying this property.

Suppose that there exists a functor $𝐿^{'} : 𝒞︀ \to (𝑇 ↓ 𝑆) \neq 𝐿$ satisfying $𝑃_{*} = 𝜋_{*} 𝐿$ for $* = ℰ︀, 𝒟︀, {𝒞︀}^{2}$ .

Then either $\exists 𝑥 \in 𝒳︀$ with $𝐿^{'} 𝑥 \neq 𝐿 𝑥$ , or $\exists 𝑓 \in 𝒳︀$ with $𝐿^{'} 𝑓 \neq 𝐿 𝑓$ .

Suppose the former. Then either $𝜋_{ℰ︀} 𝐿^{'} 𝑥 \neq 𝜋_{ℰ︀} 𝐿 𝑥$ , or $𝜋_{𝒟︀} 𝐿^{'} 𝑥 \neq 𝜋_{𝒟︀} 𝐿 𝑥$ , or $𝜋_{{𝒞︀}^{2}} 𝐿^{'} 𝑥 \neq 𝜋_{{𝒞︀}^{2}} 𝐿 𝑥$ , as the three projections uniquely define each object of $(𝑇 ↓ 𝑆)$ . This contradicts $𝐿^{'}$ satisfying the relevant conditions, so it must be that there is an arrow $𝑓$ with $𝐿^{'} 𝑓 \neq 𝐿 𝑓$ , but we encounter the same contradictions. Therefore no other satisfying functor exists, so $𝐿$ is unique.

Exercise II.6.6

TODO

Exercise II.6.7

For $𝑡$ terminal in $𝒞︀$ , show that $(𝒞︀ ↓ 𝑡) ≅ 𝒞︀$ .

Solution. Define $𝑇 : 𝒞︀ \to (𝒞︀ ↓ 𝑡)$ by $𝑇 𝑐 = 𝑓 : 𝑐 \to 𝑡$ (well-defined because $𝑡$ terminal), and $𝑇 𝑓 = 𝑓$ .

For $ℎ : 𝑐 \to 𝑡, ℎ^{'} : 𝑐^{'} \to 𝑡, 𝑓 : 𝑐 \to 𝑐^{'}$ , we must have $ℎ = ℎ^{'} \circ 𝑓$ , otherwise there would be two distinct arrows $𝑐 \to 𝑡$ , which would contract the terminality of $𝑡$ .

Define $𝑆 : (𝒞︀ ↓ 𝑡) \to 𝒞︀$ by $𝑆 (𝑓 : 𝑐 \to 𝑡) = 𝑐$ , $𝑆 ℎ = ℎ$ . Clealy $𝑆 𝑇 ≅ 𝐼_{𝒞︀}$ and $𝑇 𝑆 ≅ 𝐼_{(𝒞︀ ↓ 𝑡)}$ , so $𝒞︀ ≅ (𝒞︀ ↓ 𝑡)$ .

II.7 Free categories

TODO

II.8 Quotient categories

TODO

III Universals & limits

III.1 Universal arrows

Definition III.1.1

For $𝑆 : 𝒟︀ \to 𝒞︀$ a functor, and $𝑐 \in 𝒞︀$ , a universal arrow from $𝑐$ to $𝑆$ is a pair $⟨ 𝑟, 𝑢 ⟩$ with $𝑟 \in 𝒟︀, 𝑢 : 𝑐 \to 𝑆 𝑟 \in 𝒞︀$ , s.t. for every $𝑑 \in 𝒟︀$ , $𝑓 : 𝑐 \to 𝑆 𝑑 \in 𝒞︀$ , there is a unique arrow $𝑓^{'} : 𝑟 \to 𝑑 \in 𝒟︀$ with $𝑆 𝑓^{'} \circ 𝑢 = 𝑓$ .

That is, for each $𝑑 \in 𝒟︀, 𝑓 : 𝑐 \to 𝑆 𝑑 \in 𝒟︀$ ,

commutes for a unique $𝑓^{'}$ .

Remark III.1.2

An arrow

𝑢 : 𝑐 \to 𝑆 𝑟

is universal if and only if

⟨ 𝑟, 𝑢 ⟩

is initial in

(𝑐 ↓ 𝑆)

Remark III.1.3

It follows that

⟨ 𝑟, 𝑢 ⟩

is unique up to isomorphism in

(𝑐 ↓ 𝑆)

; in particular,

𝑟

is unique up to isomorphism in

𝒟︀

Definition III.1.4

For category

𝒟︀

and functor

𝐻 : 𝒟︀ \to

Set, a universal element of

𝐻

is a pair

⟨ 𝑟, 𝑒 ⟩

with

𝑟 \in 𝒟︀

and

𝑒 \in 𝐻 𝑟

such that, for every

𝑑 \in 𝒟︀, 𝑥 \in 𝐻 𝑑

, there is a unique

𝑓 : 𝑟 \to 𝑑 \in 𝒟︀

with

(𝐻 𝑓) 𝑒 = 𝑥

Remark III.1.5

A universal element is a universal arrow

𝑒 : * \to 𝐻 𝑟

in Ens, where

*

is a singleton set.

Remark III.1.6

For a locally small category

𝒞︀

, a universal arrow

⟨ 𝑟, 𝑢 : 𝑐 \to 𝑆 𝑟 ⟩

from

𝑐 \in 𝒞︀

𝑆 : 𝒟︀ \to 𝒞︀

is exactly a universal element

⟨ 𝑟, 𝑢 ⟩

of the functor

𝒞︀ (𝑐, 𝑆 -)

Theorem III.1.7

Let $𝑁$ be a normal subgroup of a group $𝐺$ and consider the usual projection $𝜋 : 𝐺 \to 𝐺 / 𝑁$ that sends each $𝑔 \in 𝐺$ to its coset in $𝐺 / 𝑁$ $𝜋 𝑔 = 𝑔 𝑁$ .

Let $𝐻 :$ Grp→Set be the functor defined by

𝐺^{'} \mapsto {𝜑 : 𝐺 \to 𝐺^{'} | 𝜑 𝑁 = 𝑒_{𝐺}};

that is, the functor that assigns to each group $𝐺^{'}$ the set of group homomorphisms that kill $𝑁$ .

Then $𝜑$ is a universal element of $𝐻$ .

Exercise III.1.1

TODO

Exercise III.1.2

Find a universal element for the contravariant power set functor $𝒫︀ :$ Setop→Set.

Solution. We want a pair $⟨ 𝑋 \in$ Setop,𝑆⊆𝑋⟩, such that for every $𝑌, 𝑇 \subseteq 𝑌$ there is a unique function $𝑓 : 𝑌 \to 𝑋$ with $(𝒫︀ 𝑓) 𝑆 = 𝑇$ . By the definition of $𝒫︀$ on functors, this is equivalent to $𝑓^{- 1} 𝑆 = 𝑇$ .

For this $𝑓$ to be uniquely determined by $𝑓^{- 1} 𝑆 = 𝑇$ for every $𝑇 \subseteq 𝑌$ , we must have that $𝑓$ is defined for every $𝑡 \in 𝑇$ by $𝑓 𝑡 = 𝑒$ for the same arbitrary $𝑒 \in 𝑋$ and $𝑆 = {𝑒}$ , and for every $𝑥 \in 𝑋 \ 𝑇$ , $𝑓 𝑥 = 𝑓$ for $𝑓 \neq 𝑒$ , and $𝑋 = {𝑒, 𝑓}$ . If $𝑋$ contained more elements, $𝑓$ wouldn’t be unique.

Then $𝑋 = {𝑒, 𝑓}, 𝑆 = {𝑒}$ .

This is unique up to isomorphism as required.

Exercise III.1.3

TODO

Exercise III.1.4

Use only universality (of projections) to prove the following isomorphisms of group theory:

For normal subgroups $𝑀, 𝑁$ of $𝐺$ with $𝑀 ⊲ 𝑁$ , $(𝐺 / 𝑀) / (𝑁 / 𝑀) ≅ 𝐺 / 𝑀$ ;
For subgroups $𝑆$ and $𝑁$ of $𝐺$ , $𝑁$ normal, with join $𝑆 𝑁$ , $𝑆 𝑁 / 𝑁 ≅ 𝑆 / 𝑆 \cap 𝑁$ .

Solution.

TODO