Multiset addition semigroups

The class of all multisets on a set forms a semigroup $F(S)$ with multiset addition as its operation. The additive property of $F(S)$ is formalied by a semigroup homomorphism $f : F(S) \to \mathbb{N}$ which maps each multiset to its cardinality. Given a free commutative semigroup $F(S)$ then there are two ways to form semigroups from it by taking a quotient to get a commutative semigroup presentation or taking a subalgebra to get a multiset addition semigroup.

Properties of free $\mathbb{N}$-semimodules

The free $\mathbb{N}$ semimodule $F(S)$ on a set $S$ has a number of properties that are inherited by its subalgebras. Although every commutative semigroup is a quotient of some $F(S)$, only a small number of commutative semigroups can be embedded in the free commutative semigroup $F(S)$.

Theorem. the free $\mathbb{N}$ semimodule $F(S)$ is:

1. $\mathbb{N}^S$ distributive lattice ordered
2. Cancellative
3. Torsion-free
4. Commutative and a monoid

Proof. (1) the semiring $\mathbb{N}$ is totally ordered. Therefore, $F(S)$ is ordered by the product ordering $\mathbb{N}^S$ having terms in $S$ with multiplicities in $S$. Distributive lattices are a variety of lattices that include total orders, so the product ordering on $F(S)$ is distributive.

(2) the semiring $\mathbb{N}$ is additively cancellative so that $a + b = a + c$ implies that $b = c$. It follows from additive cancellativity that we have $a + b = a + c$ for addition in the free $\mathbb{N}$ semimodule.

(3) the semiring $\mathbb{N}$ is multiplicatively cancellative for $n \not= 0$. It follows that $na = nb$ implies that $a = b$ for $n \not= 0$. Therefore, $F(S)$ is torsion-free.

(4) every semimodule is an additive commutative monoid, therefore so too is $F(S)$. $\square$

Although $F(S)$ is a distributive lattice ordered torsion-free commutative cancellative semigroup, not all of these propreties are inherited by its subsemigroups. In particular, the distributive lattice ordering is not preserved.

Definition. a commutative semigroup is subfinite provided that each element is contained in a finite number of principal ideals.

Corollary. every subsemigroup of $F(S)$ is a subfinite J-trivial commutative cancellative torsion-free semigroup

Proof. let $A \subseteq B$ be semigroups, then the algebraic preorder on $A$ is a suborder of that of $B$. Therefore, given $C \subseteq F(S)$ then the algebraic preorder on $C$ is a subpreorder of a subfinite partial order, so it is a subfinite partial order making $C$ subfinite J-trivial. It is also commutative, cancellative, and torsion-free as these properties are hereditary. $\square$

This demonstrates that not all J-trivial commutative cancellative torsion-free semigroups can be embedded in a free commutative semigroup $F(S)$. The Puiseux monoid $(\mathbb{Q}_{\ge 0}, +)$ is a J-trivial commutative cancellative semigroup but it is not subfinite so there is no way of achieving an embedding.

A notable property of the Puiseux monoid $(\mathbb{Q}_{\ge 0},+)$ is that is infinitely generated. This suggests perhaps we can produce an embedding in the finitely generated case. This is an easy corollary of Grillet's theorem.

Grillet's theorem. a monoid is finitely generated commutative cancellative reduced monoid iff it is embeddable in $\mathbb{N}^n$.

Corollary. a finitely generated commutative cancellative J-trivial monoid is embeddable in $\mathbb{N}^n$ iff it is torsion-free

This demonstrates that the only properties necessary to demonstrate that a finitely generated commutative J-trivial semigroup is embeddable in $\mathbb{N}^n$ is that it is cancellative and torsion-free. These semigroups can therefore be expressed as multiset addition semigroups.

Factorisation in $F(S)$ subsemimodules

The free commutative semigroup $F(S)$ is a $\mathbb{N}$ semimodule, and so most important operations over it can be solved by linear algebra over the natural numbers. A finitely generated subsemirgoup of $F(S)$ can be described by the span of a multiset system $\{M_1,M_2,...\}$ which is the set of all linear combinations of the system of multisets. Each solution is a different factorisation.

Example 1. consider the subsemigroup $xy,x^2,y^2$. Then every factorisation of $x^n,y^m$ is a solution of the following system of linear equations: \[ \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Each solution to the system of linear equations produces a different factorisation of the multiset. For example, $x^4y^4$ has three factorisations: $(x^2)^2(y^2)^2$,$(xy)^2x^2y^2$,$(xy)^4$.

Example 2. consider the subsemigroup $x^3,x^2y,xy^2,y^3$. Then a factorisation of $x^n,y^m$ is a solution to the following system of linear equations: \[ \begin{bmatrix} 3 & 2 & 1 & 0 \\ 0 & 1 & 2 & 3 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Now $x^6 y^6$ has five factorisations: $(x^3)^2(y^3)^2$, $(xy^2)^2 (x^2y)^2$, $x^3 y^3 x^2y xy^2$, $x^3 (xy^2)^3$, $y^3 (yx^2)^3$.

This demonstrates by linear factorisation, that not all commutative J-trivial cancellative torsion-free finitely generated semigroups have unique factorisations. Although $F(S)$ does have unique factorisations, so that each element is uniquely expressed as a multiset.

Definition. a commutative J-trivial semigroup is called factorial provided that every element has a unique factorisation.

Example. the condensation $\frac{*}{H}$ of the multiplicative semigroup $*$ of a UFD is a factorial commutative cancellative J-trivial semigroup.

Notice that $x^2,y^2,xy$ determines a commutative subsemigroup but $x^2,x^2,xy,x^2y^2$ determines the same semigroup. We therefore need one more concept in order to enable computations on multiset systems related to the subsemigroups they generate:

Definition. a multiset system $S$ is sum minimal provided that $\forall x : x \not\in (S-x)$ so that no element $x$ is generated by the other elements in the multiset system.

For example, we can describe a numerical semigroup by a minimal set of generators, which is a simple combinatorial data structure we can work with. With this definition, it is a fairly simple procedure to create an algorithm to check if a given multiset system is sum minimal by solving a system of linear equations to check for factorisations of each element.

Proposition. the category of free commutative monoids is equivalent to the category of $\mathbb{N}$ semimodules with natural matrices between them.

The linear algebraic approach to free $\mathbb{N}$ semimodules allows us to describe any homomorphism of $\mathbb{N}$ semimodules by natural matrices. In particular, the endomorphism semiring $End(F(S))$ of a free commutative semimodule is equivalent to a matrix ring $Mat_S(\mathbb{N})$ over the semiring of natural numbers.

The factorisation of multisets can be determined by solving systems of linear equations over the natural numbers, or by determining the inverse image of a natural-valued matrix. This leads to the linear algebraic approach to $\mathbb{N}$ semimodules.