On Monday, we considered how the sets can be represented as functions In fact, for every function we can define Combining this with the definition of the characteristic function, we have the identities

and

This actually provides the bijection between and the functions that I mentioned immediately following the definition of the characteristic function.

Structurally, the class

is very similar to the class

of multisets over Our ability to represent the set operations on by well-defined operations in the ordered field suggests that we look at some of the well-defined operations on as a basis for formally defining the multiset operations on

One operation on that we have already used is the cardinal sum which is defined for every set of cardinals

**Definition**

Let be an indexed family of multisets. The *multiset sum* of is the multiset

Since for all the cardinal sum on the right is well-defined and the multiset sum does indeed give us another multiset over For a pair of multisets, we will generally write the multiset sum in infix notation as

As the notation suggests, the multiset sum is related to the union operation on sets. Multiset sums, like the union of sets are both commutative and associative—these follow directly from the corresponding properties of the cardinal sum. Cardinal sums are also monotonic nondecreasing; for any cardinal sum we have for all One consequence of this is that a cardinal sum is 0 if and only if all of its summands are 0, and so we have the following relationship between support, multiset sums, and set unions:

The monotonicity of cardinal sums also ensures that the multiset sum of a family of multisets contains each of the multisets in the family:

Here’s a way in which the multiset sum differs from the union of sets. Set union is *idempotent*—for any set we have The multiset sum, on the other hand, is not idempotent, as we can see by considering the sum

This last example also shows that the class of multisets with all multiplicities equal to 1 is not closed under multiset sums.

Copyright © 2008 Michael L. McCliment.