## 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:

Definition

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

Definition

$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.