A category is a collection of morphisms between objects with the concepts of identity and composition.

# 1 Category

A category $$\cC = (\Obj, \Hom, \compL, \id)$$ consists of

• a collection of objects $$\Obj$$
• a collection of morphisms $$\Hom(A, B)$$ between objects
• a composition function $$\compL: \Hom(B, C) \times \Hom(A, B) \to \Hom(A, C)$$
• an identity morphism $$\id_A \in \Hom(A, A)$$ for each object

subject to

• associativity: $$(h \compL g) \compL f = h \compL (g \compL f)$$
• identity: $$\id_B \compL f = f = f \compL \id_A$$
-- function composition
(.) :: (b -> c) -> (a -> b) -> (a -> c)

## 1.1 Isomorphism

An inverse of a morphism $$f: A \to B$$ is a morphism $$f\inv: B \to A$$ such that $$f\inv \compL f = \id_A$$ and $$f \compL f\inv = \id_B$$.

$$A$$ and $$B$$ are isomorphic, denoted by $$A \iso B$$.

• Skeletal category: isomorphic objects are equal
• Groupoid: all morphisms are isomorphisms

## 1.2 Size

• Thin: $$\Hom(A, B)$$ contains at most one morphism
• Finite: $$\Obj$$ is a finite set and $$\Hom(A, B)$$ is a finite set
• Small: $$\Obj$$ is a set and $$\Hom(A, B)$$ is a set
• Locally small: $$\Hom(A, B)$$ is a set
• Large: otherwise

## 1.3 Construction

• Opposite category $$\cC\op$$: the same objects and reversed morphisms
• Product category $$\cC \times \cD$$: ordered pairs of objects and morphisms

## 1.4 Examples

$2:= \set{\varnothing, \singleton} \iso \set{\lfal, \ltru}$

### 1.4.1 Monoid

A monoid $$(M, \otimes, e)$$ (a set with a unital and associative binary operation) is a single-object category, where $$\Hom(*, *) = M$$.

• $$(\Hom(X, X), \compL, \id_X)$$ endomorphism monoid
• $$(LX, \concat, [])$$ free monoid
• $$(2, \lcon, \ltru)$$, $$(2, \leqv, \ltru)$$
• $$(2, \ldis, \lfal)$$, $$(2, \lneqv, \lfal)$$
• $$(\N, +, 0)$$
• $$(\N, \times, 1)$$
• $$(PX, \cap, X)$$
• $$(PX, \cup, \varnothing)$$

### 1.4.2 Poset

A preordered set (proset) $$(A, \leq)$$ (a set with a reflexive and transitive binary relation) is a thin category, where $$\Hom(a, b) \in 2$$.

A partially ordered set (poset) is a skeleton of a proset.

• $$(PA, \subseteq)$$
• $$(\N, \leq)$$
• $$(\N, \mid)$$

Any poset $$(A, \leq)$$ is isomorphic to an inclusion order $$(\set{A_{\leq c}}_{c \in A}, \subseteq)$$ where $$A_{\leq c} := \set{a \in A \mid a \leq c}$$.

$a \leq b \leqv A_{\leq a} \subseteq A_{\leq b}$

### 1.4.3 Finite category

• Empty/initial category $$\cZero$$: no objects
• Trivial/terminal category $$\cOne$$: one object $$*$$ and one morphism $$\id_*$$
• Interval category $$\cTwo$$: two objects and one non-identity morphism

### 1.4.4 Concrete category

• $$\cSet$$: sets and functions
• $$\cRel$$: sets and relations
• $$\cPos$$: posets and monotones
• $$\cMon$$: monoids and monoid homomorphisms
• $$\cGrp$$: groups and group homomorphisms
• $$\cAb$$: abelian groups and group homomorphisms
• $$\cVect$$: vector spaces and linear functions
• $$\cMet$$: metric spaces and metric maps

# 2 Functor

For categories $$\cC$$ and $$\cD$$, a functor $$F: \cC \to \cD$$ is a mapping, which sends

• $$\cC$$-objects to $$\cD$$-objects

\begin{aligned} F: \Obj_\cC & \to \Obj_\cD \\ A & \mapsto FA \end{aligned}

• $$\cC$$-morphisms to $$\cD$$-morphisms

\begin{aligned} F_{A, B}: \Hom_\cC(A, B) & \to \Hom_\cD(FA, FB) \\ (A \xto{f} B) & \mapsto (FA \xto{Ff} FB) \end{aligned}

in such a way that $$F$$ preserves

• composition: $$F(g \compL_\cC f) = Fg \compL_\cD Ff$$
• identity: $$F\id_{\cC: A} = \id_{\cD: FA}$$
-- application operator
($) :: (a -> b) -> a -> b -- fmap (<$>) :: Functor f => (a -> b) -> f a -> f b
(<$) :: Functor f => a -> f b -> f a (<$) = fmap . const
($>) :: Functor f => f a -> b -> f b ($>) = flip (<\$)

## 2.1 Composition

For $$\cA \xto{F} \cB \xto{G} \cC$$:

\begin{aligned} \begin{array}{cccc} GF: & \cA & \to & \cC \\ & A & \mapsto & G(FA) \\ & f & \mapsto & G(Ff) \end{array} \end{aligned}

The identity functor $$\id_\cC: \cC \to \cC$$ sends each object and morphism to itself.

$$\cCat$$: category of small categories and functors

## 2.2 Isomorphism

A functor between groupoids preserves the inverse:

$Ff\inv \compL_\cD Ff = F(f\inv \compL_\cC f) = F\id_{\cC:A} = \id_{\cD:FA}$

$Ff \compL_\cD Ff\inv = F(f \compL_\cC f\inv) = F\id_{\cC:B} = \id_{\cD:FB}$

An inverse of a functor $$F: \cC \to \cD$$ is a functor $$F\inv: \cD \to \cC$$ such that $$\id_\cC = GF$$ and $$FG = \id_\cD$$.

## 2.3 Construction

• Covariant functor from $$\cC$$ to $$\cD$$: $$\cC \to \cD$$
• Contravariant functor from $$\cC$$ to $$\cD$$: $$\cC\op \to \cD$$
• Presheaf on $$\cC$$: $$\cC\op \to \cSet$$
• Bifunctor from $$\cC$$ and $$\cD$$ to $$\cE$$: $$\cC \times \cD \to \cE$$
• Profunctor from $$\cC$$ to $$\cD$$: $$\cD\op \times \cC \to \cSet$$

## 2.4 Properties

• Faithful: $$\Hom_\cC(A, B) \to \Hom_\cD(FA, FB)$$ is injective
• Full: $$\Hom_\cC(A, B) \to \Hom_\cD(FA, FB)$$ is surjective
• Injective-on-objects: $$\Obj_\cC \to \Obj_\cD$$ is injective
• Surjective-on-objects: $$\Obj_\cC \to \Obj_\cD$$ is surjective
• Bijective-on-objects: $$\Obj_\cC \to \Obj_\cD$$ is bijective
• Essentially surjective: $$\Obj_\cC \to \Obj_\cD$$ is surjective up to isomorphism

Forgetful functor:

1. a fully faithful and essentially surjective functor forgets nothing.
2. a fully faithful functor forgets only properties.
3. a faithful functor forgets at most structure.
4. a functor may forget everything.

## 2.5 Subcategory

Given a category $$\cC$$, a subcategory $$\cS$$ is a category consisting of subcollections of $$\cC$$-objects and $$\cC$$-morphisms with the same identity morphisms and composition.

The inclusion functor $$I: \cS \incl \cC$$ sends objects and morphisms to themselves.

• Full subcategory: the inclusion functor is full
• Wide subcategory: the inclusion functor is bijective-on-objects

# 3 Natural transformation

For functors $$F, G: \cC \to \cD$$, a natural transformation $$\alpha: F \nat G$$ is a collection of $$\cD$$-morphisms indexed by $$\cC$$-objects $$\alpha_A: FA \to GA$$ that satisfies

• naturality: $$\alpha_B \compL Ff = Gf \compL \alpha_A$$

## 3.1 Composition

### 3.1.1 Vertical composition

$F, G, H: \cC \to \cD$

$\beta \compL \alpha : F \xnat{\alpha} G \xnat{\beta} H$

$(\beta \compL \alpha)_A := \beta_A \compL_\cD \alpha_A$

The identity natural transformation $$\id_F: F \nat F$$ sends each $$\cC$$-object $$A$$ to the identity $$\cD$$-morphism $$\id_{FA}$$.

Functor category $$[\cC, \cD]$$ or $$\cD^\cC$$: category of functors from $$\cC$$ to $$\cD$$ and natural transformations

### 3.1.2 Horizontal composition

\begin{aligned} \begin{array}{ccccc} [\cB, \cC] & \times & [\cA, \cB] & \to & [\cA, \cC] \\ G && F & \mapsto & GF \\ \beta: G_1 \nat G_2 && \alpha: F_1 \nat F_2 & \mapsto & \beta\alpha: G_1F_1 \nat G_2F_2 \end{array} \end{aligned}

$(\beta\alpha)_A := \beta_{F_2 A} \compL_\cC G_1 \alpha_A = G_2 \alpha_A \compL_\cC \beta_{F_1 A}$

### 3.1.3 Whiskering

$G \alpha: GF_1 \nat GF_2 := \id_G \alpha$

$(G \alpha)_A := G \alpha_A$

$\beta F: G_1F \nat G_2F := \beta \id_F$

$(\beta F)_A := \beta_{FA}$

$\beta\alpha = \beta F_2 \compL G_1 \alpha = G_2 \alpha \compL \beta F_1$

## 3.2 Isomorphism

A natural isomorphism $$\alpha: F \nat G$$ is a natural transformation whose components $$\alpha_A: FA \to GA$$ are isomorphisms.

$$F$$ and $$G$$ are naturally isomorphic, denoted by $$F \iso G$$.

A natural isomorphism is an isomorphism in the functor category $$[\cC, \cD]$$.

An equivalence between categories $$\cC$$ and $$\cD$$ consists of a pair of functors $$F: \cC \toot \cD: G$$ such that $$\id_\cC \iso GF$$ and $$FG \iso \id_\cD$$.

A fully faithful and essentially surjective functor realizes an equivalence of categories.

# 4 Construction

## 4.1 Comma category

Comma category $$(F: \cA \to \cC) \comma (G: \cB \to \cC)$$

• objects are triplets $$(\cA\text{-object } A, \cB\text{-object } B, \cC\text{-morphism } h: FA \to GB)$$
• morphisms are pairs $$(\cA\text{-morphism } f: A_1 \to A_2, \cB\text{-morphism } g: B_1 \to B_2)$$ such that $$h_2 \compL Ff = Gg \compL h_1$$

For functors $$F, G: \cC \to \cD$$, a natural transformation $$\alpha: F \nat G$$ is isomorphic to a functor to the comma category:

\begin{aligned} \alpha: \cC & \to F \comma G \\ A & \mapsto (A, A, \alpha_A) \\ f & \mapsto (f, f) \end{aligned}

### 4.1.1 Arrow category

$$\cArr(\cC) \iso (\id_\cC: \cC \to \cC) \comma (\id_\cC: \cC \to \cC) \iso [\cTwo, \cC]$$

• objects are morphisms: $$h: A \to B$$
• morphisms are commutative squares: $$(f: A_1 \to A_2, g: B_1 \to B_2): h_1 \to h_2$$ such that $$h_2 \compL f = g \compL h_1$$

### 4.1.2 Slice category

$$\cC \comma C \iso (\id_\cC: \cC \to \cC) \comma (C: \cOne \to \cC)$$

• objects are morphisms to $$C$$: $$h: A \to C$$
• morphisms are commutative triangles: $$(f: A_1 \to A_2): h_1 \to h_2$$ such that $$h_2 \compL f = h_1$$

A morphism $$f: A \to B$$ induces a postcomposition functor $$f_!: \cC \comma A \to \cC \comma B$$ between slice categories:

\begin{aligned} \begin{array}{cccc} f_!: & \cC \comma A & \to & \cC \comma B \\ & C \xto{o} A & \mapsto & C \xto{f \compL o} B \\ & C_1 \xto{m} C_2 & \mapsto & C_1 \xto{m} C_2 \end{array} \end{aligned}

For a monoid $$\cM: (*, M)$$, the Green’s preorder $$\leq_R$$ is the slice category $$\cM \comma *: (M, a \xto{c: a = b \compL c} b)$$.

### 4.1.3 Coslice category

$$C \comma \cC \iso (C: \cOne \to \cC) \comma (\id_\cC: \cC \to \cC)$$

• objects are morphisms from $$C$$: $$h: C \to B$$
• morphisms are commutative triangles: $$(g: B_1 \to B_2): h_1 \to h_2$$ such that $$h_2 = g \compL h_1$$

## 4.2 Functor category

$\cA \xto{F} \cB \xto{G} \cC \xto{H} \cD$

A functor $$H: \cC \to \cD$$ induces a postcomposition functor $$H^\cB: \cC^\cB \to \cD^\cB$$ between functor categories:

\begin{aligned} \begin{array}{cccc} H^\cB: & \cC^\cB & \to & \cD^\cB \\ & G & \mapsto & HG \\ & G_1 \xnat{\beta} G_2 & \mapsto & H G_1 \xnat{H \beta} H G_2 \end{array} \end{aligned}

A functor $$F: \cA \to \cB$$ induces a precomposition functor $$\cC^F: \cC^\cB \to \cC^\cA$$ between functor categories:

\begin{aligned} \begin{array}{cccc} \cC^F: & \cC^\cB & \to & \cC^\cA \\ & G & \mapsto & GF \\ & G_1 \xnat{\beta} G_2 & \mapsto & G_1 F \xnat{\beta F} G_2 F \end{array} \end{aligned}

A constant functor $$\Delta C: \cD \to \cC$$ sends all $$\cD$$-objects to $$C$$ and all $$\cD$$-morphisms to $$\id_C$$.

A diagonal functor $$\Delta: \cC \to \cC^\cD$$ is isomorphic to a precomposition functor induced by the unique functor $$\cD \to \cOne$$:

\begin{aligned} \begin{array}{cccc} \Delta: & \cC & \to & \cC^\cD \\ & C & \mapsto & \Delta C \\ & A \xto{f} B & \mapsto & \Delta A \xnat{\Delta f} \Delta B \end{array} \end{aligned}

Binary diagonal functor $$\Delta_\cTwo: \cC \to \cC \times \cC$$:

\begin{aligned} \begin{array}{cccc} \Delta_\cTwo: & \cC & \to & \cC \times \cC \\ & C & \mapsto & (C, C) \\ & A \xto{f} B & \mapsto & (A, A) \xto{(f, f)} (B, B) \end{array} \end{aligned}

## 4.3 Hom-functor

$A \xto{f} B \xto{g} C \xto{h} D$

The hom-functor $$\Hom: \cC\op \times \cC \to \cSet$$ is an endoprofunctor:

\begin{aligned} \begin{array}{cccccc} \Hom: & \cC\op & \times & \cC & \to & \cSet \\ & A && B & \mapsto & \Hom(A, B) \\ & B \xto{f\op} A && C \xto{h} D & \mapsto & \Hom(B, C) \xto{h \compL (-) \compL f} \Hom(A, D) \end{array} \end{aligned}

The postcomposition $$\Hom(B, -): \cC \to \cSet$$ is a covariant functor:

\begin{aligned} \begin{array}{cccc} \Hom(B, -): & \cC & \to & \cSet \\ & C & \mapsto & \Hom(B, C) \\ & C \xto{h} D & \mapsto & \Hom(B, C) \xto{h \compL (-)} \Hom(B, D) \end{array} \end{aligned}

The precomposition $$\Hom(-, C): \cC\op \to \cSet$$ is a presheaf:

\begin{aligned} \begin{array}{cccc} \Hom(-, C): & \cC\op & \to & \cSet \\ & B & \mapsto & \Hom(B, C) \\ & B \xto{f\op} A & \mapsto & \Hom(B, C) \xto{(-) \compL f} \Hom(A, C) \end{array} \end{aligned}

A representable functor is a presheaf naturally isomorphic to a hom-functor $$\Hom(-, C): \cC\op \to \cSet$$.

### 4.3.1 Naturality

\begin{aligned} \Hom(f, -) &: \Hom(B, -) \nat \Hom(A, -) \\ \Hom(-, h) &: \Hom(-, C) \nat \Hom(-, D) \end{aligned}

A functor on morphisms $$F_{B, C}: \Hom(B, C) \to \Hom(FB, FC)$$ is natural in the domain $$B$$ and codomain $$C$$.

### 4.3.2 Yoneda lemma

The Yoneda embedding:

\begin{aligned} \begin{array}{cccc} Y: & \cC & \to & [\cC\op, \cSet] \\ & C & \mapsto & \Hom(-, C) \\ & A \xto{f} B & \mapsto & \Hom(-, A) \xto{\Hom(-, f)} \Hom(-, B) \end{array} \end{aligned}

The Yoneda embedding is full and faithful.

\begin{aligned} \begin{array}{ccc} \Hom_\cCat(\cC\op \times \cC, \cSet) & \iso & \Hom_\cCat(\cC, [\cC\op, \cSet]) \\ \Hom & \leqv & Y \end{array} \end{aligned}

Hom functor

\begin{aligned} \begin{array}{cccc} \Hom_{(X, \leq)}(-, c): & (X, \leq)\op & \to & \cSet \\ & a & \mapsto & [a \leq c] \\ & b \geq a & \mapsto & [b \leq c] \limp [a \leq c] \end{array} \end{aligned}

Yoneda embedding

\begin{aligned} \begin{array}{cccc} Y_{(X, \leq)}: & (X, \leq) & \to & [(X, \leq)\op, \cSet] \\ & c & \mapsto & X_{\leq c} \\ & a \leq b & \mapsto & X_{\leq a} \subseteq X_{\leq b} \end{array} \end{aligned}