Semigroup semirings of multirelations

There are two main types of semigroup semiring used in relation theory: $\mathbb{N}F^{\to}(S)$ and $T_2F^{\to}(S)$. The former is the semiring of multirelations on a set constructed by the semiring $\mathbb{N}$, and the later is the semiring of relations constructed by the lattice semiring $T_2$.

• The semiring of multirelations: $\mathbb{N}F^{\to}(S)$
• The semiring of relations: $T_2 F^{\to}(S)$

Multirelations are a concept that is highly familiar to us, for example from the topos of quivers we can always get a binary multirelation. There is a further a functor from the category of categories $Cat$ to quivers, which lets us produce a binary multirelation from any category, but semigroup semirings of relations and multirelations are distinguished by the fact that their members do not have restricted arity.

The product of binary relations in a semigroup semiring is typically a quaternary multirelation, because the members of the resulting quaternary multirelation are defined by piecewise concatenation in their respective constituents. Semigroup semirings of multirelations are sort of like free rings in their construction by the free monoid. An interesting property of these semirings is that they are additively J-trivial and non-commutative.

Proposition. let $S$ be a non-trivial set then the semigroup semiring of multirelations $\mathbb{N}F^{\to}(S)$ is an additively J-trivial non-commutative semiring

Additively J-trivial semirings are interesting because they are inherently partially ordered algebraic structures. Indeed, their is a monomorphism of categories from additively j-trivial semirings to partially ordered semirings. Every semiring homomorphism is inherently monotone over J-preorders, so additively J-tivial semiring morphisms are morphisms of ordered semirings.

Idempotent semirings on the other hand abound. For example, the semiring of morphism systems of a semigroupoid is an infinite source of idempotent non-commutative semirings. So in that sense, $T_2F^{\to(S)}$ is just another non-commutative idempotent semiring and probably not as interesting as the semiring of multirelations.

Proposition. let $S$ be a set then the semigroup semiring of relations $T_2F^{\to}(S)$ is an idempotent non-commutative semiring.

One final semiring constuction related to relations is worth mentioning, which is the semiring of relations on a set which is isomorphic to the semiring of morphism systems of the complete thin groupoid. A notable difference between this and the semigroup semiring constructions is that it has restricted arity because it is not defined over a free monoid. The symmetric inverse semigroup, symmetric group, etc all embed in the multiplicative semigroup of relations.