What is a category?
2018-10-09
Intuition ¶
Just like computer programs, mathematical objects can be described on various levels of abstraction. On the lowest level, set theory and predicate logic allow us to construct all objects in a bottom-up approach, starting only from the empty set and some reasonable choice of axioms. On a higher level, category theory allows us to speak about the patterns and the structures underlying modern mathematics, and to
- distill common features of structures that appear in many areas of mathematics,
- spot known patterns in new situations, and
- simplify ones mental picture of a problem by raising the level of abstraction.
Comparing mathematics to programming, one could liken set theory and predicate logic to assembler, and category theory to a high-level programming language like Haskell, Scala, Erlang or the like.
The key idea of category theory is that mathematical objects should be studied in terms of their relations to other objects rather than in isolation, and usually come with some natural classes of maps.
For example, linear algebra is not concerned with vector spaces alone, but also with the linear maps between them: matrices carry much more structure than simple row or column vectors. Now, a category is just a collection of objects and of morphisms between them, where the objects and morphisms can be thought of as the vertices and arrows of a graph, and morphisms can be composed to obtain new morphisms.
Definition ¶
More formally, a category $\mathsf{C}$ consists of
- a class of whose elements will be called the objects of $\mathsf{C}$,
- for every pair of objects $X,Y$, a set $\mathsf{C}(X,Y)$ whose elements will be called morphisms from $X$ to $Y$,
- for every object $X$, a morphism $\iota_{X} \in \mathsf{C}(X,X)$ called the identity,
- for every triple of objects $X,Y,Z$ a map $\mathsf{C}(Y,Z) \times \mathsf{C}(X,Y) \to \mathsf{C}(X,Z)$ which is called composition and written as $(g,f) \mapsto g\circ f$.
such that composition with identity morphisms is trivial, and composition of morphisms is associative.
Examples ¶
Once one starts to look for them, one can spot categories everywhere in mathematics. For example, take
all sets as objects and all maps between them as morphisms, where "all" is the reason why the objects form no set but only a class.
all vector spaces (over a fixed field) as objects and all linear maps between them as morphisms.
all natural numbers as objects and all matrices (over some fixed field again) of size $m\times n$ as the morphisms from $n$ to $m$, where composition is given by matrix multiplication. For example, the matrices
$$ \begin{pmatrix} 1 & 0 & 2 \ 3 & 0 & 4 \end{pmatrix} \quad \text{and} \quad \begin{pmatrix}5 & 4\end{pmatrix} $$
would be regarded a morphisms from 3 to 2 and 2 to 1, respectively, with composition $\begin{pmatrix}17 & 0 & 26\end{pmatrix}$.
all natural numbers as objects and each pair $(m,n)$ where $m$ divides $n$ as a morphism from $m$ to $n$. For example, the following diagram shows all morphisms between the numbers $1,\ldots,6$ except for the identities:
Here, morphisms can be composed because the divisibility relation is transitive.
Link to functional programming ¶
Category theory also provides a solid mathematical foundation and a source of inspiration for functional programming. Informally, it helps to think
- of data types like
Integer
,Boolean
orString
as objects, and - of functions without side-effects as morphisms of a category.
For example, a function that computes the length of a string would be a
morphism from String
to Integer
, and a function that computes the
sum of two integers would be a map from (Integer, Integer)
to
String
, where (Integer, Integer)
denotes a compound data type. To
make this more precise, one would have to dive deeper into the semantics
of programming languages. A simple point of view is to think
- of each data type as a set of possible values, and
- of each function as a map from the set of possible inputs to the set of possible outputs.
References ¶
Standard textbooks on category theory are, for example,
- Categories for the Working Mathematician by Saunders MacLane, a classic,
- Basic category theory by Tom Leinster, whom I learned category theory from,
- Einführung in die Kategorientheorie by Martin Brandenburg.