A Brief Introduction to Categories, Part 1: Categories

The purpose of this post is to establish some basic language of categories. This can be read independently of the ongoing series on representation theory, although concepts and results from this post will be used in the representation theory series. So with respect to the representation theory series, one can think of this post (and the follow-up posts) as the analog of an appendix.

The notions of category theory can be encountered in many different mathematical contexts. To illustrate the concepts, a range of examples will be given, but I will go quickly over standard examples – For common examples in greater detail and multitude, see the references below. It is not necessary to know the background of every single example to grasp the concepts.

To readers who wish to read a more detailed introduction, I recommend Tom Leinster’s “Basic Category Theory” (available as a free pdf, but also published in book form) or in case you know German Martin Brandenburg’s “Einführung in die Kategorientheorie”. If you simply cannot get enough, Francis Bourceux’ three-volume Handbook of Categorical Algebra is the right place to get lost in the realm of categories and functors.

The views expressed on category theory are naturally (no pun intended) my own highly subjective ones and others may differ, especially those with a categorical disapproval of categorical things.

Introduction

The meta-mathematical notions of category theory provide a unifying framework for a lot of different mathematical theories. (Merely having a framework, however, can’t always replace delving into the specifics of the particular objects that one is interested in.) We can not only translate statements into categorical language, but we can also use categorical language to make things precise that might otherwise be vague, e.g. what it means for two different kinds of mathematical structures to be “equivalent” or what it means for a map to be “natural”.

The basic objects of category theory are categories. One should think of a category as a big directed graph in which objects are represented by nodes and morphisms are represented by arrows and where we have a special operation called composition that takes two consecutive arrows and produces a third arrow representing going along one arrow first and then along the other one.
Compared with set theory, which can be called “materialistic”, in the sense that it is about what objects actually are made out of, category theory can be considered “behavioristic”, in the sense that it’s more about how objects behave, i.e. relate to each other. Relations between objects are conceptualized by the arrows also known as morphisms. But for morphisms, just like for the objects themselves, it’s more about how they relate each other and less about what they actually represent. The relations between morphisms are given by composition.
From a linguistic point of view, category theory is purely syntax, whereas semantics come into play only in the interpretation of particular examples.

Thinking categorically, we can economize on routine verifications by doing them in the utmost generality. More importantly, category theory can expose formal similarities between seemingly disconnected phenomena. These analogies might only become apparent through the high level of abstraction category-theoretic concepts provide, allowing one to transfer intuition, techniques and concepts in ways not available otherwise, at least not as easily or as precisely-defined.

Peter Freyd wrote once that “Perhaps the purpose of categorical algebra is to show that which is trivial is trivially trivial.”
Peter May commented: “I prefer an update of that quote: ‘ Perhaps the purpose of categorical algebra is to show that which is formal is formally formal’. It is by now abundantly clear that mathematics can be formal without being trivial.”

Now then! After this informal introduction, let us delve into the formal details of why that which is formal is formally formal.

Categories

Definition C1.1 A category $\mathcal{C}$ consists of the following data:

A class of objects $\mathrm{Obj}(\mathcal{C})$
For every pair of objects $X,Y \in \mathrm{Obj}(\mathcal{C})$ , a set of morphisms $\mathrm{Hom}_{\mathcal{C}}(X,Y)$
For every triple of objects $X,Y,Z \in \mathrm{Obj}(\mathcal{C})$ , a map $\mathrm{Hom}_{\mathcal{C}}(Y,Z) \times \mathrm{Hom}_{\mathcal{C}}(X,Y) \to \mathrm{Hom}_{\mathcal{C}}(X,Z)$ called composition and denoted by $(f,g) \mapsto f \circ g$

Such that the following conditions hold:

For any object $X \in \mathrm{Obj}(\mathcal{C})$ , there exists an identity $\mathrm{id}_X \in \mathrm{Hom}_{\mathcal C}(X,X)$ such that for all objects $Y,Z \in \mathrm{Obj}(\mathcal{C})$ and all morphisms $f \in \mathrm{Hom}_{\mathcal{C}}(Y,X), g \in \mathrm{Hom}_{\mathcal{C}}(X,Z)$ we have $\mathrm{id}_X \circ f= f$ and $g \circ \mathrm{id}_X = g$
Composition is associative, that means for all objects $X,Y,Z,W \in \mathrm{Obj}(\mathcal{C})$ and $f \in \mathrm{Hom}_{\mathcal{C}}(X,Y), g \in \mathrm{Hom}_{\mathcal{C}}(Y,Z), h \in \mathrm{Hom}_{\mathcal{C}}(Z,W)$ , we have $h \circ (g \circ f) = (h \circ g) \circ f$
$\mathrm{Hom}_{\mathcal{C}}(X,Y) \cap \mathrm{Hom}_{\mathcal{C}}(X',Y') = \varnothing$ unless $X=X'$ and $Y=Y'$

Remark The last condition is just a technical one that is not very interesting and is mostly omitted from verifications that things are categories. You can always replace the Hom-sets by disjoint copies by set-theoretic juggling, so it’s not much of an issue. The advantage of this convention is that source and target of a morphism are uniquely determined.

Example C1.2 We can form the category of sets $\mathbf{Set}$ , where $\mathrm{Obj}(\mathbf{Set})$ is the class of all sets and for $X,Y \in \mathrm{Obj}(\mathbf{Set})$ , $\mathrm{Hom}_{\mathbf{Set}}(X,Y)$ is the set of all maps from $X$ to $Y$ and the composition of morphisms is just the usual composition of maps. Many other examples (but not all of them) can be formed as “subcategories” of this example in the sense that the objects are sets with additional structure and morphisms are mappings which preserve that structure in some way, such as topological spaces and continuous maps or algebraic structures of a specific type and homomorphisms or smooth manifolds and smooth maps or complex manifolds and holomorphic maps or varieties over an algebraically closed fields and regular maps etc.

Example C1.3 There is another category with the class of all sets as objects, but with more morphisms. Recall that a mapping is a particular kind of relation. $\mathbf{Rel}$ is the category consisting of all sets as objects, and for two objects $X,Y \in \mathrm{Obj}(\mathbf{Rel})$ , $\mathrm{Hom}_{\mathbf{Rel}}(X,Y)$ is the set of all relations from $X$ to $Y$ , i.e. subsets $R \subset X \times Y$ . Given three sets $X,Y,Z$ and relations $R \subset X \times Y, S \subset Y \times Z$ , we can form the composite relation $S \circ R := \{(x,z) \in X \times Z \mid \exists y \in Y: ((x,y) \in R \land (y,z) \in S) \}$ . (If $R$ and $S$ are functions, this reduces to regular function composition.) With this composition, $\mathbf{Rel}$ satisfies the axioms for a category.

Example C1.4 In the previous examples for categories, the objects were given by the class of all sets. But there’s also the possibility to fix a particular set $X$ and consider $X$ as a category $\mathcal{C}$ in the following way: $\mathrm{Obj}(\mathcal{C})=X$ and the only morphisms are the identity morphisms required by the definition of categories. Due to the striking similarity with discrete topological spaces (compare for instance the set of morphisms $\mathrm{Hom}_{\mathcal{C}}(x,y)=\varnothing$ if $x \neq y$ and $\mathrm{Hom}_{\mathcal{C}}(x,y)=\mathrm{id}_x$ if $x=y$ with the discrete metric), this construction is called the discrete category on the set $X$ .

Example C1.5 Instead of only allowing for the minimum amount of morphisms, we can take a set $X$ and consider such categories with $X$ as their class of objects that have at most one morphism between two objects. In such a case, the only interesting information is whether there is a morphism between two objects or not. Consequently, such a category corresponds to a relation $R \subset X \times X$ . But the requirements for compositions and identities force a relation to have some properties if it is supposed to define a category in this manner: the existence of identity morphisms in the supposed category is equivalent to the relation being reflexive and the existence of compositions translates to transivity. A reflexive and transitive relation is called “preorder”. For instance, all equivalence relations and all partial orderings are preorders. An example of a preorder that is neither can be formed by taking a ring, say, an integral domain $A$ such as $\mathbb{Z}$ and considering the divisibility relation on elements of $A$ . Here the failure to be a partial order is due to the existence of non-trivial units and the failure to be an equivalence relation is to due the existence of non-invertible elements.

Definition C1.6 Speaking of invertible things, just like for an element in a ring, we can define when a morphism in a category is invertible. Let $f:X \to Y$ a morphism in a category. Then $f$ is called invertible, or an isomorphism, if there is a morphism $g:Y \to X$ such that $g \circ f = \mathrm{id}_X$ and $f \circ g = \mathrm{id}_Y$ . If there is such a morphism, then $X$ and $Y$ are called isomorphic. Note that the notations $f: X \to Y$ and $g \circ f$ , albeit reminiscent of the situation in the category $\mathbf{Set}$ , don’t necessarily refer to mappings or function composition, but to the particular morphisms and composition in an arbitrary category.

Example C1.7 Other than restricting the size of morphisms as in example C1.5, one can also restrict the size of the class of objects. For this, let’s consider categories with only one object. In general, if we consider composition as a function on all morphisms of a category, it is only partially defined, since source and target need to match up correctly. But this doesn’t arise if we have only one object. Let $\mathcal C$ be a category with one object $x$ and let $\mathrm{Hom}_{\mathcal C}(x,x)=M$ . Then composition is a (totally defined) mapping $M \times M \to M$ , i.e. a binary operation.
The existence of the identity $\mathrm{id}_x:=e$ implies that $e$ is a unit with respect to this binary operation and the associativity of the composition implies that the binary operation is, well, associative. Thus composition $\circ:M \times M \to M$ makes $M$ into a monoid.
Conversely, given a monoid $M$ , we can turn $M$ into a one-object category by taking a proxy object $x$ with no particular meaning, setting $\mathrm{Hom}(x,x)=M$ and defining the composition via the monoid operation. These constructions are inverse to each other, such that monoids correspond to one-object categories.
A particular frequently occuring and much beloved class of monoids consists of groups, i.e. monoids in which every element is invertible. By a pleasant convergence of terminology, an element in a monoid being invertible (in the classical sense) is the same as being an invertible morphism if we consider the monoid as a one-object category. Thus we can say that a monoid is a group if and only if every morphism is an isomorphism. This leads to the following notion:

Groupoids

Definition C1.8 A groupoid is a category such that every morphism is an isomorphism.

If we think of groups as encoding the symmetries of one object, then groupoids can capture the symmetries of a configuration with many objects.

Example C1.9 Let $R$ be a preorder on a set $X$ , then we can form a category from these data as described in example C1.8. One can ask when one obtains groupoid in this way. It turns out that the corresponding category is a groupoid if and only if $R$ is symmetric, i.e. an equivalence relation.

Remark From this observation we can extract an intuition for general groupoids: a groupoid is like a set with an equivalence relation, except that two objects can be equivalent in more than one way and we’re keeping track of different ways of being equivalent. From this viewpoint a group, being a one-object groupoid, is like the various ways a particular object is equivalent to itself, following the narrative that groups encode the symmetries of an object.

Example C1.10 Let $G$ be a group acting on a set $X$ , then one can form a groupoid encoding the group action as follows: Let $X // G$ be the category having elements from $X$ as its objects and for every $x \in X$ and $g \in G$ , there’s a morphism $x \to gx$ , such that $\mathrm{Hom}_{X // G}(x,y)$ is in bijection with $\{g \in G:gx=y\}$ . This groupoid played an important role in a previous post.

Example C1.11 Let $\mathcal C$ be any category. Then there is a maximal subcategory that is a groupoid: simply take the subcategory of $\mathcal C$ with the same objects as $\mathcal C$ and all the isomorphisms of $\mathcal C$ as morphisms. This is called the core of the category $\mathcal C$ and it is a groupoid. If $\mathcal C$ has only one object, i.e. is a monoid, then the core of $\mathcal C$ is just the group of invertible elements, also known as units.
As an exercise, one can check that the categories $\mathbf{Set}$ and $\mathbf{Rel}$ (cf. C1.2 and C1.3) have the same core, i.e. any invertible relation is already a function and in fact a bijection.

Example C1.12 Let $X$ be a topological space. Then the fundamental groupoid $\Pi_1(X)$ has as its objects all elements of $X$ . For $x,y \in X$ , $\mathrm{Hom}_{\Pi_{\leq 1}(X)}(x,y)$ consists of all homotopy classes of paths from $x$ to $y$ . Composition is given by concatenation of paths. $\Pi_{\leq 1}(X)$ contains important homotopy-theoretic information about $X$ , such as the path-components and the fundamental group of each path-component. For more information on this very geometric construction and groupoids in algebraic topology, I heartily recommend Ronald Brown’s “Topology and Groupoids”.