Definition:Multiset

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.


Definition

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.


Equality

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


Notation

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.


Example

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