Multiset

set-theory

Definition

Multiset

A multiset is a collection in which an object may occur more than once and its number of occurrences matters. Over a set $X$ of possible objects, a multiset $M$ is described by its multiplicity function

$$m_M:X\to {\mathbb{N}}_0,$$

where $m_M(x)$ is the number of copies of $x$ in $M$. Two multisets are equal precisely when every object has the same multiplicity:

$$M=N⟺\forall x\in X:m_M(x)=m_N(x).$$

An ordinary set is the special case in which every multiplicity is either $0$ or $1$.

Support and Size

The support of a multiset is the set of objects that occur at least once:

$$\mathrm{supp}(M):=\{x\in X\mid m_M(x)>0\}.$$

For a finite multiset, its size counts occurrences rather than only distinct objects:

$$|M|:=\sum _{x\in \mathrm{supp}(M)}{m}_M(x).$$

Example

Example

Consider

$$M=\{\{a,a,a,b,b,c\}\}=\{\{a^3,b^2,c\}\}.$$

Its multiplicities are

$$m_M(a)=3,m_M(b)=2,m_M(c)=1.$$

Therefore

$$\mathrm{supp}(M)=\{a,b,c\},|M|=3+2+1=6.$$