Definition:Multiset

This page has been identified as a candidate for refactoring of medium complexity. Until this has been finished, please leave {{Refactor}} in the code. New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code.

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.

Definition

A multiset is a pair $\struct {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 $\map \mu s$ 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.

Equality

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

Let $\struct {S, \mu}$ and $\struct {T, \nu}$ be multisets.

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

That is, $\map \mu s = \map \nu {\map \sigma s}$ for all $s \in S$.

Notation

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

$\multiset {1, 2, 3, 4}$

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.

Example

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

Technical Note

The $\LaTeX$ code for \(\multiset {a, b, b, c}\) is \multiset {a, b, b, c} .

This command is specific to $\mathsf{Pr} \infty \mathsf{fWiki}$.

The underlying conventional $\LaTeX$ implementation to achieve this is:

\left\lbrace \! \left\lbrace {a, b, b, c} \right\rbrace \! \right\rbrace}