Main Index Computer Science Data Structures
  Subject Index
comment on the page

Multiset

A multiset 1  is a generalization of the concept of a set.  Its main idea is to allow a member of a multiset to have a multiple membership, while in a set each member can only have one membership.

Starting with classical set theory ,  a multiset is formally defined as a pair typeset structure where typeset structure is a set and typeset structure is a function from typeset structure to the set typeset structureof positive integers. The set typeset structure is called the underlying set of elements, and  the value typeset structure of function typeset structure at typeset structure gives the multiplicity (that is, number of occurrences) of typeset structure in typeset structure.

A multiset becomes a set if the multiplicity of every element is equal to one.

The cardinality of a finite set is defined as a number of its elements.  If we extend  the concept of set indicator function typeset structure by releasing the constraint that the values are 0 and 1 only and define it as the multiplicity of the corresponding element then the cardinality of multiset typeset structure is again given by formula

| M | = Underscript[∑, x ∈ M] 1 _ M (x) .

The concepts of intersection, union, subset, and Cartesian product of multisets are defined by formulas

If typeset structure then typeset structure for each typeset structure.

If typeset structure are two multisets of a multiset typeset structure, then

FormBox[RowBox[{1 _ (A ∩ B) = min {1 _ A, 1 _ B} = 1 _ A · 1 _ B, , ,, Cell[]}], TraditionalForm]

1 _ (A ∪ B) = max {1 _ A, 1 _ B} = 1 _ A + 1 _ B - 1 _ A · 1 _ B,

1 _ (X \ A) = 1 _ X - 1 _ A .

1 _ (A × B) (x, y) = 1 _ A (x) · 1 _ B (x) .

The number of multisets of cardinality typeset structure, with elements taken from a set of cardinality typeset structure is given by the binomial coefficients typeset structure. This common value is often called multiset coefficient and denoted typeset structure.

To see this represent the multiset, say typeset structure in the form

• • • | • • | • • • | • • .

This is a multiset of cardinality typeset structure made of elements of a set of cardinality typeset structure. The number of all signs including both dots and vertical lines is typeset structure, typeset structure dots and typeset structure vertical lines.

Thus the number of multisets of cardinality typeset structure made of elements of a set of cardinality typeset structure equals the number of ways to arrange the typeset structure  vertical lines among the typeset structure symbols.  Generally,  it is the number of ways to arrange the typeset structure dots among the typeset structure characters. This is given by the binomial coefficient typeset structure. This clearly equals the number of subsets of cardinality typeset structure of a set of cardinality typeset structure.

Example: A free commutative monoid typeset structure with a set of generators typeset structure can be viewed as the set of finite multisets with elements drawn from typeset structure, equipped with the obvious addition operation. Another interpretation of such monoids is as finite formal sums of elements of typeset structure with positive integral coefficients.

Notes

1 The term multiset goes back to Nicolaas Govert de Bruijn in the 1970's. The word multiset is often shortened to mset. According to some sources it is an abbreviation of multiple-membership set.  Also used names for this concept are  bag, bunch, weighted set, occurrence set, heap, sample, or fireset  (from finitely repeated element set).

References

[1]  Blizard, W. D. (1988). Multiset theory. Notre Dame J. Formal Logic , 30(Number 1), 36-66.

Cite this web-page as:

Štefan Porubský: Multiset.

Page created  .