Multiset - Formal Definition

Formal Definition

Within set theory, a multiset may be formally defined as a 2-tuple(A, m) where A is some set and m : A → N_≥1 is a function from A to the set N_≥1 = {1, 2, 3, ...} of positive natural numbers. The set A is called the underlying set of elements. For each a in A the multiplicity (that is, number of occurrences) of a is the number m(a). If a universe U in which the elements of A must live is specified, the definition can be simplified to just a multiplicity function m_U : U → N from U to the set N = {0, 1, 2, 3, ...} of natural numbers, obtained by extending m to U with values 0 for each element not in A. This extended multiplicity function is the multiplicity function called 1_A below. Like any function, the function m may be defined as its graph: the set of ordered pairs { (a, m(a)) : a in A }. With these definitions the multiset written as { a, a, b } is defined as ({ a, b },{ (a, 2), (b, 1) }), and the multiset { a, b } is defined as ({ a, b },{ (a, 1), (b, 1) }).

The concept of a multiset is a generalization of the concept of a set. A multiset corresponds to an ordinary set if the multiplicity of every element is one (as opposed to some larger natural number). An indexed family, ( a_i ), where i is in some index-set, may define a multiset, sometimes written { a_i }, in which the multiplicity of any element x is the number of indices i such that a_i = x. The condition for this to be possible is that no element occurs infinitely many times in the family: even in an infinite multiset, the multiplicities must be finite numbers.

It is possible to extend the definition of a multiset by allowing multiplicities of individual elements to be infinite cardinals instead of natural numbers. Not all properties carry over to this generalization however, and this article uses the definition above, with finite multiplicities.