Multisets #

Introduction #

History #

The multiset is a simple and natural piece of mathematical technology that has been strangely underused in the last hundred years. That the multiset has failed to live up to its potential is due probably to historical accident. One possible explanation is that as the need for foundational rigor became urgent, modern mathematics quickly standardized on the set as a kind of universal building block, starving out other data structures, like the multiset. Such is the unfortunate role of fashion in mathematics. Luckily, multisets have seen renewed interest with the work of more computation-oriented mathematicians like Donald Knuth.

Motivation #

We are taking the time to explain multisets because they play an important interpretative role, giving us an alternative way of understanding algebraic structures. This role will only become clear in the next two sections: Word rings, where we'll elements of the word ring as multisets of words ("multiwords"), and Adjacency, where we'll interpret matrices as multisets of paths ("multipaths"). Interleaving the explanation of multisets with those topics would be confusing, so we'll front-load the work in understanding multisets here, in one place.

Sets and multisets #

Sets vs multisets #

To contrast sets with multisets, we first repeat some basic facts about sets.

Sets are the building blocks of modern mathematics. They consist of a collection of elements: \( \sym{X} = \SeFo{\sym{x_1}, \sym{x_2}, \elSy, \sym{x_{\sym{n}}}} \). We can express that an element is a member of a set with the notation \( \elemOf{\setElementSymbol{x}}{\setSymbol{X}} \).

Among the fundamental properties of a sets is that the elements have no defined order. Hence, the expressions \( \SeFo{\reFo{\card{r}}, \blFo{\card{b}}}\textAnd \SeFo{\blFo{\card{b}}, \reFo{\card{r}}} \) describe the same set. Furthermore, an object is either an element of a set or it is not. It is meaningless to say that it occurs twice, for example. Hence, the expressions \( \SeFo{\reFo{\card{r}}, \reFo{\card{r}}, \blFo{\card{b}}}\textAnd \SeFo{\reFo{\card{r}}, \blFo{\card{b}}} \) describe the same set -- especially when constructing sets we rely on this redundancy being irrelevant.

If we instead specify that repetition does matter, we arrive at the idea of a multiset. A multiset can contain an object more than once. The number of times a multiset contains an object will be called the multiplicity of that object.

We'll write multisets with double-struck braces: \( \sym{X} = \multiset{\sym{x_1},\sym{x_2},\elSy,\sym{x_{\sym{n}}}} \). Hence, \( \multiset{\reFo{\card{r}},\reFo{\card{r}},\blFo{\card{b}}}\textAnd \multiset{\reFo{\card{r}},\blFo{\card{b}}} \) describe different multisets: the multiplicity of \( \reFo{\card{r}} \) is \( 1 \) in the first and \( 2 \) in the second.

We’ll denote the multiplicity of an object \( \multisetElementSymbol{x} \) in a multiset \( \multisetSymbol{M} \) by \( \multisetSymbol{M}\multisetMultiplicitySymbol \multisetElementSymbol{x} \). For example, in the multiset \( \multisetSymbol{M} = \multiset{\reFo{\card{r}},\reFo{\card{r}},\blFo{\card{b}}} \), we have that \( \multisetSymbol{M}\multisetMultiplicitySymbol \reFo{\card{r}} = 2 \), \( \multisetSymbol{M}\multisetMultiplicitySymbol \blFo{\card{b}} = 1 \), and \( \multisetSymbol{M}\multisetMultiplicitySymbol \grFo{\card{g}} = 0 \).

The set of multisets #

The powerset \( \powerSet{\multisetSymbol{B}} \) of a set \( \multisetSymbol{B} \) is the set of subsets of \( \multisetSymbol{B} \). We'll call these the sets on \( \multisetSymbol{B} \), and \( \multisetSymbol{B} \) the base set.

We can similarly form the set of multisets whose objects are taken from \( \multisetSymbol{B} \), written \( \multisets{\multisetSymbol{B}} \). We'll call these the multisets on \( \multisetSymbol{B} \).

Any particular object from the base set can occur any finite number of times in one such multiset, so \( \multisets{\multisetSymbol{B}} \) is generally an infinite set (unless \( \multisetSymbol{B} \) is empty). Let's look at some examples of this simple and natural idea.

If \( \multisetSymbol{B} \) is a singleton, that is, contains only one element, then the multisets in \( \multisets{\multisetSymbol{B}} \) can contain this element any finite number of times. Here we list some multisets in \( \multisets{\multisetSymbol{B}} \) for \( \multisetSymbol{B} = \SeFo{\reFo{\card{r}}} \):

Clearly, we can identify these multisets with the positive integers, since they count the number of times that \( \reFo{\card{r}} \) is present.

If \( \multisetSymbol{B} \) contains two elements, then the multisets in \( \multisets{\multisetSymbol{B}} \) can be identified with pairs of positive integers, counting how many times the two elements are present. Here we list some elements of the set \( \multisets{\multisetSymbol{B}} \) for \( \multisetSymbol{B} = \SeFo{\reFo{\card{r}}, \blFo{\card{b}}} \):

For example, we can identify the multiset \( \multisetSymbol{M} = \multiset{\reFo{\card{r}},\reFo{\card{r}},\blFo{\card{b}}} \) with the function \( \boundMultiplicityFunction{\multisetSymbol{M}} = \assocArray{\mto{\reFo{\card{r}}}{2},\mto{\blFo{\card{b}}}{1}} \).

Formally, then, we have a bijection between multisets on \( \multisetSymbol{B} \) on one side and functions from \( \multisetSymbol{B} \) to the natural numbers on the other (multiplicity functions):

We'll shortly see how we can encode the natural operations on a multiset in terms of operations on such multiplicity functions.

Projection and lift #

We can define this bijection via two functions called projection and lift:

Lift takes a set and gives the multiset that contains each element exactly once:

Projection takes a multiset and gives the set of its elements:

Lifting and projecting a set yields the same set:

Conversely, the set-like multisets are precisely those for which:

Multiset-multiplicity duality #

We saw that multisets can be represented one-to-one by multiplicity functions.

There is a bijection between \( \multisets{\setSymbol{X}} \), the set of finite multisets on a base set \( \setSymbol{X} \), and the integrable functions from \( \setSymbol{X} \) to the natural numbers. By this we mean the set of functions with finite total. We'll write this set of functions as \( \finiteTotalFunctionSpace{\setSymbol{X}}{\baseField{\na}} \), because it necessarily consists of those functions in \( \functionSpace{\setSymbol{X}}{\baseField{\na}} \) that are only non-zero on a finite subset of \( \setSymbol{X} \):

Then the bijection between multisets and their multiplicity functions is given by:

More importantly, this bijection is an isomorphism, because it preserves the multiset operations of union, intersection, sum, etc., which we revisit here:

We say that the multiset \( \multisetSymbol{M} \) is dual to the multiplicity function \( \boundMultiplicityFunction{\multisetSymbol{M}} \).

We can express this isomorphism as a isomorphism of realms, where a realm is a set with the algebraic structure of sums, unions, and intersections. We will not enter into the realm of realms, however.

We can also see this duality as a particularly simple example of the duality between a space and its rings of functions. Here, the space is just \( \setSymbol{X} \) with the discrete topology, and the (semi)ring is the ring of functions \( \functionSignature{\function{f}}{\setSymbol{X}}{\na} \).

Multiset constructors #

Let's consider a general multiset constructor:

Here, \( \function{F} \) is some function that computes an output value from inputs \( \multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\elSy,\multisetElementSymbol{x}_{\sym{n}} \). Where do these inputs come from? The values of \( \multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\elSy,\multisetElementSymbol{x}_{\sym{n}} \) are drawn from multisets (or sets) \( \multisetSymbol{M}_1,\multisetSymbol{M}_2,\elSy,\multisetSymbol{M}_{\sym{n}} \) via the bindings \( \elemOf{\multisetElementSymbol{x}_{\sym{i}}}{\multisetSymbol{M}_{\sym{i}}} \). Bindings are indications that the multiset constructor should "draw an element from \( \multisetSymbol{M}_{\sym{i}} \) and place it in \( \multisetElementSymbol{x}_{\sym{i}} \)". The multiset constructor performs bindings in all possible ways in order to build a multiset of results.

This is very similar to how ordinary set constructor notation works, except for one important distinction. In set constructor notation, a particular value can only be drawn from a set once -- or more precisely, if we draw a particular value more than once, we would correspondingly collect a particular result \( \function{F}(\multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\elSy,\multisetElementSymbol{x}_{\sym{n}}) \) more than once, but this would still result in the same constructed set, since multiplicity is ignored! In contrast, multisets care about multiplicity. Therefore we draw an element from each \( \multisetSymbol{M}_{\sym{i}} \) exactly as many times as it appears. Here we show this difference for a simple example:

Similarly, when \( \function{F} \) produces a particular result multiple times, it will appear in the constructed multiset with the corresponding multiplicity. In the following example, \( \modFunction(\setElementSymbol{x},2) \) outputs the value \( 0 \) three times as \( \setElementSymbol{x} \) is bound the integers \( \zeroTo{4} \), because \( \modFunction(0,2) = \modFunction(2,2) = \modFunction(4,2) = 0 \):

The set version of this construction doesn't capture this multiplicity:

Images and preimages of sets #

We now review some basic facts about images and preimages of functions, to set the stage for analogous definitions for multisets. These ideas can be found in any undergraduate text on set theory. If this is familiar, you can jump to .

Definition #

Consider a function \( \functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}} \). We wish to apply it "set-wise", asking how it acts on a set of inputs (\( \setSymbol{A} \subseteq \setSymbol{X} \)) to give a set of outputs (\( \setSymbol{B} \subseteq \setSymbol{Y} \)). We similarly might wish to know what set of inputs corresponds to a given set of outputs.

To formalize these ideas, we define the image and preimage functions of \( \function{f} \), written \( \imageModifier{\function{f}} \) and \( \preimageModifier{\function{f}} \) respectively. They have the following signatures:

We define the image and preimage functions by using set constructor notation, where the image \( \imageModifier{\function{f}} \) function collects the outputs corresponding to the provided set of inputs, and the preimage \( \preimageModifier{\function{f}} \) collects the inputs corresponding to the provided set of outputs:

We can use a more compact, equivalent definition:

Example #

Consider the function \( \functionSignature{\function{f}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}}}{\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}} \) defined by \( \function{f} = \assocArray{\mto{\reFo{\card{r}}}{\teFo{\card{x}}},\mto{\grFo{\card{g}}}{\teFo{\card{x}}},\mto{\blFo{\card{b}}}{\orFo{\card{y}}}} \).

We’ll say that e.g. \( \SeFo{\teFo{\card{x}}} \) is the image of \( \SeFo{\reFo{\card{r}}} \) under \( \function{f} \), meaning that \( \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) = \SeFo{\teFo{\card{x}}} \) (for singletons, people sometimes elide the braces). For \( \function{f} \), we have the following images:

Since we've listed the images of all subsets of \( \SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}} \), we can collect these together to give the explicit value of \( \imageModifier{\function{f}} \):

Note the important but elementary fact that the image function \( \imageModifier{\function{f}} \) preserves unions for any function \( \function{f} \):

We show one example of this identity in action :

However, the image function does not preserve intersections or relative complements. Here are counterexamples for each case:

In general, however, we do have that have the following inequalities for intersections and complements:

Let's examine the preimage function \( \preimageModifier{\function{f}} \), which again we can write as a literal mapping for our example:

The preimage function of \( \function{f} \) is quite nice, since it preserves intersections*,* unions, and relative complements for any \( \function{f} \):

Here we show some examples for these identities for our specific function, but leave the general proofs as exercises:

We now extend the image and preimage functions to the setting of multisets.

Images and preimages of multisets #

The multi-image function \( \multiImageModifier{\function{f}} \) and multi-preimage function \( \multiPreimageModifier{\function{f}} \)are functions that play the same role as the image function \( \imageModifier{\function{f}} \) and preimage function \( \preimageModifier{\function{f}} \), but operate on multisets on the domain and codomain:

They are defined as follows, where \( \elemOf{\multisetSymbol{\reFo{A}}}{\multisets{\setSymbol{X}}}\textAnd \elemOf{\multisetSymbol{\blFo{B}}}{\multisets{\setSymbol{Y}}} \):

Or more compactly:

The only difference from the definitions of the image and preimage functions are that we are now using multiset constructor notation, rather than set constructor notation.

Example #

Let's compute the multi-image function for an example function \( \function{f} \). We'll use the same function \( \function{f} \) we examined above, which was \( \functionSignature{\function{f}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}}}{\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}} \) defined by \( \function{f} = \assocArray{\mto{\reFo{\card{r}}}{\teFo{\card{x}}},\mto{\grFo{\card{g}}}{\teFo{\card{x}}},\mto{\blFo{\card{b}}}{\orFo{\card{y}}}} \).

Then we can show the multi-image function \( \multiImageModifier{\function{f}} \) for set-like multisets inputs (those with maximum multiplicity 1):

Compare with the image function \( \imageModifier{\function{f}} \):

Note differences between the multi-image function \( \multiImageModifier{\function{f}} \)and the image function \( \imageModifier{\function{f}} \), for example:

Now compare the multi-preimage function \( \multiPreimageModifier{\function{f}} \) with the ordinary preimage function \( \preimageModifier{\function{f}} \):

Note that \( \multiPreimageModifier{\function{f}}\textAnd \preimageModifier{\function{f}} \) are identical when we restrict \( \multiPreimageModifier{\function{f}} \) to the set-like multisets.

Multiplicity functions of multi-image functions #

Just as we can characterize multisets in terms of multiplicity functions, we can do the same for multi-image functions.

Let us interrogate the behavior of \( \multiImageModifier{\function{f}} \) via the output multiset \( \multisetSymbol{\blFo{B}}\defEqualSymbol \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}) \) for a particular input multiset \( \elemOf{\multisetSymbol{\reFo{A}}}{\multisets{\setSymbol{X}}} \). Recall that this output is simply:

The multiplicity function \( \boundMultiplicityFunction{\multisetSymbol{\blFo{B}}} \) will count how many times any \( \elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}} \) occurs in the multi-image \( \multisetSymbol{\blFo{B}} = \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}) \).

Let us compute it pointwise -- i.e. for a given \( \multisetElementSymbol{\daBlFo{y}} \):

We've written the multiplicity \( \multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}} \) as a count of the number of ways we can bind \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\reFo{\setSymbol{A}}} \) to achieve the condition \( \multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}}) \).

Preservation of sums #

It is clear that the number of ways that \( \multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}}) \) can be true when \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}\multisetSumSymbol \multisetSymbol{\teFo{\primed{A}}}} \) is the number of ways it can be true when \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}} \) plus the number of ways when \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\teFo{\primed{A}}}} \):

Therefore we have that multi-image functions are linear -- they preserve multiset sums:

The same is not true for multiset intersection (or relative complement), for the same reason that ordinary image functions do not preserve set intersection and relative complement. However, we can put bounds on these multisets, whose proofs are left as an exercise:

Multiplicity functions of multi-preimage functions #

Let's run the same game for multi-preimage functions. Here, \( \multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}} \) will count how many times \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}} \) occurs in the multi-preimage \( \multisetSymbol{\reFo{A}}\defEqualSymbol \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}) \). This is the number of ways that we can bind \( \elemOf{\multisetElementSymbol{\daBlFo{y}}}{\multisetSymbol{\blFo{B}}} \) to satisfy \( \multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}}) \):

Again, it is easy to verify pointwise that \( \boundMultiplicityFunction{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetSumSymbol \multisetSymbol{\orFo{\primed{B}}})} = \boundMultiplicityFunction{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})} + \boundMultiplicityFunction{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\orFo{\primed{B}}})} \) and hence that multi-preimage functions are linear:

However, we do have the additional properties that multi-preimage functions preserve union, intersection, and complement.

To prove this, let us evaluate multiplicity of the multiset \( \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetUnionSymbol \multisetSymbol{\orFo{\primed{B}}}) \) pointwise, using the definition of \( \multisetUnionSymbol \) as the pointwise \( \max \) of multiplicity functions:

Hence under duality we have that:

Similar arguments run for intersection and relative complement.

Images and pre-images as matrix algebra #

We can easily connect the multi-image and multi-preimage to matrix algebra.

The transfer matrix of a function \( \functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}} \) is a generalized matrix \( \matrix{\boFo{F}} \) whose rows and columns are indexed by \( \setSymbol{X} \) and \( \setSymbol{Y} \) respectively, and which has the following entries:

The fact that \( \function{f} \) is a function -- i.e. single-valued -- is equivalent to the property \( \forAllForm{\multisetElementSymbol{\daReFo{x}}}{\indexSum{\matrixPart{\matrix{\boFo{F}}}{\multisetElementSymbol{\daReFo{x}}}{\multisetElementSymbol{\daBlFo{y}}}}{\multisetElementSymbol{\daBlFo{y}}}{} = 1} \).

The transfer matrix \( \matrix{\boFo{F}} \) associated with \( \sym{f} \) can be thought of as the multiplicity function for the graph \( \setSymbol{F} \), which is the set of input-output tuples from \( \function{f} \):

The way \( \matrix{\boFo{F}} \) encodes the multiplicity function of \( \setSymbol{F} \) is:

Similarly we can define the multiplicity tuple \( \tupleSym{\reFo{\boFo{A}}} \) of a multiset \( \elemOf{\reFo{\setSymbol{A}}}{\multisets{\setSymbol{X}}} \) to be the generalized tuple of multiplicities whose components are indexed by the base set \( \setSymbol{X} \):

The transfer matrix and multiplicity tuple allows us to compute the multi-image \( \blFo{\setSymbol{B}}\defEqualSymbol \function{\multiImageModifier{\function{f}}}(\reFo{\setSymbol{A}}) \) as a sum:

This computation is pointwise, for a fixed \( \elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}} \). But we can write it pointfree, where we compute the multiplicity tuple \( \tupleSym{\blFo{\boFo{B}}} \) for the multiset \( \elemOf{\blFo{\setSymbol{B}}}{\multisets{\setSymbol{Y}}} \) in one go using vector-matrix multiplication:

Multi-preimages can also be expressed this way. We can compute \( \reFo{\setSymbol{A}}\defEqualSymbol \function{\multiPreimageModifier{\function{f}}}(\blFo{\setSymbol{B}}) \) pointwise as:

Here, we can represent this pointfree as a matrix-vector multiplication:

Linearity #

The fact that multi-image and multi-preimage preserve multiset sums is then equivalent to the statement that matrix-vector multiplication is linear:

Multiset products #

In this section we'll establish how to multiply two multisets together. Doing this will require us to choose a function with appropriate properties to combine elements from each multiset together, to yield a resulting multiset.

Images of multiple arguments #

In the previous section we defined how we can "lift" a function \( \functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}} \) between sets \( \setSymbol{X},\setSymbol{Y} \) to its multi-image function \( \functionSignature{\function{\multiImageModifier{\function{f}}}}{\multisets{\setSymbol{X}}}{\multisets{\setSymbol{Y}}} \) between multisets on \( \setSymbol{X},\setSymbol{Y} \):

We can easily extend this idea to a function of \( \sym{n} \) arguments \( \functionSignature{\function{g}}{\TuFo{\setSymbol{X}_1, \setSymbol{X}_2, \elSy, \setSymbol{X}_{\sym{n}}}}{\setSymbol{Y}} \), lifting it into a function \( \functionSignature{\function{\multiImageModifier{\function{g}}}}{\TuFo{\multisets{\setSymbol{X}_1}, \multisets{\setSymbol{X}_2}, \elSy, \multisets{\setSymbol{X}_{\sym{n}}}}}{\multisets{\setSymbol{Y}}} \):

For similar reasons to the single-argument case, \( \multiImageModifier{\function{g}} \) preserves multiset sums in any of its arguments individually -- it is multilinear.

Semigroups #

We now focus our attention on binary functions that define the product of semigroups, as these will form useful ingredients in cooking up multiset products.

A semigroup on a set \( \setSymbol{X} \) is a pair \( \TuFo{\setSymbol{X}, \sgdot } \), where \( \functionSignature{\function{\sgdot }}{\TuFo{\setSymbol{X}, \setSymbol{X}}}{\setSymbol{X}} \) is an associative binary operation:

Lifting semigroup products #

Let us now consider how to lift the semigroup product \( \sgdot \) , defined on \( \setSymbol{X} \), to operate on multisets on \( \setSymbol{X} \). We should technically write this multi-image function as \( \multiImageModifier{\sgdot } \), but we will use the symbol \( \multiImageColorModifier{\srdot } \) instead, as we did for multiset versions of union, etc.

To recall, the multi-image function that lifts \( \sgdot \) is the function \( \functionSignature{\function{\multiImageColorModifier{\srdot }}}{\TuFo{\multisets{\setSymbol{X}}, \multisets{\setSymbol{X}}}}{\multisets{\setSymbol{X}}} \) defined as:

This function endows \( \multisets{\setSymbol{X}} \) with an interesting structure: that of a semiring. First, let's explain what a semiring is!

Semirings #

A semiring is a tuple \( \TuFo{\setSymbol{M}, \srplus , \srdot } \), where \( \functionSignature{\function{\srdot }}{\TuFo{\setSymbol{X}, \setSymbol{X}}}{\setSymbol{X}} \) is an associative binary operation and \( \functionSignature{\function{\srplus }}{\TuFo{\setSymbol{X}, \setSymbol{X}}}{\setSymbol{X}} \) is a commutative, associative binary operation with identity that distributes over \( \srdot \):

Additionally they must have an additive identity (the zero element), and usually also have one or more multiplicative identities.

Probably the simplest example of a semiring is given by the natural numbers under their ordinary sum and product: \( \TuFo{\na, + , \times } \).

Semirings are an "API" for the most general kinds of number-like objects, requiring only that they can be added and multiplied in a sensible way.

Semigroups to semirings #

We now show how an arbitrary semigroup yields a semiring via multi-images:

We define the multiset semiring induced by a semigroup \( \TuFo{\setSymbol{X}, \sgdot } \), to be the semiring \( \TuFo{\multisets{\setSymbol{X}}, \multisetSumSymbol , \srdot = \multiImageModifier{\sgdot }} \), which we can denote \( \multisetSemiring{\setSymbol{X}}{\sgdot } \):

• the semiring elements are the multisets on \( \setSymbol{X} \)

• the semiring addition \( \srplus \) is given by multiset sum \( \multisetSumSymbol \)

• the semiring product \( \srdot \) is given by the multi-image function \( \multiImageModifier{\sgdot } \) that lifts the semigroup product \( \sgdot \)

Let's verify this is actually a semiring.

The additive identity is obvious: it is the empty multiset, since \( \multisetSymbol{A}\multisetSumSymbol \multiset{} = \multisetSymbol{A} \).

Associativity of the semiring product \( \srdot \) follows from associativity of \( \sgdot \) straightforwardly.

Distributivity of \( \srdot \) over \( \srplus \) follows from the fact that any $n$-ary multi-image function is multilinear: it preserves multiset sums in each of its arguments. We'll spelling this out for left-distributivity, right-distributivity is proved in a similar way:

Example 1: "tally" multisets #

Let's flex our muscles a bit to see how these multiset semirings might model familiar parts of mathematics.

Let's consider the multisets on a singleton set \( \blFo{\setSymbol{X_0}} = \SeFo{\blFo{\sym{x}}} \). We'll name this set \( \reFo{\setSymbol{X_1}} \):

We saw earlier that the multisets on a singleton are in bijection with the natural numbers, where we are essentially "tallying by finger counting":

From now on, we'll express these multisets in a more compact form using integer multiples:

Using this notation, we have:

To define the semiring structure on \( \reFo{\setSymbol{X_1}} = \multisets{\blFo{\setSymbol{X_0}}} \), we must choose a semigroup product \( \functionSignature{\function{\sgdot }}{\TuFo{\blFo{\setSymbol{X_0}}, \blFo{\setSymbol{X_0}}}}{\blFo{\setSymbol{X_0}}} \) on \( \blFo{\setSymbol{X_0}} = \SeFo{\blFo{\sym{x}}} \). But there is only one possible such structure, given by \( \blFo{\identity} = \assocArray{\mto{\TuFo{\blFo{\sym{x}}, \blFo{\sym{x}}}}{\blFo{\sym{x}}}} \). Therefore our semiring product on \( \reFo{\setSymbol{X_1}} \) is \( \reFo{\msrdot } = \multiImageModifier{\blFo{\identity}} \), yielding the the semiring structure we'll call \( \reFo{\multisetSemiringSymbol{M_1}} \):

\( \reFo{\multisetSemiringSymbol{M_1}} \) has the following properties:

• the sum of two multisets corresponds to the sum of two natural numbers: \( \repeatedMultiset{\sym{m}}{\styledMultiset{\reFo}{\blFo{\sym{x}}}}\,\reFo{\msrplus }\,\repeatedMultiset{\sym{n}}{\styledMultiset{\reFo}{\blFo{\sym{x}}}} = \repeatedMultiset{\paren{\sym{m} + \sym{n}}}{\styledMultiset{\reFo}{\blFo{\sym{x}}}} \)

• product of two multisets corresponds to the product of two natural numbers: \( \repeatedMultiset{\sym{m}}{\styledMultiset{\reFo}{\blFo{\sym{x}}}}\,\reFo{\msrdot }\,\repeatedMultiset{\sym{n}}{\styledMultiset{\reFo}{\blFo{\sym{x}}}} = \repeatedMultiset{\paren{\sym{m} \, \sym{n}}}{\styledMultiset{\reFo}{\blFo{\sym{x}}}} \)

Hence, \( \reFo{\multisetSemiringSymbol{M_1}} \) is isomorphic to the semiring of the natural numbers:

We have some additional properties of \( \reFo{\multisetSemiringSymbol{M_1}} \) that exploit the other multiset operations:

Example 2: univariate polynomials #

We'll now form the multisets on \( \reFo{\setSymbol{X_1}} \), and call this \( \grFo{\setSymbol{X_2}} \):

Before trying to interpret \( \grFo{\setSymbol{X_2}} \), we'll choose to abbreviate the elements of \( \reFo{\setSymbol{X_1}} \) in a more suggestive way:

As a special case, we'll use \( \reFo{1} \) to denote the empty multiset \( \elemOf{\styledMultiset{\reFo}{}}{\reFo{\setSymbol{X_1}}} \).

We can now list some of the infinitely many elements of \( \grFo{\setSymbol{X_2}} \):

We can further also use integer multiple notation to write these elements of \( \grFo{\setSymbol{X_2}} \) in a more compact way:

On the other hand, we can avoid using any notation at all, and write an element of \( \grFo{\setSymbol{X_2}} \) directly as a multiset of multisets on \( \blFo{\setSymbol{X_0}} = \SeFo{\blFo{\sym{x}}} \):

General form #

A general element \( \elemOf{\multisetSymbol{M}}{\grFo{\setSymbol{X_2}}} \) can be written as a sum of elements of \( \reFo{\setSymbol{X_1}} \), with corresponding multiplicities \( \sym{m}_{\sym{i}} \). Recall that only finitely many of these can be non-zero.

The summation symbol \( \grFo\indexSumSymbol{} \) is colored to indicate that is represents the composition of binary multiset sums \( \grFo{\msrplus } \).

Polynomials #

It should be transparent now that there is a bijection between \( \grFo{\setSymbol{X_2}} \) and the polynomials in variable \( \blFo{\sym{x}} \) with non-negative integer coefficients:

Semiring product #

Next, we seek a product \( \grFo{\msrdot } \) so that \( \TuFo{\grFo{\setSymbol{X_2}}, \grFo{\msrplus }, \grFo{\msrdot }} \) forms a semiring.

But we have an obvious candidate: the lift \( \multiImageModifier{\reFo{\msrdot }} \) of the product \( \reFo{\msrdot } \) of \( \reFo{\multisetSemiringSymbol{M_1}} \), since the semiring \( \TuFo{\reFo{\setSymbol{X_1}}, \reFo{\msrplus }, \reFo{\msrdot }} \) defines a semigroup \( \TuFo{\reFo{\setSymbol{X_1}}, \reFo{\msrdot }} \).

Setting \( \grFo{\msrdot } = \multiImageModifier{\reFo{\msrdot }} \), we can define the semiring \( \grFo{\multisetSemiringSymbol{M_2}} = \TuFo{\grFo{\setSymbol{X_2}}, \grFo{\msrplus }, \grFo{\msrdot }} \).

As an example, let's see how the product \( \grFo{\msrdot } \) acts on two elements of \( \grFo{\setSymbol{X_2}} \):

This corresponds to the product of polynomials:

Product computation #

We can compute the product of two general elements of \( \elemOf{\multisetSymbol{A},\multisetSymbol{B}}{\grFo{\multisetSemiringSymbol{M_2}}} \) by first expressing them as finite sums of elements of elements of \( \reFo{\multisetSemiringSymbol{M_1}} \):

Then the product is given by:

Solving for the multiplicity in \( \multisetSymbol{A}\,\grFo{\msrdot }\,\multisetSymbol{B} \) of a generic element \( \elemOf{\power{\reFo{\sym{x}}}{\sym{i}}}{\reFo{\setSymbol{X_1}}} \), we can remove one of the indices of the double summation:

These computations may seem obvious when we have the polynomial interpretation of these multisets in mind, and in a sense it is pedantic to spell them out. But it is perhaps surprising that we were naturally led to this semiring structure as soon as we chose the base set \( \blFo{\setSymbol{X_0}} = \SeFo{\blFo{\sym{x}}} \).

In summary, we have the semiring isomorphism between the positive-integral univariate polynomials \( \polynomialRing{\semiring{\na}}{\blFo{\sym{x}}} \) and the multiset semiring on the multiset semiring on \( \SeFo{\blFo{\sym{x}}} \) (phew!):

Summary of examples #

Our last two examples have covered one semigroup and two multiset semirings involved, let's summarize the situation in a table:

The univariate polynomials modelled by \( \grFo{\multisetSemiringSymbol{M_2}} \) are specifically those that have natural-number coefficients. We will shortly see how to obtain the full ring of polynomials with integer-valued coefficients using signed multisets.

Next, we will extend our notion of multisets slightly, which will allow us to beef up these constructions of the semirings \( \semiring{\na} \) and \( \polynomialRing{\semiring{\na}}{\blFo{\sym{x}}} \) to constructions of the rings \( \ring{\mathbb{Z}} \) and \( \polynomialRing{\ring{\mathbb{Z}}}{\blFo{\sym{x}}} \).

Signed multisets #

We can extend the idea of a multiset in a very simple way to yield a signed multiset.

We can think of a normal, unsigned multiset \( \elemOf{\multisetSymbol{A}}{\multisets{\setSymbol{X}}} \) on a base set \( \setSymbol{X} \) as an unordered list of elements from \( \setSymbol{X} \). To form a signed multiset, we allow some of these elements to be present in negated form in the multiset. This is similar to the way we conceptualize of negative integers are the negated forms of positive integers.

To indicate the presence of a negated form of an element \( \elemOf{\setElementSymbol{x}}{\setSymbol{X}} \), we write it with an overbar: \( \negated{\signedMultisetElementSymbol{x}} \). For example, the following signed multiset consists of three non-negated copies of \( \signedMultisetElementSymbol{x} \), and two negated copies of \( \signedMultisetElementSymbol{y} \):

If a single object is present in both negated and non-negated forms, these "cancel" each other in pairs:

A signed multiset is in normal form if it is written so that no cancellable pairs are present.

Essentially, the "net" number of ordinary or negated copies of an object gives the multiplicity of that object, which can now be a negative integer if there are negated copies present.

We write the set of signed multisets on a base set \( \setSymbol{X} \) as \( \signedMultisets{\setSymbol{X}} \).

Signed multiplicities #

For a multiset \( \elemOf{\multisetSymbol{A}}{\multisets{\setSymbol{X}}} \), the multiplicity function \( \functionSignature{\function{\boundMultiplicityFunction{\multisetSymbol{A}}}}{\setSymbol{X}}{\na} \) associates to each element \( \elemOf{\setElementSymbol{x}}{\setSymbol{X}} \) a natural number \( \multisetSymbol{X}\multisetMultiplicitySymbol \setElementSymbol{x} \).

For a signed multiset \( \elemOf{\multisetSymbol{B}}{\signedMultisets{\setSymbol{X}}} \), the multiplicity function \( \functionSignature{\function{\boundMultiplicityFunction{\multisetSymbol{B}}}}{\setSymbol{X}}{\mathbb{Z}} \) associates to each element of \( \setSymbol{X} \) an integer. Negative integers indicate negative multiplicities.

All other operations on signed multisets are defined in an identical way relative to their multiset relatives, with one exception -- the relative complement no longer requires a \( \max(\plSqSy,0) \) in its definition, since negative multiplicities are permitted:

Signed sets #

Analogous to the signed multisets \( \signedMultisets{X} \) on a set \( \setSymbol{X} \) are the signed sets \( \signedSubsets{X} \) on \( \setSymbol{X} \).

Just as for multisets, any element \( \elemOf{\setElementSymbol{x}}{\setSymbol{X}} \) can be present in a signed set \( \elemOf{\signedSetSymbol{A}}{\signedSubsets{X}} \) in a signed set in unnegated or negated form. When present in negated form it is written \( \negated{\signedSetElementSymbol{x}} \). A given element \( \setElementSymbol{x} \) can not be present in both unnegated and negated forms simultaneously. To illustrate the possibilities, we show the set of signed sets on a variety of base sets:

In general, for a base set \( \setSymbol{X} \) of cardinality \( \setCardinality{\setSymbol{X}} = \sym{n} \) the cardinality of the set of signed sets on \( \setSymbol{X} \) is:

This is because in a given signed set \( \elemOf{\signedSetSymbol{A}}{\signedSubsets{\setSymbol{X}}} \) element of \( \setSymbol{X} \) can either 1) not occur in \( \signedSetSymbol{A} \), 2) occur unnegated or 3) occur negated.

Multiplicity functions #

To help us think about signed sets, we can regard them in terms of their multiplicity functions, which can now take on values in the set \( \SeFo{-1, 0, 1} \) to indicate the presence, absence, or presence in negated form of any given element.

For example, here are some multiplicity functions for signed sets on base set \( \SeFo{\reFo{\setElementSymbol{a}}, \blFo{\signedSetElementSymbol{b}}, \grFo{\setElementSymbol{c}}} \):

Operations #

We can define union and intersection operations on signed sets by applying the definition of these operations in terms of multiplicity functions that we obtained in the case of ordinary sets, which we recall below:

To handle signed multiplicities for signed sets \( \signedSetSymbol{A} \) and \( \signedSetSymbol{B} \), we need only modify the relative complement, which should now "clip" the resulting multiplicity to be no greater than 1 and no less than -1:

With these definitions in hand, we can look at some examples of unions on the signed sets on base set \( \SeFo{\reFo{\setElementSymbol{a}}, \blFo{\signedSetElementSymbol{b}}, \grFo{\setElementSymbol{c}}} \):

Some intersections:

Some relative complements:

Sum #

When we introduced the sum of multisets, as distinct from the union of multisets, the reader might wonder why there was no such distinction for ordinary sets. The reason is that sets take multiplicities in \( \SeFo{0, 1} \), and for these values there is no distinction between the \( \max(\plSqSy,\plSqSy) \) (the multiplicity implementation of union) and \( \min(\plSqSy + \plSqSy,1) \) (the multiplicity implementation of sum). For signed multisets these implementations are distinct, as there is no longer a \( \min \) at play. For signed sets, these are again distinct, although here the multiplicity implementation of sum is now \( \clip(\plSqSy + \plSqSy,-1,1) \) :

Here we show some examples of the sums of signed sets:

An interesting aspect of signed set summation is that it is not associative, unlike for multiset summation. For multisets \( \multisetSymbol{X},\multisetSymbol{Y},\multisetSymbol{Z} \), we have that \( \multisetSymbol{X}\multisetSumSymbol \paren{\multisetSymbol{Y}\multisetSumSymbol \multisetSymbol{Z}}\identicallyEqualSymbol \paren{\multisetSymbol{X}\multisetSumSymbol \multisetSymbol{Y}}\multisetSumSymbol \multisetSymbol{Z} \), which justifies writing sums of three or more sets without any parentheses \( \multisetSymbol{X}\multisetSumSymbol \multisetSymbol{Y}\multisetSumSymbol \multisetSymbol{Z} \) since the order of binary operations does not matter. This is not true for signed sets because of the presence of \( \clip \):

Signed projection and lift #

Just like for sets and multisets, we can lift and project between signed sets and signed multisets.

Signed lifting takes a signed set and gives the signed multiset that contains each element either negated or unnegated exactly once:

Signed projection takes a signed multiset and gives the signed set that contains an element unnegated if it occurs a positive number of times, and negated if it occurs a negative number of times:

Here we use \( \positiveSignedPart{\signedMultisetSymbol{A}} \) to denote the ordinary multiset consisting of all the unnegated elements of the signed multiset \( \signedMultisetSymbol{A} \), and \( \negativeSignedPart{\signedMultisetSymbol{A}} \) to be the same but for negated elements (where the negated elements occur unnegated in the result, of course):

As before, lifting and projecting a signed set yields the same set:

Signed multiset rings #

Recap #

In the previous section we saw how the multisets on a set with an associated semigroup operation give rise to a semiring. Specifically if we have a semigroup operation \( \functionSignature{\function{\sgdot }}{\TuFo{\setSymbol{X}, \setSymbol{X}}}{\setSymbol{X}} \) on a set \( \setSymbol{X} \), we can equip the set of multisets \( \multisets{X} \) with a multiplication \( \msrdot \defEqualSymbol \multiImageModifier{\sgdot } \) to yield a semiring that we will denote \( \multisetSemiring{\setSymbol{X}}{\sgdot } \).

Compactly, then, we have \( \multisetSemiring{\setSymbol{X}}{\sgdot }\defEqualSymbol \TuFo{\multisets{X}, \multisetSumSymbol , \msrdot } \). To recap, the semiring operations are:

• adding two elements \( \multisetSymbol{A},\multisetSymbol{B} \) of the semiring corresponds to adding the corresponding multisets (\( \isomorphicSymbol \) adding their multiplicity functions):

• multiplying two elements of the semiring corresponds to \( \sgdot \)-multiplying all pairs that can be formed from the two multisets:

Multiplicity functions #

We can also state the semiring sum and product in terms of multiplicity functions. The multiplicity of some element \( \multisetElementSymbol{c} \) in the sum and product is computed as:

We can now extend this situation to signed multisets by simply allowing the corresponding multiplicities to be negative.

Signed multiset ring #

If \( \functionSignature{\function{\sgdot }}{\TuFo{\setSymbol{X}, \setSymbol{X}}}{\setSymbol{X}} \) is a semigroup operation on a set \( \setSymbol{X} \), we can now define the signed multiset ring, written \( \signedMultisetRing{\setSymbol{X}}{\sgdot } \) to be the following tuple:

Here, \( \msrdot \) is again the multi-image lift \( \multiImageModifier{\sgdot } \) of the semigroup operation \( \sgdot \), this time to operate on signed multisets. How does this work?

The most natural way to understand this is to first extend \( \sgdot \) to be a binary operation on signed sets on \( \setSymbol{X} \).

Advanced topics #

Lattice structure #

Convexity #

Galois connection #