Condensation of semirings

Every semiring is canonically associated to a minimal congruence with naturally ordered quotient, which can be defined by the additive J classes of the semiring. The quotient by this minimal congruence is the condensation of $S$.

The condensation theory of semirings
All the basic ingredients in this proof are available in any basic text on semiring theory. The fundamental breakthrough here is just a result in a change in thinking related to semiring congruences.

Theorem. let $S$ be a semiring and let $H$ be the Green's $H$ relation of the additive monoid $+$ of $S$, then $H$ forms a semiring congruence of $S$.

Proof. let $a,b,c,d \in S$ with $a H b$ and $c H d$. Then by the definition of the Green's $H$ relation there exist elements $x_1,x_2,y_1,y_2$ such that \[ a + x_1 = b \] \[ a = b + y_1 \] \[ c + x_2 = d \] \[ c = d + y_2 \] We can now demonstrate that $(a + c) \space H \space (b + d)$ by a simple process of substitution: \[ a + c = b + d + y+1 + y_2 \] \[ b + d = a + c + x_1 + x_2 \] To demonstrate that $ac \space H \space bd$ we can simply use the distributive law once after substitution: \[ ac = (b + y_1)(d+ y_2) = bd + by_2 + dy_1 + y_1y_2 \] \[ bd = (a + x_1)(c + x_2) = ac + ax_2 + cx_1 + x_1x_2 \] The fact that $a H b$ and $c H d$ both imply that $a + c \space H \space b + d$ and $ac \space H \space bd$ means that $H$ is both an additive congruence and a multiplicative congruence. It follows that it is a semiring congruence. $\square$

Definition. let $S$ be a semiring and let $H$ be the $H$ classes of its additive monoid then the condensation of $S$ is the quotient $\frac{S}{H}$.

The additive monoid of $S$ is its condensation on the level of semigroup theory, so it is not hard to see that it is a $J$ trivial. This is equivalent to saying that $S$ is a naturall ordered semiring.

Corollary. $\frac{S}{H}$ is a naturally ordered semiring

This condensation mapping $\pi : S \to \frac{S}{H}$ is characterized by a universal property in the sense of category theory.

Corollary. let $S$ be a semiring then any mapping $f$ from $S$ to a naturally ordered semiring $R$ filters through the condensation homomorphism $\pi : S \to \frac{S}{H}$ by a unique morphism $m$. General structure theory of semirings:
This condensation theorem for semirings is the most general tool we have for defining a general structure theory for semirings. This is applicable to any semiring, and it characterizes the relationship between its order theoretic and algebraic properties.

* Every semiring is an extension of a partially ordered semiring.

The only case when the partial order doesn't matter is the case in which is trivial, which is rings. For a ring $R$ it is clearly the case that all elements are additively related, so its quotient is the trivial semiring. Every semiring has a maximal subring, which is generated by the set of all elements with additive inverses.

References:
semiring in nLab

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.

Matrix algebras of distributive lattices

Let $L$ be a bounded distributive lattice, then $L$ is also a semiring. The idempotent semiring of matrices $Mat_n(L)$ has a natural presentation as an ordered algebraic structure, by its own additive partial order. Given a representation of $L$ by a family of sets then $Mat_n(L)$ consists of set valued matrices. Set valued matrices can then be defined by products of relation algebras.

Matrix semiring of $T_2$
The composition of two relations $R \circ S$ on a set $X$ is a relation whose entries $(a,b) \in R \circ S$ are defined by: \[ \exists x : (a,x) \in S, (x,b) \in R \] Which can be expressed as a distributive lattice polynomial: \[ \bigvee_{x \in X} (a,x) \in S \wedge (x,b) \in R \] This distributive lattice polynomial corresponds to the inner product of $T_2$ valued vectors, and thus it consists of terms of the product of $T_2$ valued matrices. Thus, \[ Rel \cong Mat(T_2) \] In order to produce a proper correspondence, it is necessary to consider the different types of composition ordering and matrix representations. The most common representation of relations by matrices, uses the row-first approach. In that case, the relation algebra might correspond to the opposite semiring.

Set-valued matrices:
In order to construct a more general theory of matrices over distributive lattices, it is necessary to first construct a set-theoretic representation of $L$. \[ f : L \to \wp(X) \] This invites us to consider the theory of set-valued matrices. In these cases, the distributive lattice describing the combination of set vectors $U,V$ with indices in $I$ is: \[ U \cdot V = \bigcup_{i \in I} U_i \cap V_i \] In that case, the membership of $x$ in the above set is a distributive lattice polynomial in $T_2$ \[ x \in U\cdot V = \bigvee_{i \in I} x \in U_i \wedge x \in V_i \] This suggests that the composition of set-valued matrices in $Mat_n(L)$ is a product of compositions of relation compositions in $Mat_n(T_2)$. This leads to the theory of relation decompositions.

Example. let $S = {a,b,c}$ \[ \begin{bmatrix} \{a\} & \{a,b\} & \{b\} \\ \{a,c\} & \{a\} & \{a,b\} \\ \{c\} & \{a,c\} & \{a\} \end{bmatrix} \] We can split this up into three adjacency matrices $M_a,M_b,M_c$. \[ M_a = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{bmatrix} , M_b = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}, M_c = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{bmatrix} \] This turns $M$ into an indexed family of relations. Then composition of matrices in $Mat(L)$ then simply becomes the composition of a product of relations.

The matrix algebra:
Let $L$ be a distributive lattice, with set theoretic representation $f : L \to \wp(S)$. Then we can naturally turn any $L$ matrix into a $S$ indexed family of relations, whose composition is the componentwise composition of relations. If $L$ is a finite boolean algebra, then this is equivalent to a product of relation algebras.

In the case that $L$ is not a boolean algebra, such as the ordered triple $T_3$ which has set theoretic representation $\emptyset, \{a\},\{a,b\}$ then we get an indexed family of relations $\{R_a,R_b\}$ except with the condition that $R_b \subseteq R_a$, so that matrices over $T_3$ are a totally ordered family of relations. The specialization order of the set theoretic representation corresponds to the inclusion ordering of the relation decomposition of the matrix representation.

The matrix semiring construction provides order-theoretic foundations for the relation algebra. The relation algebra $Rel$ can be construed as the matrix semiring over the ordered pair $T_2$, the simplest non-trivial case of a matrix semiring over a distributive lattice.

Category theory typically deals with the composition of morphisms one at a time, this problem is dealt with by the use of idempotent semirings. This provides a matrix theoretic representation for the simplest of these semirings, the semiring of families of morphisms of a complete thin groupoid.

Additive preorders of semirings

Semirings come from two major sources: classical ring theory and ordered algebraic structures. Every semiring $R$ is associated with an additive preorder: the natural increasing action preorder of the commutative additive monoid of $R$. This has $a \sqsubseteq b \Leftrightarrow \exists c : a+c = b$. This breaks up semirings into two basic classes: those whose additive preorders are symmetric and those whose preorder are antisymmetric.

Those semirings with symmetric preorder are precisely rings. To see this, notice that all J-total monoids are groups. on the other hand, it can be shown that semirings with antisymmetric preorder are ordered algebraic structures. This divides semirings along the lines that they most apppear in applications. Beyond these there are all the in between cases. The additively ordered semiring $\mathbb{N}$ is a special case, because although it is additively J-trivial it is also cancellative so that it can be embedded in a ring $\mathbb{Z}$. Most additively ordered semirings, such as the idempotent semirings emerging from quantales, cannot be embedded in rings under any circumstances. Numerical semigroups are also cancellative, commutative, and J-trivial, so they are another source of addition of semirings of this type.

Semirings with antisymmetric addition also emerge from classical ring theory. The ideals of a commutative ring form an idempotent semiring by the addition and multiplication of ideals. Radical ideals form a bounded distributive lattice $Spec(R)$ which means that they can also be represented as semirings under their lattice operations.

Theorem. let $R$ be a semiring with additive preorder $\sqsubseteq$. Then addition and multiplication are both monotone over this preorder.

Proof. (1) suppose $a \sqsubseteq b$ then $a+c = b$. Let $d$ be another element, then $(d+a)+c = (d+b)$ so $d+a \subseteq d+b$ by $c$.

(2) suppose $a \subseteq b$ then $a+c = b$. Let $d$ be another element, then $d(a+c) = da + dc = db$ so $da\subseteq db$ by $dc$. $\square$

By the preceding theorem, every semiring is a preordered algebraic structure. This is even true in the case of rings, it is just that the additive preorder on rings is the complete relation, and every map to a complete relation is monotone. Complete preorders are maximal in the hom class comparison ordering induced by underlying set functor.

In the more interesting case, when the semiring is not a ring, this turns any semiring into a preordered algebraic structure. Further, every semiring with antisymmetric preorder is an ordered algebraic structure. $\mathbb{N}$ is a good first example: both addition and multiplication are monotone over the additive ordering of the natural numbers. This is the subject of a corollary.

Corollary. let $R$ be a semiring with additive partial order $\sqsubseteq$. Then $R$ is an ordered semiring with respect to its additive ordering.

This covers the second basic case of semirings besides rings: those emerging from ordered algebraic structures. This idea neatly divides semirings into two basic classes: rings and ordered semirings. The other semirings have a mix of symmetry and antisymmetry of some kind.

Idempotent semirings are a very promising case, because they allow us to define all kinds of algebraic operations on sets: such as the arithmetic of ideals of semigroups and rings and the composition of morphism systems of a category. The use of idempotent semirings in category theory gets around the use of partial operations. There are also links between idempotent semirings, quantales, and hyperoperations that could be of use in number theory.

Categorical approach to relation algebra

In the same way that composition of morphisms in a category is an extension of the composition in a preorder the composition of sets of morphisms is an extension of relation algebra. The relation algebra on a set is the quantale of morphism systems of the complete thin groupoid. As a result, morphisms are enriched ordered pairs and morphism systems are enriched relations.

The composition of morphism systems in a category is simply the set of all compositions of morphisms in each set, whenever they exist. If there are no compatible morphisms then the empty set is returned. Aside from the empty compositions, the quantale of morphism systems is similar to the quantales of sets of other algebraic structures.

Semiring of morphism systems:
Let $C$ be a category and $F,G$ families of morphisms in $C$. Then $F \circ G$ is the composition of all morphisms in $F$ and $G$ whenever they exist. This can be expressed in symbols as: \[ \bigcup_{m \in F, n \in G} \left\{ \begin{array}{ll} \emptyset & \text{Input}(m) \not= \text{Output}(n) \\ \{m \circ n\} & \text{otherwise} \end{array} \right. \] The resulting structure $(\wp(Arrows(C)),\circ)$ is a monoid with identity $I$ equal to the family of all identity morphisms of the category $C$. The composition function of a category has existence associativity, so that if $(ab)c$ exists then so does $a(bc)$ and then they both coincide. Therefore, the composition of morphism systems is also associative.

A corresponding semilattice structure $(\wp(Arrows(C)), \vee)$ can be defined by the union of morphism systems. This is a unital semilattice, by the fact that $\emptyset$ is an identity with respect to unions. In order to show that $\wp(Arrows(C))$ is a semiring, we only now need to show that these two monoids are related to one another.

Theorem. $(\wp(Arrows(C)),\vee,\circ)$ is a semiring

Proof. for the sake of notation it is convenient to replace the piecewise description of the composition of two morphisms by the composition of two singleton sets $\{m\} \circ \{n\}$. Then we can simply the rewrite the definition of composition, moving around the unions a little in order to get distributivity. \[ F \circ (G \cup H) \] \[ \bigcup_{m \in F, n \in G \cup H} \{m\} \circ \{n\} \] \[=\bigcup_{m \in F} ( \bigcup_{n \in G \cup H} \{m\} \circ \{n\} )\] \[=\bigcup_{m \in F}( ( \bigcup_{n \in G } \{m\} \circ \{n\}) \cup ( \bigcup_{n \in H} \{m\} \circ \{n\})) \] \[ = F\circ G \cup F \circ H \] It follows that $F\circ(G \cup H) = F\circ G \cup F \circ H$, the other distributive law $(F \cup G) \circ H = F \circ H \cup G \circ H$ follows by exactly the same reasoning. In order to confirm the structure is a semiring, we finally need to demonstrate that the additive identity $\emptyset$ is a multiplicative zero. In fact it is, because $\emptyset \circ A = A \circ \emptyset = \emptyset$. It follows that $\wp(Arrows(C))$ is a semiring $\square$

The relationship between the semiring of a category and its partial semigroup, is that the semiring is a multi-valued extension of the ordinary composition of morphisms. In particular, the composition function of a category $(C,\circ)$ can be recovered as a partial semigroup from the subset of the composition monoid of morphism systems consisting of all singleton morphism systems.

The composition of singleton morphisms in the case where no composition exists is the empty set. The partiality of the composition function of a category can be gotten around by adjoining a zero element. This is not necessary when the category $C$ is a monoid.

Semiring of relations:
Let $K_X$ be the complete thin groupoid on $X$. Then the morphisms of $K_X$ are ordered pairs $(a,b)$ and composition of ordered pairs $(a,b)$ and $(b,c)$ is $(a,c)$. Then since morphisms are ordered pairs, morphism systems are relations. Then the composition of relations is a special case of the composition of families of morphisms in a category: \[ R \circ S = \{ (a,c) : \exists (a,b) \in S, (b,c) \in R : (a,b) \circ (b,c) = (a,c) \}\] It follows that $(\wp(Arrows(K_X)),\circ)$ is equal to the composition of relations, and so relation algebra can be recovered by the composition of families of morphisms in a category. By the preceding theorem, $(\wp(Arrows(K_X)),\vee,\circ)$ is also a semiring as a special case of a family of morphism systems of a category.

The semiring congruence of a category:
The composition of morphism systems of a category is an extension of the composition of relations. The semiring of morphism systems of a category extends relation algebra on the semiring level.

Definition. let $F \in \wp(Arrows(C))$ be a morphism system of a category $C$. Then the underlying binary relation $T(F)$ is the subset of $\wp(Ob(C)^2)$ consisting of all ordered pairs of objects in the morphisms of $F$. \[ T : \wp(Arrrows(C)) \to \wp(Ob(C)^2) \] Theorem. let $C$ be a category then the underlying binary relation forms a congruence of the composition of morphism systems.

Proof. let $F,G$ be morphism systems with underlying binary relations $R,S$. Then if $m : A \to C \in F \circ G$ we have that there exists $f : B \to C$ in F and $g : A \to B$ in G such that $m = f \circ g$. Then $(B,C) \in R$ and $(A,B) \in S$ implies $(A,C) \in R \circ S$. In the other direction, suppose that $(A,C) \in R \circ S$ then there exists $f : B \to C$ and $g : A \to B$ such that $f \circ g : A \to C$, so that $(A,C)$ is in the underlying binary relation of $F \circ G$. $\square$

Theorem. let $C$ be a category then the underlying binary relation forms a congruence of the union of morphism systems.

Proof. let $F,G$ be morphism systems with underlying binary relations $R,S$. Then if $m : A \to B$ is in $F \cup G$ then either (1) $m \in F$ in which case $(A,B) \in R$ or (2) $m \in G$ in which case $(A,B) \in S$. Therefore, $(A,B) \in R \cup S$. In the other direction, every ordered pair in $R \cup S$ is an ordered pair of $F \cup G$, so the two coincide. $\square$

Corollary. the underlying binary relation forms a congruence of the semiring of morphism systems of a category.

The fact that the underlying binary relation is a semiring congruence, means that we can say that the composition fo morphism systems in a category is an extension of relation algebra. This is formalized by a semiring homomorphism.

Theorem. $T : \wp(Arrrows(C)) \to \wp(Ob(C)^2)$ is a semiring homomorphism from the semiring of homomorphisms of a category to the semiring of relations.

Proof. the function $T$ is defined by the image functor so it is a union homomorphism. $T(\emptyset = \emptyset)$ so $T$ also preserves additive identities. Finally, each morphism in $R \circ S$ is some composite $g \circ f : A \to C$ with $f : A \to B \in S$ and $g : B \to C \in R$ such that $(A,B) \in T(S)$ and $(B,C) \in T(R)$ so $(A,C) \in T(R) \circ T(S)$. Then in the other direction, $T(R) \circ T(S)$ is all ordered pairs $(A,C)$ such that there is a morphism $f: A \to B \in R$ and a morphism $g : B \to C \in S$ then $g \circ f \in R \circ S$ so $(A,C) \in T(R \circ S)$. Therefore, $T(R \circ S) = T(R) \circ T(S)$. $\square$

The equivalence classes of $T$ do not form intervals, so the underlying binary relation cannot form a lattice congruence. It suffices then to show that they form a semiring congruence, which we have done here.

Relation algebra:
The definition of the composition of morphism systems is based upon the union of the compositions of each individual pair of morphisms, so that composition can be union decomposed. Therefore, $\wp(Arrows(C))$ clearly forms a quantale for any category $C$ but this isn't enough to recover the full relation algebra structure. In order to do that we must recall that $K_X$ is a groupoid. \[ R^{-1} = \{ m^{-1} : m \in R \} \] The inverse of a morphism system of a groupoid is simply the set of inverses of each of its morphisms. With this groupoid-theoretic characterization we have a full characterisation of the relation algebra: $(S,\vee,\wedge, 0,1,\circ,I,-)$.

• $\vee,\wedge$ are the union and intersection of relations. $0$ is the empty relation and $1$ is the complete relation.
• $\circ$ is the composition of morphism systems
• $I$ is the set consisting of all identity morphisms
• $R^{-1}$ maps each morphism to its inverse

The residuals $R \triangleleft S$ and $R \triangleright S$ are $R \circ S^{-1}$ and $R^{-1} \circ S$, and so they are special cases of operations that can be defined for any morphism system of a groupoid. This turns the relation algebra of the complete thin groupoid into a residuated boolean algebra.

We can relate the relation algebra to general categories by the underlying binary relation congruence. In the special case of the morphism system of a groupoid, this also forms a unary congruence of the inverse operation.

Theorem. let $C$ be a groupoid with inverse operation $^{-1} : Ob(C) \to Ob(C)$. Then $T(R^{-1}) = T(R)^{-1}$. The underlying binary relation of the inverse of a morphism system, is the inverse of its underlying binary relation.

Proof. let $f : A \to B$ be a morphism in a groupoid it has ordered pair $(A,B)$ which has inverse $(B,A)$. Its inverse is $f^{-1} : B \to A$ which has ordered pair $(B,A)$ so the two coincide. This then applies to morphism systems on the level of images by these functions. $\square$

Although the morphism systems of categories always extend relations, the special properties of the relation algebra come from their embedding in a groupoid.

Properties of relations:
The properties of relations, expressed in relation algebra, are analogous to those which can be expressed in any category. The morphism system of a subsemigroupoid can be expressed by the condition: \[ R^2 \subseteq R \] The condition $R^2 \subseteq R$ in any quantale expresses composition closure. In a monoid, this defines subsemigroups of the monoid, but in the relation algebra this defines a transitive relation. Categories are basic extensions of transitivity, so transitive relations can be defined like this. The dual condition is: \[ R \subseteq R^2 \] This means that a given morphism system is self-factorizable. The idempotents of $\wp(Arrows(C))$ are clearly all morphism systems that satisfy both conditions. Relation composition forms an ordered semigroup, so that composition is bimonotone. In a number of cases it is also increasing.

When $R$ is reflexive so that $I \subseteq R$ then clearly $R$ is increasing. The same is true of morphism systems of a category with respect to the identity $I$. We have $I \subseteq R$ means that $R \circ S \subseteq R \circ I = R$ and $S \circ R \subseteq I \circ R = R$. The dual condition $I \cap R = \emptyset$ defines irreflexivity. Finally, coreflexive relations $R \subseteq I$ form a distributive lattice subsemiring.

Theorem. coreflexive relations $R \subseteq I$ form a distributive lattice subsemiring.

Proof. (1) union closure follows from the fact that $R \subseteq I$ is a principal down set, as does the membership of $\emptyset$. (2) two loop edges (a,a) are only composable when they are equal, so the composition of coreflexive relations is intersection which is again closed because $R \subseteq I$ forms a principal down set. This means multiplication is a semilattice, so that as a semiring the coreflexive relations form a distributive lattice. $\square$

Systems of identity morphisms still form a distributive lattice subsemiring in any category. The other properties of relations require the use of the inverse, which means that they are only applicable to a groupoid.

• Symmetric : $R^{-1} = R$
• Antisymmetric : $R^{-1} \cap R \subseteq I$
• Functional : $R^{-1} \circ R \subseteq I$
• Inverse functional: $R \circ R^{-1} \subseteq I$

Symmetry corresponds to inverse closure in a groupoid. Clearly, the combination of symmetry, transitivity, and reflexivity defines wide subgroupoids. In the case of of the complete thin groupoid $K_X$ we already know that this corresponds to the lattice $Part(A)$.

Corollary. the lattice $Part(A)$ is isomorphic to the family of morphism systems of the complete thin groupoid that satsify $I,R^{-1},R^2 \subseteq R$.

We see how a number of concepts like subsemigroupoids, wide subcategories, and wide subgroupoids can be defined by the algebra of morphism systems. In the case of wide thin groupoids, these create the familar classes of relations.

Subsemigroups of relations:
Every relation algebra is associated with the following composition subsemigroups: $PT_X$ consisting of all partial transformations, $PS_X$ the symmetric inverse semigroup of charts, $T_X$ the full transformation monoid, and the symmetric group $S_X$ of permutations. Each of these subsemigroups is a suborder of $Rel$. The full transformation monoid and the symmetric group form antichains, so we can ignore them for now. On the other hand, $PT_X$ and $PS_X$ both have non-trivial partial orders so we would like to relate the order on them to their semigroups.

Recall that coreflexive relations form a distributive lattice subsemigroup. Let $E$ be the composition subsemigroup of coreflexive relations of $Rel$. The composition of coreflexive relations is decreasing, so its action preorder is a suborder of the dual of the inclusion order of relations.

Input composition by a coreflexive relation is a domain restriction and output composition is codomain restriction. Thusly, the decreasing left actions by $E$ form domain restrictions of relations, which can be used to recover the inclusion ordering of $PT_X$ and $PS_X$. The natural ordering of an inverse semigroup in this context is the same as the inclusion ordering of relations.

Lattice ordered semimodules of multisets

The free commutative monoid $F(S)$ on a set $S$ consists of all multisets on $S$. This has a natural semiring action by $\mathbb{N}$, so $F(S)$ is a semimodule. The algebraic preorder of $F(S)$ is not only a partial order, since $F(S)$ is J-trivial, but it also a lattice.

Commutativity and semimodule theory:
A semiring action on a commutative monoid is defined by a structure preserving map from $R$ to $End(M)$. This requires that three conditions must be satisfied:

• Action: $(ab)^n = a^nb^n$
• Additivity $a^n a^m = a^(n+m)$
• Multiplicativity $(a^n)^m = a^{nm}$

Every commutative monoid is a $\mathbb{N}$ semimodule. In a non-commutative monoid we can get the last two conditions, but we cannot get the first. Thusly, the techniques of semimodule theory cannot be applied to non-commutative monoids.

Commutativity and lattice theory:
The algebraic preordering of the free commutative semigroup is a lattice. This provides a natural link between commutative operations and lattices. Additionally, it is a distributive lattice of multisets.

On the other hand, the algebraic preordering on a non-commutative free semigroup is in general not a lattice. It is a partial order which orders lists by consecutive subsequences. Thusly, the techniques of lattice theory cannot be applied to non-commutative monoids. It seems that the lattice ordered semimodule structure is something that can only be applied in the commutative case.

Examination of the ordered algebraic structure:
An ordered monoid is an internal monoid in the category of preorders and monotone maps. It is not hard to see that $(\mathbb{N},\le,+)$ is an ordered monoid, but it has the stronger property that its action is biextensive. This naturally trasfers to the free commutative monoid $(F(S),+)$.

• Monotone: $\forall a,b,c : a \leq b \implies a+c \leq b+c$
• Biextensive: $\forall a,b : a \leq a + b$

The commutative monoid of all multiset addition actions is a submonoid of the monoid of all increasing monotone actions on the distributive lattice of multisets. We can therefore say that $F(S)$ is not only an ordered semimodule, its actions are also increasing.

Linear maps:
Recall from basic list processing, that mapcat replaces each element of a list with another list and then concatenates them all together. The corresponding operation over multisets is the unordered mapcat, which takes any element of a multiset and replaces it with another multiset, then adds them altogether.

The linear maps of free commutative semimodules $m : F(S) \to F(T)$ are precisely those defined by some unordered mapcat function $f : S \to F(T)$ that takes each element of the underlying set to a multiset in $F(T)$. This is also a monotone map of ordered semimodules. Therefore, the category of ordered semimodules can be used to understand the maps of free commutative monoids.