1. Categories

1.1Introduction

This brief introduction is taken from Awodey’s book.

What is category theory? As a first approximation, one could say that category theory is the mathematical study of (abstract) algebras of functions.

The historical development of the subject has been, very roughly, as follows:

•	1945: Eilenberg and Mac Lane’s “General theory of natural equivalences” was the original paper, in which the theory was first formulated.
•	Late 1940s: The main applications were originally in the fields of algebraic topology, particularly homology theory, and abstract algebra.
•	1950s: Grothendieck et al. began using category theory with great success in algebraic geometry.
•	1960s: Lawvere and others began applying categories to logic, revealing some deep and surprising connections.
•	1970s: Applications were already appearing in computer science, linguistics, cognitive science, philosophy, and many other areas.

One very striking thing about the field is that it has such wide-ranging applications. In fact, it turns out to be a kind of universal mathematical language like Set Theory. As a result of these various applications, category theory also tends to reveal certain connections between different fields like Logic and Geometry.

In fact, just as the idea of a topological space arose in connection with continuous functions, so also the notion of a category arose in order to define that of a functor, at least according to one of the inventors. The notion of a functor arose - so the story goes on - in order to define natural transformations. One might as well continue that natural transformations serve to define adjoints, so we have the following succession:$$\text{category}⇝\text{functor}⇝\text{natural transformation}⇝\text{adjunction.}$$

Before getting down to business, let us ask why it should be that category theory has such far-reaching applications. Well, we said that it is the abstract theory of functions, so the answer is simply this:$$\text{Functions are everywhere!}$$

And everywhere that functions are, there are categories. Indeed, the subject might better have been called abstract function theory, or, perhaps even better: archery.

1.2Definition

定义 1.2.1. A category $\mathcal{C}$ consists of the following data:

(1)	objects: $A,B,C,\dots$ (not necessarily sets). The class of objects of $\mathcal{C}$ is denoted by $\mathrm{Ob}(\mathcal{C})$.
(2)	arrows (or morphisms): $f,g,h,\dots$ (not necessarily functions). The class of arrows of $\mathcal{C}$ is denoted by $\mathrm{Mor}(\mathcal{C})$. The class of arrows between two objects $A,B$ of $\mathcal{C}$ is denoted by ${\mathrm{Hom}}_{\mathcal{C}}(A,B)$ or ${\mathrm{Mor}}_{\mathcal{C}}(A,B)$.
(3)	For every arrow $f$ there are objects $\mathrm{dom}(f)$ and $\mathrm{cod}(f)$ called the domain and the codomain of $f$ respectively. We write $f:A\to B$, where $A=\mathrm{dom}(f)$ and $B=\mathrm{cod}(f)$.
(4)	For every arrows $f:A\to B$ and $g:B\to C$ there is an arrow denoted $g\circ f:A\to C$ and called the composite of $f$ and $g$.
(5)	For every object $A$ there is an arrow denoted $1_A:A\to A$ and called the identity arrow.

which satisfy the following axioms:

(i)	Associativity:$$(h\circ g)\circ f=h\circ (g\circ f),\forall f:A\to B,g:B\to C,h:C\to D$$
(ii)	Unit:$$f\circ 1_A=f=1_B\circ f,\forall f:A\to B$$

If $A,B$ are objects and $f:A\to B$ is an arrow in a category $\mathcal{C}$, then sometimes we simply denote $A,B\in \mathcal{C}$ and $f\in \mathcal{C}$ instead of $A,B\in \mathrm{Ob}(\mathcal{C})$ and $f\in {\mathrm{Hom}}_{\mathcal{C}}(A,B)$.

1.3Examples

The Category $\mathbf{Set}$

•	objects: sets
•	arrows: functions
•	composition: composition of functions
•	identity arrow: identity function

There are variations of this category obtained by restricting the sets and/or the functions, such as: the category ${\mathbf{Set}}_{fin}$ of finite sets and functions, the category of sets and injective functions etc.

Categories of Structured Sets

(1)	The category of groups and group homomorphisms, denoted by $\mathbf{Grp}$. The category of abelian groups and group homomorphisms, denoted by $\mathbf{Ab}$.
(2)	The category of monoids and monoid homomorphisms, denoted by $\mathbf{Mon}$.
(3)	The category of unitary rings and unitary ring homomorphisms, denoted by $\mathbf{Ring}$. The category of commutative unitary rings and unitary ring homomorphisms, denoted by $\mathbf{CRing}$.
(4)	The category of rings and ring homomorphisms, denoted by $\mathbf{Rng}$. The category of commutative rings and ring homomorphisms, denoted by $\mathbf{CRng}$.
(5)	The category of fields and field homomorphisms, denoted by $\mathbf{Field}$.
(6)	The category of left vector spaces over a field $K$ and $K$-linear maps, denoted by $\mathbf{Vect}(K)$. The category of left modules over a unitary ring $R$ and $R$-module homomorphisms, denoted by $\mathbf{Mod}(R)$.
(7)	The category of graphs and graph homomorphisms, denoted by $\mathbf{Graph}$.
(8)	The category of topological spaces and continuous maps, denoted by $\mathbf{Top}$.
(9)	The category of real Banach spaces and linear contractions, denoted by $\mathbf{Ban}$.
(10)	The category of differentiable (smooth) manifolds and differentiable (smooth) mappings, denoted by $\mathbf{Man}$.
(11)	The category of preordered sets and monotone mappings, denoted by $\mathbf{Preord}$. The category of posets (partially ordered sets) and monotone mappings, denoted by $\mathbf{Pos}$.

注 1.3.1. All the above examples are concrete categories, which roughly speaking means that the objects are some sets and the arrows are some functions.

The Category $\mathbf{Rel}$

•	objects: sets
•	arrows: relations $r=(A,B,R)$, where $R\subseteq A\times B$
•	composition: composition of relations, defined for relations $r=(A,B,R)$ and $s=(B,C,S)$ as $s\circ r=(A,C,S\circ R)$, where $$S\circ R=\{(a,c)\in A\times C\mid \exists b\in B\text{such that}(a,b)\in Rand(b,c)\in S\}$$
•	identity arrow: for every set $A$, the identity arrow is the equality relation ${\delta }_A=\left(A,A,{\Delta }_A\right)$, where ${\Delta }_A=\{(a,a)\mid a\in A\}$.

Another Category of Finite Sets: $\mathbf{Mat}(K)$

•	Objects: finite sets (or simply natural numbers)
•	arrows: for every finite sets $A$ with $|A|=m\in \mathbb{N}$ and $B$ with $|B|=n\in \mathbb{N}$, define an arrow $A\to B$ to be a matrix in $M_{m,n}(K)$ (where $K$ is a fixed field).
•	composition: multiplication of matrices
•	identity arrow: identity matrix

Poset Categories

Given a poset $(P,⩽)$, we may construct an associated category called a poset category:

•	Objects: the elements of $P$
•	arrows: we say that there is an arrow between $a,b\in P$, and we write $a\to b$, if and only if $a⩽b$.
•	composition: composition of arrows in the sense that $a\to b\to c$ if and only if $a⩽b⩽c$
•	identity arrow: we have $a\to a$ for every object $a\in P$.

Monoid Categories

Given a monoid $(M,\cdot )$, we may construct an associated category:

•	objects: the single object $M$
•	arrows: the elements of $M$
•	composition: the multiplication of the elements of $M$
•	identity arrow: the identity element from the monoid

The Category $\mathbf{Cat}$

定义 1.3.2. A covariant functor (or simply functor) between two categories $\mathcal{C}$ and $\mathcal{D}$ is a mapping of objects of $\mathcal{C}$ to objects of $\mathcal{D}$ and of arrows of $\mathcal{C}$ to arrows of $\mathcal{D}$, denoted by $$F:\mathcal{C}\to \mathcal{D}$$satisfying the axioms:

(i)	For every $f:A\to B$ in $\mathcal{C}$, we have $F(f):F(A)\to F(B)$ in $\mathcal{D}$.
(ii)	For every object $A$ of $\mathcal{C}$, we have $F(1_A)=1_{F(A)}$.
(iii)	For every composable pair of arrows $f:A\to B$ and $g:B\to C$ in $\mathcal{C}$, we have $$F(g\circ f)=F(g)\circ F(f)$$hence the commutativity of the following left diagram implies the commutativity of the right diagram:

For functors $F:\mathcal{C}\to \mathcal{D}$ and $G:\mathcal{D}\to \mathcal{E}$, one defines the composite functor $G\circ F:\mathcal{C}\to \mathcal{E}$ by $$\begin{array}{rl}(G\circ F)(C)=G(F(C)),& \text{for every object}C\text{of}\mathcal{C}\\ (G\circ F)(f)=G(F(f)),& \text{for every arrow}f:A\to B\text{of}\mathcal{C}\end{array}$$

The category $\mathbf{Cat}$:

•	objects: small categories (that is, categories $\mathcal{C}$ such that $\mathrm{Ob}(\mathcal{C})$ and $\mathrm{Mor}(\mathcal{C})$ are sets)
•	arrows: covariant functors
•	composition: composition of functors
•	identity arrow: identity functor $1_{\mathcal{C}}:\mathcal{C}\to \mathcal{C}$ for every category $\mathcal{C}$, defined by the identity on objects and on arrows.

A Category form Logic

Given a deductive system of logic, we may construct an associated category of proofs:

•	objects: formulas $\phi ,\psi ,\dots$
•	arrows: implications $\phi \to \psi$
•	composition: succesive implications $\phi \to \psi \to \Delta$
•	identity arrow: each formula implies itself

A Category from Computer Science

Given a functional programming language $L$, we may construct an associated category:

•	objects: data types of $L$
•	arrows: computable functions on $L$ (“processes”)
•	composition: succesive computable functions $X\to Y\to Z$, where the output of the first arrow is the input of the second arrow
•	identity arrow: “do nothing” procedure

A Category from Physics

•	objects: physical system $A,B,C,\dots$
•	arrows: physical processes which take a physical system of type of $A$ into a physical system of type $B$
•	composition: sequential composition of physical processes
•	identity arrow: the physical process leaving the physical system invariant

1.4Isomorphisms

定义 1.4.1. In any category $\mathcal{C}$, an arrow $f:A\to B$ is called an isomorphism if there is an arrow $g:B\to A$ such that$$g\circ f=1_A\text{ and }f\circ g=1_B$$Since inverses are unique, we write $g=f^{-1}$.

We say that $A$ is isomorphic to $B$, written $A\cong B$ if there exists an isomorphism between them.

We recall the following famous theorem from Group Theory.

定理 1.4.2 (Cayley). Every group is isomorphic to a subgroup of a symmetric group.

证明. Let $(G,\cdot )$ be a group and consider the symmetric group$$S_G=\{g:G\to G\mid g\text{is bijective}\}.$$For every $a\in G$, define$$t_a:G\to G\text{by}{t}_a(x)=ax,\forall x\in G.$$One proves that $t_a\in S_G$, that is $t_a$ is bijective. We may now define$$f:G\to S_G\text{by}f(a)=t_a,\forall a\in G$$One shows that $f$ is an injective homomorphism. Then $\mathrm{Ker}f=\{1\}$.

By the first isomorphism theorem, it follows that$$G\cong G/\{1\}\cong G/\mathrm{Ker}f\cong \mathrm{Im}f.$$But $\mathrm{Im}f$ is a subgroup of $S_G$, so that we are done. Note that $\mathrm{Im}f$ is sometimes called the Cayley representation of $G$.

$\square$

注 1.4.3. Note the two different levels of isomorphisms that occur in the proof of Cayley’s theorem. There are bijective functions $g:G\to G$, which are isomorphisms in $\mathbf{Set}$, and there is the isomorphism between $G$ and $\mathrm{Im}f$ in $\mathbf{Grp}$. Cayley’s theorem says that any abstract group can be represented as a “concrete” one, that is, a subgroup of a symmetric group.

We may give the following category-theoretic analogue.

定理 1.4.4. Every category $\mathcal{C}$ with a set of arrows is isomorphic to one in which the objects are sets and the arrows are functions.

证明. Define the Cayley representation $\overline{\mathcal{C}}$ of $\mathcal{C}$, that is, the category corresponding to $\mathcal{C}$ via the isomorphism, to be the following concrete category:

•	objects: sets of the form $\bar{C}=\{f\in \mathcal{C}\mid \mathrm{cod}(f)=C\}$ for objects $C$ of $\mathcal{C}$
•	arrows: functions $\bar{g}:\bar{C}\to \bar{D}$ for arrows $g:C\to D$ in $\mathcal{C}$, defined by $\bar{g}(f)=g\circ f$ for every $f:X\to C$ in $\bar{C}$.

One shows the required properties.

$\square$

1.5Constructions on Categories

Product Category

Let $\mathcal{C}$ and $\mathcal{D}$ be categories. The product category $\mathcal{C}\times \mathcal{D}$ is defined as follows:

•	objects: pairs $(C,D)$ for some objects $C\in \mathcal{C}$ and $D\in \mathcal{D}$
•	arrows: pairs $(f,g)$ for some arrows $f\in \mathcal{C}$ and $g\in \mathcal{D}$
•	composition: for every composable arrows $(f,g),\left(f^{\prime },g^{\prime }\right)\in \mathcal{C}\times \mathcal{D}$, their composite is defined as$$(f,g)\circ \left(f^{\prime },g^{\prime }\right)=\left(f\circ f^{\prime },g\circ g^{\prime }\right)$$
•	identity arrow: for every object $(C,D)\in \mathcal{C}\times \mathcal{D}$, the identity arrow is $1_{(C,D)}=\left(1_C,1_D\right)$.

Clearly, the construction may be generalized for a finite number of categories.

Opposite Category

Let $\mathcal{C}$ be a category. The opposite category ${\mathcal{C}}^{\mathrm{op}}$ of $\mathcal{C}$ is defined as follows:

•	objects: the objects of $\mathcal{C}$. We denote by $C^{\ast }$ the object $C$ of $\mathcal{C}$ viewed as an object of ${\mathcal{C}}^{\mathrm{op}}$.
•	arrows: the arrows of the form $f^{\ast }:B^{\ast }\to A^{\ast }$ for some arrow $f:A\to B$ in $\mathcal{C}$.
•	composition: for every arrows $f^{\ast }:B^{\ast }\to A^{\ast }$ and $g^{\ast }:C^{\ast }\to B^{\ast }$ in ${\mathcal{C}}^{\mathrm{op}}$, their composite is defined as $$f^{\ast }\circ g^{\ast }=(g\circ f{)}^{\ast }$$
•	identity arrow: for every object $A^{\ast }\in {\mathcal{C}}^{\mathrm{op}}$, the identity arrow is $1_{A^{\ast }}=(1_A{)}^{\ast }$.

Arrow Category

Let $\mathcal{C}$ be a category. The arrow category ${\mathcal{C}}^{\to }$ of $\mathcal{C}$ is defined as follows:

•	objects: the arrows of $\mathcal{C}$.
•	arrows: an arrow $g=\left(g_1,g_2\right):f\to f^{\prime }$, where $f:A\to B$ and $f^{\prime }:A^{\prime }\to B^{\prime }$ are arrows of $\mathcal{C}$, is a square where $g_1:A\to A^{\prime }$ and $g_2:B\to B^{\prime }$ are arrows in $\mathcal{C}$, which is commutative in the sense that $$f^{\prime }\circ g_1=g_2\circ f$$
•	composition: for every composable arrows $\left(h_1,h_2\right)$ and $\left(g_1,g_2\right)$ in ${\mathcal{C}}^{\to }$, their composite is defined as $$\left(h_1,h_2\right)\circ \left(g_1,g_2\right)=\left(h_1\circ g_1,h_2\circ g_2\right).$$
•	identity arrow: for every object $f:A\to B$ in ${\mathcal{C}}^{\to }$, the identity arrow is $1_f=\left(1_A,1_B\right)$.

1.6Free Categories

Let $A$ be a set, which will be called an “alphabet”. Denote by $A^{\ast }$ the set of all “words” of with “letters” from $A$, that is, strings of elements from $A$. We call $A^{\ast }$ the Kleene closure of $A$. Denote by $e$ the empty word. We immediately have the following result.

定理 1.6.1. Let $A$ be a set. Consider on $A^{\ast }$ the operation “.” defined by concatenation. Then $\left(A^{\ast },\cdot \right)$ is a monoid with identity element $e$, called the free monoid on $A$.

定理 1.6.2 (Universal Mapping Property of the Free Monoid). With the above notation, there is an injective monoid homomorphism $i:A\hookrightarrow A^{\ast }$ with the property that for every monoid $N$ and for every function $f:A\to N$, there is a unique monoid homomorphism $\bar{f}:A^{\ast }\to N$ such that $\bar{f}\circ i=f$, that is, the following diagram is commutative

证明. Let $i:A\hookrightarrow A^{\ast }$ be the inclusion homomorphism, which is an injective monoid homomorphism. Define $\bar{f}:A^{\ast }\to N$ by$$\begin{array}{rl}\bar{f}(e)& =e_N\\ \bar{f}(w)& =f\left(a_1\right)\cdots f\left(a_n\right),\forall w=a_1\cdots a_n\in A^{\ast }\end{array}$$One checks that $\bar{f}$ is a monoid homomorphism and $\bar{f}(a)=f(a)$ for every $a\in A$, that is, $\bar{f}\circ i=f$.

For uniqueness, suppose that there is another monoid homomorphism $g:A^{\ast }\to N$ such that $g\circ i=f$. For every $w=a_1\dots a_n\in A^{\ast }$ we have$$g(w)=g\left(a_1\cdots a_n\right)=g\left(a_1\right)\cdot \cdots \cdot g\left(a_n\right)=f\left(a_1\right)\cdot \cdots \cdot f\left(a_n\right)=\bar{f}\left(a_1\cdots a_n\right),$$hence $\bar{f}=g$.

$\square$

推论 1.6.3. Universal mapping property of the free monoid determines it uniquely up to an isomorphism.

证明. Suppose that $M$ and $N$ are free monoids on a set $A$. Consider the inclusion homomorphisms $i:A\to M$ and $j:A\to N$. Since $M$ is a free monoid, by universal mapping property there is a monoid homomorphism $\alpha :M\to N$ such that $\alpha \circ i=j$. Since $N$ is a free monoid, by universal mapping property there is a monoid homomorphism $\beta :N\to M$ such that $\beta \circ j=i$. It follows that $(\beta \circ \alpha )\circ i=i$. But we also have $1_M\circ i=i$. Then by the uniqueness from universal mapping property we must have $\beta \circ \alpha =1_M$.

    

Similarly, we have $\alpha \circ \beta =1_N$. Hence $\alpha :M\to N$ is a monoid isomorphism.

$\square$

Next let us see how can we generalize the above results to categories.

To each category $\mathcal{C}$ we may associate a graph $G=(V,E)$, where the class $V$ of vertices consists of the objects of $\mathcal{C}$, while the class $E$ of edges consists of the arrows of $\mathcal{C}$. Then we have two functions $s:E\to V$ (source) defined by $s(e)=v_1$ for every arrow $e:v_1\to v_2$, and $t:E\to V$ (target) defined by $t(e)=v_2$ for every arrow $e:v_1\to v_2$.

We define the free category on the graph $G$, denoted by $\mathcal{C}(G)$, as follows:

•	objects: the vertices of $G$
•	arrows: the paths in $G$
•	composition: the concatenation of paths in $G$
•	identity arrow: for every $v\in V$ the identity arrow $1_v$ is the loop on $v$.

We may define a functor $U:\mathbf{Cat}\to \mathbf{Graph}$, called the forgetful functor, which associates to a category $\mathcal{C}$ its underlying graph having as edges the arrows of $\mathcal{C}$, and as vertices the objects of $\mathcal{C}$, and to a functor between categories its underlying graph homomorphism (that is, a functor without the conditions on composition and identity). One may prove the following result.

定理 1.6.4 (Universal Mapping Property of the Free Category on a Graph). With the above notation, there is a graph homomorphism $i:G\to U(\mathcal{C}(G))$ with the property that for every category $\mathcal{D}$ and for every graph homomorphism $f:G\to U(\mathcal{D})$, there is a unique functor $\bar{f}:\mathcal{C}(G)\to \mathcal{D}$ such that $U(\bar{f})\circ i=f$, that is, the following diagram is commutative:

推论 1.6.5. Universal mapping property of the free category on a graph determines it uniquely up to a graph isomorphism.

1.7Large, Small and Locally Small Categories

定义 1.7.1. A category is called:

(1)	small if both classes of objects and arrows are sets.
(2)	large if it is not small.
(3)	locally small if for every objects $C,D\in \mathcal{C}$, ${\mathrm{Hom}}_{\mathcal{C}}(C,D)$ is a set.

例 1.7.2.  

(1)	The category of finite sets and functions is equivalent to a small category.
(2)	$\mathbf{Set}$, $\mathbf{Pos}$, $\mathbf{Grp}$ and $\mathbf{Top}$ are locally small, but not small.
(3)	$\mathbf{Cat}$ is large, but not locally small. Indeed, if $\mathcal{C}$ is a locally small category which is not small, and $1$ is the category with one object and one arrow, then functors $1\to \mathcal{C}$ are simply objects of $\mathcal{C}$, so ${\mathrm{Hom}}_{\mathbf{Cat}}(1,\mathcal{C})$ is not a set.