Multiset membership

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 \mathcal{M} = \left(S, f\right) where f: S\to\mathbf{Card}. Since S 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 \mathcal{M} = \left(S,f\right) be a multiset. The support of \mathcal{M} is

\mathrm{support}\left(\mathcal{M}\right) := \left\{x\in S | f(x) > 0\right\}.

The support of a multiset is a subset of its underlying set: \mathrm{support}\left(\mathcal{M}\right) \subseteq S. We’ll now define membership in a multiset as


x\in\mathcal{M} := x\in\mathrm{support}\left(\mathcal{M}\right)

It may be tempting to define multiset membership as x\in\mathcal{M} := x\in S. So why not define it this way? Consider a multiset where S = \left\{a, b, c\right\} and f(a) = 2, f(b) = 7, f(c) = 0. Here, c\in S but appears 0 times in \mathcal{M}. Since \mathrm{support}\left(\mathcal{M}\right) = \left\{a, b \right\}, we end up with a, b\in\mathcal{M}, and c \not\in\mathcal{M}—exactly the result we would expect if c occurs 0 times in \mathcal{M}.

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 \phi: S \mapsto \left(S, f\right) with f: x\mapsto 1. That is, a set S is identified with the multiset \mathcal{M} = \phi\left(S\right) over S where every element of S has a multiplicity of 1. With this mapping, we have

\mathrm{support}\left(\mathcal{M}\right) = S and

x\in S \Leftrightarrow x\in\mathrm{support}\left(\mathcal{M}\right) \Leftrightarrow x\in \mathcal{M}.

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.


One Response to Multiset membership

  1. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: