Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Rel has biproducts, and this is weird

Martin Brandenburg (Mar 21 2026 at 09:00):

I have just noticed that the category of sets with relations as morphisms has biproducts. Which is really weird. I mean it is easy since products are "virtually the same" as coproducts in this category, but I always thought that biproducts are meant for "module-like" categories. Thoughts?

David Michael Roberts (Mar 21 2026 at 10:20):

Isn't a relation something like a bimodule?

Tobias Fritz (Mar 21 2026 at 11:25):

This is perhaps best understood by noting that Rel is equivalent to the category of finitely generated free modules over the Boolean semiring $\mathbb{B} = \{0,1\}$, where $1 + 1 = 1$. To see this, note that such a morphism is a matrix of elements of $\mathbb{B}$, which can be seen as a relation, and matrix multiplication corresponds to relational composition thanks to $1 + 1 = 1$.

Martin Brandenburg (Mar 21 2026 at 13:25):

David Michael Roberts said:

Isn't a relation something like a bimodule?

Yes, but relations are the morphisms here, not the objects.

Martin Brandenburg (Mar 21 2026 at 13:26):

Tobias Fritz said:

This is perhaps best understood by noting that Rel is equivalent to the category of finitely generated free modules over the Boolean semiring [...]

This is very nice!

Oscar Cunningham (Mar 21 2026 at 13:52):

By the way, I don't think we want 'finitely generated' here. That would give us relations between finite sets only. Rel was defined above as having general sets as objects. Note that unlike usual linear algebra it's okay to add infinitely many 0s and 1s. The sum is just 0 if all of the terms are 0, and 1 if any of the terms are 1.

John Baez (Mar 21 2026 at 14:10):

Indeed linear algebra has common features working over any rig: for any rig $R$ the category of $R$-modules has biproducts. So does the category of free finitely generated $R$-modules, and when $R$ is the boolean rig $\mathbb{B} = \{0,1\}$ then this is the category of finite sets and relations.

There's a wonderful class of rigs where infinite sums are allowed, making linear algebra over these rigs better behaved. These are the [[quantales]]: the cocomplete posets equipped with a monoidal structure that distributes over all colimits. These become rigs where we can add up any number of elements by taking their coproduct (aka "supremum" aka "least upper bound"), and multiply any finite number of elements using the monoidal structure.

A good example is the tropical rig $[0,\infty)$ with the reversed order, so that addition (aka coproduct aka "supremum") is actually the infimum, where we define multiplication to be addition. While royally confusing at first, linear algebra over this rig is very nicely connected to minimization problems, so there was an even a conferencce Tropical Mathematics & Optimisation for Railways, held at the University of Birmingham, School of Engineering, on Monday 18 June 2018. Unfortunately nobody I know was able to attend.

$\mathbb{B}$ is even better than a quantale, because not only is it a cocomplete poset where addition given by sup, it's a complete poset where multiplication is given by inf. Thus, infinite sums and infinite products always converge, and we're in a kind of dream world when doing linear algebra over $\mathbb{B}$. This is the category of relations.

John Baez (Mar 21 2026 at 14:12):

I'm not sure I've seen a lot about the correct general concept of "module" over a quantale, which generalizes the axioms involving addition to allow infinite sums. I'm probably just forgetting it.

Nathanael Arkor (Mar 21 2026 at 16:35):

Viewing Rel as a double category, the fact that it has biproducts is a consequence of the fact it has well behaved coproducts, along with companions and conjoints: see Theorem 5.10 of @Evan Patterson's Transposing cartesian and other structure in double categories. This is a common phenomenon with double categories of bimodules/relations (e.g. Dist also has biproducts).

Joe Moeller (Mar 21 2026 at 17:13):

I remember being obsessed with this question. Specifically I wanted to understand why Grp has separate product and coproduct and no tensor product, but then Ab has biproducts and a tensor product. I wanted an explanation for that change happening that also applied to Set vs Rel. I think I felt satisfied after reading Anders Kock's papers on monoidal monads etc.

Jean-Baptiste Vienney (Mar 21 2026 at 21:02):

Oscar Cunningham said:

By the way, I don't think we want 'finitely generated' here. That would give us relations between finite sets only. Rel was defined above as having general sets as objects. Note that unlike usual linear algebra it's okay to add infinitely many 0s and 1s. The sum is just 0 if all of the terms are 0, and 1 if any of the terms are 1.

I think that Rel is not even equivalent to the category of free modules over $\mathbb{B}=\{0,1\}$. A relation $R$ from $X$ to $Y$ can relate an element $x \in X$ to an infinity of elements in $Y$ while a linear map from $\mathbb{B}^{(X)}$ (the set of families $(u_x)_{x \in X} \in \mathbb{B}^X$ such that $u_x=0$ for all but finitely many $x \in X$) to $\mathbb{B}^{(Y)}$ can only send $x$ to $\sum_{y \in A}y$ for a finite subset $A$ of $Y$.

I tink that the category of free modules over $\mathbb{B}$ is equivalent to the wide subcategory of Rel made of the relations $R$ from $X$ to $Y$ such that each $x \in X$ is related to finitely many elements in $Y$. So Rel can be seen as a bigger category than the category of free modules over $\mathbb{B}$ where a basis element can be sent to an infinite sum of basis elements.

Oscar Cunningham (Mar 21 2026 at 21:17):

Right. One way to say it is that Rel is equivalent to the category of free sup-lattices. A sup-lattice isn't literally a $\mathbb{B}$-algebra. It's an upgraded version where you're allowed to sum (i.e. sup) infinitely many things.

David Michael Roberts (Mar 21 2026 at 21:18):

@Martin Brandenburg bimodules between some kind of algebras.

David Michael Roberts (Mar 21 2026 at 21:19):

Sorry that was implicit, I should have specified

Graham Manuell (Mar 22 2026 at 10:48):

John Baez said:

I'm not sure I've seen a lot about the correct general concept of "module" over a quantale, which generalizes the axioms involving addition to allow infinite sums. I'm probably just forgetting it.

These have definitely been studied under the unsurprising name of quantale module.

Damiano Mazza (Mar 22 2026 at 11:24):

This paper by Laird, Manzonetto, McCusker and Pagani considers continuous semirings, which maybe are special cases of quantales? Given a continuous semiring $R$, they consider its "free biproduct completion", which is the category of "small" matrices on elements of $R$ (small in the sense that they are indexed by arbitrary sets, not just finite sets). As Jean-Baptiste points out, there is no requirement on the columns of these matrices to be almost everywhere zero, so these are more than just categories of free modules. Composition is well-defined because all small sums exist in a continuous semiring. These categories always have small biproducts and $\mathbf{Rel}$ is obviously a special case, as already observed.

They briefly mention the notion of "continuous module" over a continuous semiring, but do not expand on it. I suppose that these free biproduct completions may be seen as categories of free continuous modules.