Our informal conception of a multiset is that it’s like a set, but allows an element to be in the set multiple times. Formally, we’re considering multisets to be a structure where . Since is a set, we have a primitive notion of membership available in the underlying set theory. What we want to do now is formalize the notion of membership in a multiset. Before we do, let’s define one other notion:
Let be a multiset. The support of is
The support of a multiset is a subset of its underlying set: . We’ll now define membership in a multiset as
It may be tempting to define multiset membership as . So why not define it this way? Consider a multiset where and . Here, but appears 0 times in . Since , we end up with , and —exactly the result we would expect if occurs 0 times in .
Since multisets are intended to be a generalization of sets, we should be able to correlate the class of sets with some subclass of multisets. (This probably has a more elegant statement in terms of category theory. Unfortunately, I have only a passing familiarity with it at this point, and wouldn’t trust any formulation I might propose in cetegory-theoretic terms.) The correlation is given by with . That is, a set is identified with the multiset over where every element of has a multiplicity of 1. With this mapping, we have
We’ll revisit this correspondence again as we define the various operations on multisets, showing how the operations on multisets are an extension of the operation on sets.
Copyright © 2008 Michael L. McCliment.