# 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.
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}`