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:

Definition

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

Definition

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

and

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.

This entry was posted on Monday, April 28th, 2008 at 4:00 am and is filed under Mathematics, Multisets. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

[…] two multisets and over . If we try to define equality between multisets strictly on the basis on membership, we would have . This isn’t quite what we want, since it doesn’t account for the multiplicity […]

[…] two multisets and over . If we try to define equality between multisets strictly on the basis on membership, we would have . This isn’t quite what we want, since it doesn’t account for the multiplicity […]