Categories

Written by: Gabriel Field.

Definition

Transformations between mathematical objects capture the relationships between them. For example, we compare cardinalities using injective, surjective and bijective functions, and we declare groups to be "the same" using isomorphisms.

The central thesis of category theory is that understanding the objects we care about requires understanding the transformations between them. A category therefore abstracts this relationship of "transformations between objects".

Definition. (Category)

A category $\mathsf{C}$ consists of:

A collection $\mathrm{ob}\ \mathsf{C}$ of objects;
For each pair of objects $x, y \in \mathrm{ob}\ \mathsf{C}$, a collection $\mathsf{C}(x, y)$ called the hom-set from $x$ to $y$^[1] [1] The elements of the hom-sets go by various names including arrow, morphism and map.;
For each object $x \in \mathrm{ob}\ \mathsf{C}$, an identity arrow $1_x \in \mathsf{C}(x, x)$;
For each triple of objects $x, y, z \in \mathrm{ob}\ \mathsf{C}$, a composition operation $\circ : \mathsf{C}(y, z) \times \mathsf{C}(x, y) \to \mathsf{C}(x, z)$;

Subject to the following constraints:

(Associativity) For all $a, b, c, d \in \mathrm{ob}\ \mathsf{C}$ and for all $f \in \mathsf{C}(a, b),\ g \in \mathsf{C}(b, c),\ h \in \mathsf{C}(c, d)$, we require $$ (h \circ g) \circ f = h \circ (g \circ f) $$
(Unitality) For all $a, b \in \mathrm{ob}\ \mathsf{C}$ and for all $f \in \mathsf{C}(a, b)$, we require $$ 1_b \circ f = f = f \circ 1_a $$

The subscripts on each $1_a$ are sometimes omitted, as is the $\circ$ symbol entirely. As further shorthand, it is common to write expressions such as $\text{``}a \xrightarrow{f} b \text{ in } \mathsf{C}\text{''}$ to refer to objects $a, b \in \mathrm{ob}\ \mathsf{C}$ and an arrow $f \in \mathsf{C}(a, b)$. In light of this, the associativity and unitality axioms can be rewritten as^[2] [2] The first of these conditions highlights why some category theorists prefer writing $fg$ to mean "$f$ then $g$" rather than the conventional "$f$ after $g$" — the conventional order is backwards to the diagrams! $$\begin{align*} \forall a \xrightarrow{f} b \xrightarrow{g} c \xrightarrow{h} d \text{ in } \mathsf{C},\quad &(h \circ g) \circ f = h \circ (g \circ f) \\ \forall a \xrightarrow{f} b \text{ in } \mathsf{C},\quad &1_b \circ f = f = f \circ 1_a \end{align*}$$ In particular, the associativity condition states that any path $a_0 \xrightarrow{f_1} a_1 \xrightarrow{f_2} \cdots \xrightarrow{f_n} a_n$ can be composed together in a unique way: $a_0 \xrightarrow{f_n \circ \cdots \circ f_1} a_n$.

Examples

By understanding categories in the abstract, we can apply our understandings to a diverse array of mathematical contexts.

Example. ($\mathbf{Set}$)

The most important example of a category^[3] [3] The Yoneda lemma makes this precise. is the category $\mathbf{Set}$. Its objects are sets, and the collection $\mathbf{Set}(X, Y) := Y^X$ is the set of all functions $X \to Y$. The identity arrows $1_X := \mathrm{id}_X$ are the identity functions, and the composition operation is function composition. You should check that this is a category!

Example. ($\mathbf{Group}$)

As alluded to in the previous section, there is a category $\mathbf{Group}$ whose objects are groups, and whose hom-sets $\mathbf{Group}(G, H)$ consist of all group homomorphisms between them. The identity arrows $1_G := \mathrm{id}_G$ and composition operations are the same as in $\mathbf{Set}$.

Example. (Algebraic structures)

Generalising the previous example, many notions of algebraic structures form categories. For instance, there are categoires $\mathrm{Monoid}$, $\mathrm{Ring}$, $\mathrm{Algebra}$ etc. whose objects are monoids, rings, algebras etc. (respectively) and whose hom-sets consist of the homomorphisms between them. The identity arrows are the identity functions and the composition operations are function composition; these always turn out to produce homomorphisms.

A particular kind of algebraic structure you may not be familiar with is a based set. Each based set is a pair $(X, x)$ of a set $X$ and an element $x \in X$, called its basepoint. A based set homomorphism from $(X, x)$ to $(Y, y)$ is a function $f : X \to Y$ which preserves the endpoint: $x \xmapsto{f} y$. These form a category $\mathrm{Set}_{*}$ where the objects are based sets and the arrows between them are based set homomorphisms; as before, the identities and composition operations are given by identity functions and function composition.

It is also worth noting that $\mathrm{Set}$ can be described as a category of algebraic structures. Sets are algebraic structures with no operations, and the homomorphisms are functions (which don't need to preserve any structure at all!).

Example. ($\mathbf{Top}$)

Another important category is $\mathrm{Top}$, whose objects are topological spaces and whose arrows are the continuous functions between them. $\mathrm{Top}$ behaves quite differently to the categories of algebraic structures. For example, the isomorphisms in algebraic categories are exactly the bijective homomorphisms, but there are bijective continuous functions in $\mathrm{Top}$ which fail to be isomorphisms (homeomorphisms).

If you are familiar with topology, is a good exercise to check that $\mathrm{Top}$ is indeed a category.

There are many other categories with geometric flavours. Topological/differentiable/smooth manifolds give rise to such categories.

Example. ($\mathbf{Vect}_K^{\text{fd}}$ and $\mathbf{Mat}_K$)

Another category of algebraic structures worth explicitly mentioning is the category $\mathbf{Vect}_K^{\text{fd}}$ whose objects are finite-dimensional vector spaces over the field $K$, and whose arrows are the linear transformations between them. If you have studied linear algebra, you will know that these linear transformations may be encoded using matrices. Accordingly, there is a category $\mathbf{Mat}_K$ defined as follows. The collection $\mathrm{ob}\ \mathbf{Mat}_K := \mathbb{Z}_{\geq 0}$ is the set of natural numbers, and each hom-set $\mathbf{Mat}_K (n, k)$ is the set of $k \times n$ matrices with elements in $K$. You could think of the objects $n, k$ as representing the standard vector spaces $K^n$ and $K^k$, and the matrices $M \in \mathbf{Mat}_K (n, k)$ as encoding linear transformations $K^n \to K^k$. Can you guess what the identity and composite arrows are?

On the surface, these two categories seem very different. $\mathbf{Vect}_K^{\text{fd}}$ has as many objects as there are sets^[4] [4] See the section on size issues whereas $\mathbf{Mat}_K$ only has countably many objects, and the arrows in $\mathbf{Mat}_K$ aren't even functions. However, as any linear algebra student is acutely aware, studying linear transformations is the same as studying matrices. This idea appears in category theory as an equivalence of categories between the categories $\mathbf{Vect}_K^{\text{fd}}$ and $\mathbf{Mat}_K$.

Example. (Posets and preorders)

Akin to $\mathbf{Mat}_K$, not all categories use functions as their arrows. There is no better example of this than the poset and preorder categories.

Fix a poset $(P, \leq)$. We can construct a category $\mathsf{P}$ as follows.

The collection of objects is $\mathrm{ob}\ \mathsf{P} := P$.
For each pair of objects $x, y \in P$, if $x \leq y$, then the hom-set $\mathsf{P}(x, y) := \left\{ \text{``Yep, } x \leq y \text{ alright!''} \right\}$ consists of a single element; otherwise, $\mathsf{P}(x, y) := \varnothing$. The particular name of the element isn't important, and henceforth we will abbreviate it to $(x \leq y)$, enclosed in parentheses.
For each object $x \in P$, the identity arrow $1_x := (x \leq x)$ represents the fact that $x \leq x$. The identity arrows therefore encode reflexivity.
For objects $x \xrightarrow{(x \leq y)} y \xrightarrow{(y \leq z)} z \text{ in } \mathsf{P}$, the composite arrow $(y \leq z) \circ (x \leq y) := (x \leq z)$ represents the fact that $x \leq y \leq z \implies x \leq z$. The composition operation therefore encodes transitivity.

The associativity and unitality equations are trivial — since each hom-set consists of at most one element, any two elements of the same hom-set are equal. Because the description above makes use only of reflexivity and transitivity, it also holds for a preorder.

A few poset categories are interesting for categorical reasons. The ordinal $0$, also known as the empty poset, yields the empty category $\mathbf{0}$. The ordinal $1$ (which contains a single element) yields the terminal category $\mathbf{1}$. The ordinal $2$ defines a category $\mathbf{2} = (\bullet \to \bullet)$ which contains two objects and a single arrow between them. We can use this category and the idea of a functor to inspect the arrows within a category of interest.

The fact that preorders form categories allows us to apply category theory to order theory, and it allows us to borrow ideas from order theory when developing category theory. For example, adjunctions can be inspired by Galois connections, and the fact that right adjoints preserve limits can be used to establish that upper/lower adjoints of Galois connections are semilattice homomorphisms.

Preorders also represent an extreme kind of category when discussing size issues. For example, any $\kappa$-small category that admits all $\kappa$-small limits is a preorder^[5] [5] Proof.

Example. ($\mathbf{Cat}$)

Categories are now objects we care about. The central thesis of category theory states that understanding the objects we care about requires understanding the arrows the arrows between them. The arrows between categories are known as functors and they, together with the small categories, form the category $\mathbf{Cat}$ of all small categories. See our discussion on functors for more details.

Functors, then being objects that we care about, should be understood by studying the arrows between them. The arrows between functors are known as natural transformations and they upgrade $\mathbf{Cat}$ from being merely a category to being a 2-category.

This sort of recursiveness is a common theme in category theory…

Exercise.

Check that the above examples do indeed form categories. Only check the ones which interest you :)

Size issues

Many categories that arise 'in nature' have at least as many objects as there are sets. The most important category, $\mathbf{Set}$, is such an example. Of course, there is no set of all sets, so we cannot expect $\mathbf{Set}$ to have a set of objects. There are a couple of solutions. Perhaps the easiest to explain is the idea of a Grothendieck universe^[6] [6] I hate these, though, although others such as type theories also exist.

In any case, it is worth making the following definition. Fix a cardinal $\kappa$. A set is $\kappa$-small when its cardinality is $< \kappa$. A category $\mathsf{C}$ is $\kappa$-small just when the cardinality of the union of all its hom-sets is $\kappa$-small: $$ \left\lvert \bigcup_{x, y \in \mathrm{ob}\ \mathsf{C}} \left( \mathsf{C}(x, y) \right) \right\rvert < \kappa $$ In practice, we fix an inaccessible cardinal $\kappa$, use the word small to mean $\kappa$-small, and immediately forget about the cardinal $\kappa$. We then adjust our definitions — $\mathbf{Set}$ is redefined to be the category of small sets and functions between them, $\mathbf{Group}$ is the category of small groups and their homomorphisms, etc. A large set is one that is not small.

This distinction facilitates an important definition; a category $\mathsf{C}$ is locally small just when each hom-set $\mathsf{C}(x, y)$ is small. Whilst many categories do not have a small collection of objects, they turn out to be locally small. All of the categories listed in the previous section are locally small.

It is somewhat fruitless to think of large categories; for a different choice of the cardinal $\kappa$, some previously large categories may be small categories. In general, results that hold for small categories or locally small categories hold for slightly larger categories or those with slightly larger hom-sets if you pass to a larger inaccessible cardinal.

As a related point, it is worth emphasising that the term 'hom-set' can be somewhat misleading. The hom-sets $\mathsf{C}$ of a category $\mathsf{C}$ are only ever required to be collections — a catch-all term to evade size issues. In particular, they need not form (small) sets. It is exactly the locally small categories for which the name 'hom-set' is not misleading.

Emily Riehl. Category Theory in Context. URL: https://emilyriehl.github.io/files/context.pdf.