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