Multisets

Why

We often want to discuss lists without regard to order. This is natural, for instance, in discussing number factorizations. There, the associativity and commutativity of natural multipliciation mean that the factorization $(2, 3)$ and $(3,2)$ are equivalent, in the sense that they both factor 6.

Definition

Given a set $A$, a multiset (or mset, bag) of elements of or in $A$ is a function $m: A \to \N $. In this case, the result $m(a)$ is called the multiplicity of $a \in A$. For this reason, another term for the object we have named a multiset is multiplicity function. An $a \in A$ with $m(a) \neq 0$ is called an element of the multiset.

The size (or cardinality) of a multiset $m$ is the sum of the multiplicities of its elements. In summation notation, the size is defined to be

\[ \sum_{a \in A} m(a) \]

The set

\[ \Set{a \in A}{m(a) > 0} \]

is called the support of the multiset.

Examples

A natural use for multisets is in factorizations of natural numbers.

Notation

Notation for multisets is nonstandard—here are some common in use. If $a$ and $b$ are two distinct objects and $A = \set{a, b}$ is the unordered pair containing them, the multiset $m: A \to \N $ defined by $m(a) = 2$ and $m(b) = 3$ is sometimes denoted

\[ \{ \{ a,a,b,b,b\} \} \]

or alternatively

\[ [a,a,b,b,b] \]

\[ \set{a^2, b^3} \]

As it appears to the present authors, none of these is desirable. This last notation seems to be a reference to the notation for natural powers (a sheet not required by this one) and the use of multisets in number factorizations .

Other terminology

Other authors refer to the ordered pair $(A, m)$ as the multi set, and call $A$ the underlying set. We avoid this terminology, for the reason that $\dom m = A$.