Why double categories? Part 1
The algebra of relations
This post is cross-posted at the Topos Institute blog.
Lately I’ve been fixated on double categories, pursuing a range of theoretical and applied directions. Being a type of higher-dimensional category, double categories might seem intimidating, especially to newcomers to category theory. So I’d like to explain what makes double categories so natural, even inevitable.
In a series of posts, I will give a few different answers to the question of “why double categories?” without assuming any knowledge of the subject, or even very much of category theory. The focus will be on high-level ideas; I’m not going to give any precise definitions or theorem statements. Today I will explain how double categories clarify an old idea, what was once called the “calculus of relations,” now the “algebra of relations.” I think this application a good place to start because it arises from very concrete things.
The algebra of relations
Of all the concepts of mathematics, relations are among the most tangible and immediately connected to everyday life. So a first, very immediate justification for double categories is that they are the most satisfactory answer yet found to the question:
What is the algebra of relations between things?
To appreciate how double categories illuminate relational algebra, it is helpful to recall some of its long history.
Since the early 20th century revolution in formal mathematics, and with antecedents even in the 19th century, mathematicians have sought axioms for the “algebra of relations”: a synthetic account of the rules for relational reasoning. Two famous approaches are
- relation algebras, introduced by Tarski (1941) to axiomatize binary relations on a set, and
- relational algebra, introduced by Codd (1970) as a mathematical foundation for relational databases.
If you’ve worked at all with logic or databases, you’ve probably encountered something like one of these. Confusingly, the two formalisms are rather different despite having almost the same name.
Whatever other merits they might possess, the axioms of these systems appear to be ad hoc and arbitrary, with little to mark them as privileged compared to other possible axioms or to connect them with other ideas in mathematics. They are intellectual islands within mathematical logic and theoretical computer science.
Bicategories of relations
When category theory emerged as a unifying metatheory for mathematics, people naturally sought to axiomatize relations in category-theoretic terms, hoping to bring relations into the fold of structuralist mathematics, to make the “algebra of relations” part of what is now understood as algebra. I know of two early approaches:1
- allegories, introduced by Freyd and Scedrov (1990) in their book, Categories, Allegories, and
- bicategories of relations, introduced at around the same time by Carboni and Walters (1987).
Of the two, allegories are closer to Tarski’s relation algebras, with a converse or involution operation playing a key role in the axioms, whereas bicategories of relations are defined in terms of concepts well known to category theorists, namely (locally posetal) bicategories and monoidal categories. The latter are especially helpful in making connections with other parts of mathematics and science. Coecke and Paquette (2010) develop a detailed analogy between the monoidal category of finite-dimensional Hilbert spaces, as used in quantum theory, and the monoidal category of sets and relations.2 Bicategories of relations will always hold a special place in my heart, being the topic of my very first paper involving category theory (Patterson 2017). In this partly expository work, I argued that bicategories of relations could serve as a mathematical foundation for knowledge representation reminiscent of, but more elegant and flexible than, the standard foundation based on description logic.
Nevertheless, as I’ve learned more category theory, I have gradually realized that allegories and bicategories of relations, which are essentially equivalent structures, suffer from defects that cannot be repaired at the categorical or bicategorical level. The reason is that the category they seek to axiomatize—the category of sets and relations—is a badly behaved category, and the (locally posetal) bicategory of sets, relations, and implications is not much better. Naturally, then, any attempt to axiomatize it will only reproduce its deficiencies in a more abstract form.
Although the details of these issues are not too important at this level, I will mention a few to be concrete:
- The (bi)category of sets and relations fails to have many limits and colimits.
- The limits and colimits it does possess behave counterintuitively due to its self-duality: products in this category (which are also coproducts) are disjoint unions of sets!
The second issue is the source of a longstanding puzzle: in category theory, we seek to recognize mathematical constructions as “intrinsic” in arising from universal properties, such as limits and colimits, but the evident cartesian (set-theoretic) product of relations does not arise from any standard universal property in the category or bicategory of relations. Carboni and Walters’ axioms for a bicategory of relations are a direct response to this problem, characterizing the cartesian product through an elaborate structure that is only with considerable effort eventually proved to be property-like.
Double categories of relations
The category-theoretic troubles with relations are explained by the slogan that, while the morphisms of a category need not be functions, category theory tends to work best when the morphisms are “function-like.” Indeed, category theory arose to codify the patterns present in the ur-category of sets and functions and in the many categories of mathematical structures—vector spaces, groups, topological spaces, and so on—whose morphisms are structure-preserving maps. The category of relations is very far from these examples.
With this perspective, an idea suggests itself: to fix the bicategory of relations, we just need to put the functions back in.3 Double categories are the right structure to do this. A double category has two kinds of morphisms, which for now we will think of as “vertical” and “horizontal,” and square-shaped cells binding them together, which can be composed in both directions.
We can make a double category \(\mathbb{R}\mathsf{el}\) that has
- sets as objects
- functions as vertical morphisms
- relations as horizontal morphisms
- a unique cell of the form
whenever the implication holds:
\[ R(x,y) \implies S(f(x), g(y)), \qquad \forall x \in X,\ y \in Y. \]
At first glance, the double category of relations looks not too different from the bicategory of relations, but something remarkable happens. We can now recover the cartesian product, plus a whole bunch of other operations on relations, from double-categorical universal properties. That is, merely from the composition of functions, of relations, and of the cells between them, all of the following operations, and others still, are uniquely determined by universal properties in \(\mathbb{R}\mathsf{el}\):
| Notation | Description |
|---|---|
| \(R \times S\) | cartesian product of relations \(R\) and \(S\) (with any domains and codomains) |
| \(R + S\) | disjoint union of relations |
| \(R \wedge S\) | conjunction of relations \(R\) and \(S\) (with equal domains and codomains) |
| \(R \vee S\) | disjunction of relations |
| \(\top_{X,Y}\) | total relation between two sets \(X\) and \(Y\) |
| \(\bot_{X,Y}\) | empty relation between two sets \(X\) and \(Y\) |
| \(\top R\) | the set underlying or tabulating a relation \(R\) |
| \(f_!\) | graph of a function \(f\) |
| \(f^*\) | cograph of a function \(f\) |
| \(\Delta_X: X \to X \times X\) | diagonal map for a set \(X\) |
| \(\nabla_X: X+X \to X\) | codiagonal map for a set \(X\) |
With the categorical philosophy now fully at work, we find that operations that must be taken as primitive in traditional approaches to relational algebra are now derived just by postulating a few basic notions of composition and invoking suitable universal properties.4 Moreover, the universal properties suggest a simple and elegant axiomatization of relations, which Michael Lambert has supplied in his paper on double categories of relations (Lambert 2022).
During a summer at Topos Institute, Michael and I worked on applying these ideas to relational databases. He summarized our work in a blog post that makes good further reading for this one. Double-categorical databases are an idea that I hope to revisit in the future.
Summary and outlook
The question originally posed can now be refined to:
How can the algebra of relations be deduced from universal properties?
Double categories provide the answer. This is the first sense in which I will argue that double categories are inevitable: it seems to me that any attempt to answer this question will eventually lead to the idea of a double category or some variant of it.
While elegance is always desirable, choosing axioms is about more than aesthetics. A good set of axioms suggests fruitful generalizations and brings out the unity of mathematics. In the case of relations, we often prefer to use spans instead. Spans are more easily internalized than relations in categories besides \(\mathsf{Set}\), and, contrary to popular belief among database theorists, spans are a more faithful model than relations of SQL databases. Generalizing bicategories of relations to cartesian bicategories so as to encompass spans is a serious endeavor.5 By contrast, the central concept in a double category of relations, that of a cartesian equipment, applies just as easily to spans as to relations. So not only do double categories reconstruct the algebra of relations from universal properties, they put relational algebra into a broader context in which it can be precisely compared with other ideas. That’s what category theory is all about.
References
Footnotes
For the category theorists: I omit from this list the calculus of relations in a regular category because it is a construction, not a theory. Indeed, relations in a regular category are a prime example intended to be captured by both allegories and bicategories of relations.↩︎
The book chapter by Coecke and Paquette (2010) remains an excellent introduction to monoidal categories, and not just for physicists.↩︎
You might think that the functions are already there, since they are a special kind of relation! While that’s true in a sense, the behavior of a category depends on the totality of its morphisms. A category can be ill behaved because it has “too few” morphisms but also because it has “too many.”↩︎
If you’ve heard about categorical logic, you might know that Lawvere achieved a reconstruction of first-order logic through universal properties in his program on “adjointness in foundations”. His approach is similar in spirit to the one for relational algebra described here.↩︎
Explaining why would require a longer technical discussion, but that there are difficulties can be inferred from the long gap between the publication of the original paper on bicategories of relations (Carboni and Walters 1987) and its sequel (Carboni et al. 2008).↩︎