Arithmetical properties of multiset systems

Perhaps the most basic object of mathematical discourse is that of a set system. This picture is complicated somewhat when we consider topos theory, and we start to consider copresheaf topoi which are about as fundamental as set systems. But we always can find ourselves looking back at concepts of set systems and hypergraphs. As we introduce and develop more forms of mathematical structure we can see set systems from different lights. We will see today how a semiring structure can be established on set systems.

Let $F(S)$ be a free commutative monoid on a set $S$. Then $\mathbb{N}F(S)$ is the semigroup semiring of all multiset systems whose terms are in $S$. We can now define an injective function that maps set systems into this semiring. \[ f: \wp(\wp(S)) \to \mathbb{N}F(S) \] With this we can treat set systems like any other arithmetic structure such as $\mathbb{N}$. In fact it is similar to $\mathbb{N}$ in a remarkable way: it is both additively and multiplicative J-trivial.

Proposition. let $\mathbb{N}F(S)$ be a semigroup semiring of multiset systems. Then both its additive and multiplicative parts are J-trivial commutative semigroups.

A semigroup semiring is additively J-trivial if its base semiring is. On the other hand, $\mathbb{N}F(S)$ is multiplicatively J-trivial because both the argument semigroup $F(S)$ and the multiplicative semigroup of the semiring are J-trivial. On the other hand, $\mathbb{Z}F(S)$ is clearly neither additively or multiplicatively J-trivial. We can always recover a J-trivial semigroup from a commutative semiring by quotienting out by the H classes.

Multiplication of set systems:
The definition of the multiplication of set systems follows easily from the definition of semigroup semirings. Algorithms can easily be provided for dealing with the multiplication of set systems by using for example either Clojure's list comprehensions or Java's for loops.

Definition. let $S$ and $T$ be indexed families of multiset systems. Let addition constitute the composition of multisets in a free commutative monoid. Then $ST$ can be defined by the sum: \[ \sum_{i \in I, j \in J} \{(S_i + T_j)\} \] This can be used to define our first examples of set system multiplication. Recall from the most basic of mathematics that an ordered pair is a set system of the form $\{\{a\},\{a, b \}\}$. I will first demonstrate the properties of set system multiplication by getting the powers of an ordered pair. \[ \{\{a\},\{a,b\}\}^2 = \{\{a,a\},\{a,a,b\},\{a,a,b\},\{a,a,b,b\}\} \] This process can naturally be continued to get yet higher powers of the ordered pair. The resulting multiset systems get quite large as the multiplication process continues. \begin{equation} \{\{a\},\{a,b\}\}^3 = \{\{a,a,a\},\{a,a,a,b\},\{a,a,a,b\},\{a,a,a,b,b\}, \\ \{a,a,a,b\},\{a,a,a,b,b\},\{a,a,a,b,b\},\{a,a,a,b,b,b\}\} \end{equation} In fact, the exact asymptotics of the growth of the cardinality of products of multiset systems is determined by a homomorphism of semigroups from the multiplication of set systems to the free commutative monoid.

Proposition. let $\mathbb{N}F(S)$ be the semigroup semiring of multiset systems. Let $|X|$ denote the cardinality of a multiset $X$. Then if $A$,$B$ are multiset systems we have that $|AB| = |A||B|$.

It follows that there is a homomorphism $f: (\mathbb{N}F(S),*) \to (\mathbb{N},*)$. Furthermore, it is not hard to see that this can be extended to a homomorphism of semirings $f: \mathbb{N}F(S) \to \mathbb{N}$.

Multiplicative factorisation of set systems:
We can now use the semigroup semiring $\mathbb{N}F(S)$ to interpret the properties of set systems.

Theorem. let $G$ be a complete bipartite graph between the sets $S$ and $T$. Then the binary family of edges of $G$ is the product of disjoint unary families formed from $S$ and $T$.

Proof. the complete bipartite graph has one edge ${s,t}$ for each $s \in S$ and each $t \in T$. On the other hand, the unary family of $S$ has one singleton $\{s\}$ for each $s \in S$ and likewise for $T$ there is one $\{t\}$ in the unary family of $T$ for each $t \in T$. Now given any $s \in S$ and $t \in T$ we get $\{s\} + \{t\} = \{s,t\}$ which is a set because $S$ and $T$ are disjoint. So the product of the unary families of $S$ and $T$ is the family of $G$. $\square$

This general process produces a multiplicative factorisation from complete bipartite binary families. We can now demonstrate this as an example of

Example. $\{\{a,x\},\{a,y\},\{b,x\},\{b,y\}\} = \{\{a\},\{b\}\}*\{\{x\},\{y\}\} $

With this approach, we can form a whole new algebraic theory of multiset systems. All the different set systems that emerge from graphs, partial orders, designs, matroids, etc can now be considered in a new light.

Foundations of combinatorial commutative algebra:
We have seen that commutative algebraic, and in particular the commutative semigroup semiring $\mathbb{N}F(S)$, can be used to better understand set systems and multiset systems. The dual concept is to use set systems as a tool of commutative algebra, which leads to combinatorial commutative algebra.

We have seen that multiset systems are elements of $\mathbb{N}F(S)$. There is an obvious correspondence from $\mathbb{N}F(S)$ to $\mathbb{Z}F(S)$, which extends the homomorphism $f: \mathbb{N} \to \mathbb{Z}$. \[ i : \mathbb{N}F^(S) \to \mathbb{Z}F(S) \] Where $\mathbb{Z}F(S)$ is in fact a ring of polynomials, because polynomial rings are nothing more then semigroup rings over free commutative monoids. Let $R$ be a commutative ring with identity $1$ then $R$ has a characteristic $C$ which means that extends over $GF(C)$. There is an obvious morphism $f: \mathbb{Z} \to GF(C)$ so that any non-zero characteristic prime ring is a quotient of $\mathbb{Z}$.

This naturally means that any integral polynomial in the semigroup ring $\mathbb{Z}F(S)$ can be embedded into a commutative ring with identity. This then produces a series of maps $\mathbb{N}F^(S) \to \mathbb{Z}F^{S} \to R F^(S)$ so that multiset systems are embeddable into arbitrary polynomial rings.

The Stanley-Reisner ring is nothing more then an application of this general construction in the case where $F$ is a field and the multiset system in question is the subclass closed set system of an abstract simplicial complex. The Stanley-Reisner ring is the simple the quotient ring determined by the monomial ideals of the set of this set system, but this could just as well be applied to get a quotient ring of a ring from arbitrary multiset systems.

See also:
[1] https://en.wikipedia.org/wiki/Stanley%E2%80%93Reisner_ring

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.

Rings of multivariable Laurent polynomials

The commutative group ring of the free commutative group $F^{\circ}(X)$ over a field $k$ is a ring extension of the commutative semigroup ring of the free commutative monoid $F(X)$ over $k$. Although, $F^{\circ}(X)$ is a natural semigroup extension of $F(X)$, rings of multivariable Laurent polynomials don't have the same level of importance as polynomial rings in commutative algebra.

A distinguishing property of ordinary polynomials is that they can be cast into functions, so that over affine space $\mathbb{A}^n$ they are functions $f: \mathbb{A}^n \to k$ and this works for any commutative ring. On the other hand, for Laurent polynomials to be cast into functions $f : \mathbb{A}^n \to k$ we need to have some notion of division to deal with negative degree exponents, so we need to work over a field.

In those cases when we take the commutative group ring of a commutative ring $R$ which is not a field, with respect to $F^{\circ}(X)$ then what we get is certainly still a commutative ring, it is just not a commutative ring of functions. Consider the commutative group ring $\mathbb{Z}(\mathbb{Z}^n,+)$ consisting of polynomials with integer exponents and integer coefficients. Then this is a valid commutative ring, but its elements are not functions because $\mathbb{Z}$ is not a field.

So in some sense we ought to have our free commutative group ring be over a field $k$. Then we get terms like $5\frac{x}{yz} + \frac{6y}{xz}$ consisting of fractional monomials, but then given any term like this we can add to get $\frac{5x^2 + 6y^2}{xyz}$ which is always a polynomial with a monomial in the denominator. So we see that multivariable Laurent polynomials are simply rational functions with monomials in the denominator, so we have an embedding. \[ kF^{\circ}(x,y,z) \subseteq k(x,y,z) \] The ring of Laurent polynomials is simply the localisation of the polynomial ring by the multiplicative set of monomials, and so they are merely a special case of rational functions. Now it is clear why we don't see Laurent polynomials so much in commutative alebra. They are simply part of the far more important and general concept of fields of rational functions $k(x,y,z)$.

Just as we don't tend to restricted localisations of the integers like the dyadic rationals that much, we won't see rings of multivariable Laurent polynomials showing up as much. In general, we always want to deal with the largest localisation of a domain, which is its field of fractions.

So although the group completion of the free commutative semigroup $F(X)$ is an important and natural concept in commutative semigroup theory, it doesn't have the same role and level of importance in commutative algebra, as determined by commutative semigroup rings. This demonstrates that not everything in commutative algebra is a consequence of commutative semigroup rings, but the use of semigroup rings is still an infinitely powerful technique in the construction of commutative rings.

Applications of commutative semigroup rings

Let $R$ be a commutative ring. Then every commutative semigroup $S$ is naturally associated to a commutative ring extension of $R$, the commutative semigroup ring of $R$ by $S$. It is not hard to see that this construction is full of applications in commutative algebra and algebraic geometry. We will utilize commutative semigroup rings as an organizing principle in the theory of polynomial rings, which is an important part of algebraic geometry.

Polynomial rings:

The free $\mathbb{N}$-semimodule $F(X)$ is a very familiar object of commutative semigroup theory. It is not hard to see that the polynomial ring $R[x_1,x_2,...]$ is merely the commutative semigroup ring of $R$ by $F(x_1,x_2,...)$ : $RF(x_1,x_2,..)$. As a consequence, the polynomial rings that are so fundamental in algebraic geometry, can be considered to be a special case of a commutative semigroup ring.

Subalgebras of polynomial rings

Let $S$ be a finitely generated torsion-free cancellative J-trivial commutative semigroup. Then $S$ embeds into the free commutative semigroup $F(X)$ on a finite set of generators $X$. As a consequence, we can embed the commutative semigroup ring $RS$ into the polynomial ring $R[x_1,x_2,...]$.

As an example, any numerical semigroup can be embedded in the polynomial ring on a single generator. The polynomial subring $R[x^2,x^3]$ for example is merely the commutative semigroup ring of the numerical semigroup $\{2,3\}$. If we had $R[x^2y,yz^3]$ for example it would be generated by the commutative semigroup $(x^2y,yz^3) \in F(x,y)$, and so on.

Extensions of polynomial rings:

It is a basic fact of commutative algebra that $F(X)$ is a cancellative semigroup. Therefore, the free $\mathbb{N}$ semimodule $F(X)$ can be embedded in the free $\mathbb{Z}$-module $F^{\circ}(X)$. As a consequence, the commutative semigroup ring of multivariable polynomials $RF(X)$ can be embedded in the ring of multivariable Laurent polynomials $RF^{\circ}(X)$.

This can be further extended by considering rings of Puiseux polynomials $R\mathbb{Q}^n$ consisting of polynomials that have rational exponents, or this could even be embedded in $R\mathbb{R}^n$ to have arbitrary real exponents, so that we can have a complete extension of the ordinary polynomial ring $R[x_1,x_2,...]$.

Coordinate rings of varieties

Let $Y$ be an algebraic variety defined by a system of polynomial equations in $R[x_1,x_2,...]$. Then by now means is it the case that the coordinate ring $A(Y)$ can always be defined by a commutative semigroup ring. However, there is an important case in which they can be: algebraic varieties defined by differences of monomials. These correspond to relations in the presentation of a commutative semigroup.

Therefore, we can use commutative semigroup rings in algebraic geometry in order to deal with the important special case of varieties determined by differences of monomials. For example, consider the hyperbola $\frac{R[x,y]}{xy=1}$. Then this clearly produces a presentation of the commutative group $\mathbb{Z}$ so this is a ring of Laurent polynomials. As you can see, this is a very useful concept of commutative algebra.

References:
[1] Commutative semigroup rings by Gilmer