From ProofWiki
Jump to: navigation, search

Informal Definition

A multiset is an extension of the concept of a set.

While a set can contain only one occurrence of any given element, a multiset may contain multiple occurrences of the same element.

Note that by this definition, a set is also classified as a multiset.


A multiset is a pair $(S, \mu)$ where:

$S$ is a set
$\mu: S \to \N_{>0}$ is a mapping to the strictly positive natural numbers

For $s \in S$ the natural number $\mu \left({s}\right)$ is called the multiplicity of $s$.

Note that the multiplicities of elements is finite: we do not allow infinitely many occurrences of the same element, though the set $S$ itself may be finite, countably infinite or uncountably infinite.


Care must be taken to define equality of multisets such that no restriction is placed on the ordering of elements.

Let $\left({S, \mu}\right)$ and $\left({T, \nu}\right)$ be multisets.

We say that $\left({S, \mu}\right)$ and $\left({T, \nu}\right)$ are equal if there exists a bijection $\sigma: S \to T$ such that $\mu = \nu \circ \sigma$.

That is, $\mu \left({s}\right) = \nu \left({\sigma \left({s}\right)}\right)$ for all $s \in S$.


To distinguish multisets from sets, sometimes multisets are written with double braces, for example:

$\left\{ {\left\{ {1, 2, 3, 4}\right\} }\right\}$

Beware the fact that such a notation is also used to mean a set containing a set, so be sure you know what notation is being used.


While $\left\{ {a, b, c, d}\right\}$ is a set, $\left\{ {\left\{ {a, b, c, c, d}\right\} }\right\}$ is a multiset.