Definition:Multiset

From ProofWiki

Jump to: navigation, search

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.

Formally we define a multiset to be a set $S$ together with a map $\mu : S\to \N$ (here $\N$ does not include $0$).

For $s \in S$ the natural number $\mu(s)$ is called the mutliplicity of $s$.

Note that the multiplicities of elements if 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.

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

Let $(S,\mu)$ and $(T,\nu)$ be multisets.

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

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

To distinguish multisets from sets, sometimes multisets are written with double braces, e.g.:

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