nLab FinRel




FinRelFinRel is the category of finite sets and all relations between them: the full subcategory of Rel on finite sets. Like Rel, FinRel can also be seen as a 2-poset, and a cartesian bicategory.


As a category of matrices

FinRelFinRel is equivalent to Mat(Bool)Mat(Bool), the category whose objects are natural numbers and where a morphism f:mnf \colon m \to n is an n×mn \times m matrix with entries in the semiring of booleans, Bool={F,T}Bool = \{F,T\}, where addition is the logical operation “or” and multiplication is “and”.

For any semiring RR, the category Mat(R)Mat(R) has biproducts, corresponding to addition of natural numbers, and the initial object 00 is also terminal (hence is a zero object). For any commutative semiring RR, Mat(R)Mat(R) also has another symmetric monoidal structure: a tensor product with mn=mnm \otimes n = m n, which distributes over biproducts. Thus FinRelFinRel has all these properties.


We can define bimonoids in any symmetric monoidal category: roughly, a bimonoid is a monoid and comonoid in a compatible way. A bimonoid is said to be special if comultiplication followed by multiplication is the identity, and bicommutative if it is both a commutative monoid and a cocommutative comonoid.

In a category with biproducts and a zero object, every object cc is a bicommutative bimonoid where the multiplication is the fold map :ccc\nabla \colon c \oplus c \to c and the comultiplication is the diagonal Δ:ccc\Delta \colon c \to c \oplus c. Thus, every object of FinRelFinRel is a bicommutative bimonoid. One can easily check that it is also special.

But something stronger is true. FinRelFinRel made symmetric monoidal with biproducts is the free symmetric monoidal category on a special bicommutative bimonoid. That is, given a symmetric monoidal category CC and a special bicommutative bimonoid object cCc \in C, there is symmetric monoidal functor F:FinRelCF \colon FinRel \to C, unique up to monoidal natural isomorphism, mapping 1FinRel1 \in FinRel together with its bimonoid operations to cc and its bimonoid operations.

This is conveniently expressed in the language of PROPs: Mat(Bool)Mat(Bool) is the PROP for special bicommutative bimonoids. This is Theorem 7.2 in Coya-Fong 17, based on techniques from Lack 04.


  • Steve Lack, Composing PROPs, Theory and Applications of Categories 13(9):147–163, 2004. (pdf)

  • Brandon Coya and Brendan Fong, Corelations are the prop for extraspecial commutative Frobenius monoids, Theory and Applications of Categories, Vol. 32, 2017, No. 11, pp. 380-395. (arxiv)

category: category

Last revised on October 23, 2020 at 03:59:59. See the history of this page for a list of all contributions to it.