One fact that gets thrown around a lot in category theory is that categories are monads in spans.
I considered this a weird fact for a long time, but then it slowly became an irreplaceable part of the way I think about categories.
\bf Span(Set) is a bicategory, i.e. a category whose hom-sets are in fact hom-categories themselves (and whose composition is suitably weakened, but we won’t concern ourselves with that here). This is less scary than it might look. In the case of \bf Span(Set), the objects are sets X, Y, \ldots, the morphisms are functions X \xleftarrow{f} S \xrightarrow{g} Y (S being the apex, X, Y being the feet and f,g being the legs), and the morphisms between these are morphisms between the apexes that commute with the legs.
Most importantly, these spans compose by pullback: given two composable spans X \xleftarrow{f} S \xrightarrow{g} Y \xleftarrow{h} R \xrightarrow{k} Z, we get a composite span X \xleftarrow{p_Sf} S \times_Y R \xrightarrow{p_Rg} Z, where S \xleftarrow{p_S} S \times_Y R \xrightarrow{p_R} R is the pullback of h and g over Y:
Evidently, the identity span is the one whose legs are identities X = X = X.
Now, to get a sense of what a ‘monad in \bf Span(Set)’ is, and why it is a category, we first have to learn that a monad in a bicategory is nothing but a monoid in one of the endomorphism categories of said bicategory.
Thus, in our case, we have to realize what a monoid in {\bf Span(Set)}(X,X) is. First, recall that endomorphisms in a bicategory always form a monoidal category, where the monoidal product is given by composition.
Thus a monoid in {\bf Span(Set)}(X,X) is, first of all, a span X \xleftarrow{s} M \xrightarrow{t} X equipped with two morphisms:
- A unit:
- A composition:
We can reason about these operations using elements, not just because we are in sets, but because we can always do that if we are careful enough, meaning we use generalized elements.
Also, a good way to reason about spans is to think that the apex is a set of things indexed by the feet. So in our case, chosen two elements x,y \in X, we get a bunch of elements m \in M_{x,y} = \{m \mid s(m) =x, t(m)=y\}. So we see… we get a set of things for every two elements in X… if you squint a bit, you can think we are assigning hom-sets to pairs of objects of a category!
Thus from now on, I’ll call elements of X ‘objects’ and elements of M ‘morphisms’. Moreover, I’ll denote an m \in M as m:x \to y when s(m)=x and t(m)=y. This motivates calling s and t the source and target maps of our wannabe category.
With this notation, we see that i(x) : x \to x and that the domain of ; is, in fact, the set of composable maps \sum_{y \in X} \{x \xrightarrow{m} y \xrightarrow{n} z\}. The big diagram defining ; then can be summarized as follows:
Thus, at least at the level of data, we are getting what we expect: a monad in \bf Span(Set) is a set of objects and a set of morphisms, each with a source and target object, such that every object x \in X has a distinguished identity morphism i(x):x \to x and such that consecutive morphisms can be composed.
It remains to state which properties do i and ; respect, namely unitality and associativity.
The first means that composing with identity morphisms is a no-op, which in our notation means:
and surely this is property of a category too.
The second means that composing morphisms is an associative operation, also true for categories:
So the remarkable simplicity of monoids yields a very rich structure, that of a category, when interpreted in the right context (endomorphisms of \bf Span(Set)). This is one of the tenets of category theory: complexity can be traded off between an object and the context we are defining it in.
In fact, this very trick is used to define and relate different flavours of categories: just take monads in a suitable bicategory. I won’t delve into details, but I’ll just mention that internal categories and enriched categories can be obtained in this way, by replacing \bf Span(Set) with, respectively, spans in a finitely complete category \cal E and \cal V-valued matrices for a suitably cocomplete monoidal category \cal V [1]. The paper A unified framework for generalized multicategories takes this even further, and gives a great breakdown of the kinds of categories one can get by simply taking monads in the right place. Among these: topological spaces, metric spaces, operads!
Footnotes
- Jade Master is very passionate about double categories of matrices—check out her PhD thesis if you want to learn about the magic things you can do with monads in matrices