nLab
multiset

Multisets

Multisets

Idea

A multiset is like a set, just allowing that the elements have multiplicities. Thus the multiset {1,1,2}\{1,1,2\} differs from the multiset {1,2}\{1,2\}, while {1,2,1}\{1,2,1\} is the same as {1,1,2}\{1,1,2\}. Multisets are useful in combinatorics. See wikipedia.

Definitions

While it is possible to take multisets as a fundamental concept in foundations, it is more common to define them in terms of sets and functions.

A multiset 𝒳=X,μ X\mathcal{X} = \langle X,\mu_X\rangle,can be defined as a set XX (its underlying set) together with a function μ X\mu_X (giving each element its multiplicity) from XX to a class of nonzero cardinal numbers. A multiset is locally finite if multiplicity takes values in the natural numbers. Many authors take all multisets to be locally finite; that is the default in combinatorics. The multiset is finite if it is locally finite and XX is a finite set. We can also define a multiset to be a function from the proper class of all objects to the class of all cardinal numbers, with the proviso that the objects whose multiplicity is nonzero form a set (the set XX above).

If we are only interested in multisets with elements drawn from a given set UU (as is common in combinatorics), then an alternative definition is very useful: a multisubset of UU is a function f:BUf\colon B \to U, where two multisubsets f:BUf\colon B \to U and f:BUf'\colon B' \to U are considered equal if there is a bijection g:BBg\colon B \to B' that makes a commutative triangle. In other words, a multisubset of UU is an isomorphism class in the slice category Set/USet/U. (Compare this to the structural definition of subset of UU as an injective function to UU.)

A multisubset of UU is locally finite if every fibre is finite; it is finite if additionally the image of ff (which corresponds to AA in the original definition) is finite. A locally finite multisubset can also be described as a function from UU to the set of natural numbers; this is just the multiplicity function μ\mu again, now with UU (rather than XX) specified as the domain and allowing the value 00 to be taken.

Operations on multisets

The operations on cardinal numbers induce operations on multisets (or on multisubsets of any given set UU).

In the following, let 𝒳=X,μ X\mathcal{X} = \langle X,\mu_X\rangle and 𝒴=Y,μ Y\mathcal{Y} = \langle Y,\mu_Y\rangle be multisets.

  • The cardinality of a multiset is given by

    |𝒳|= eXμ X(e).|\mathcal{X}| = \sum_{e\in X} \mu_X(e).
  • The intersection of multisets is the multiset whose cardinality is given by the infimum operation on cardinal numbers.

    𝒳𝒴=XY,min(μ X,μ Y).\mathcal{X}\cap\mathcal{Y} = \langle X\cap Y, \min(\mu_X,\mu_Y)\rangle.
  • The union of multisets is the multiset whose cardinality is given by the supremum operation on cardinal numbers.

    𝒳𝒴=XY,max(μ X,μ Y).\mathcal{X}\cup\mathcal{Y} = \langle X\cup Y, \max(\mu_X,\mu_Y)\rangle.
  • The set difference of multisets is the multiset given by

    𝒳\𝒴={aXY|μ X(a)>μ Y(a)},μ Xμ Y. \mathcal{X} \backslash \mathcal{Y} = \langle \{ a \in X \cup Y \;|\; \mu_X(a) \gt \mu_Y(a) \}, \mu_X - \mu_Y \rangle .
  • The sum of multisets is the multiset whose cardinality is given by addition of cardinal numbers; this has no analogue for ordinary sets.

    𝒳+𝒴=XY,μ X+μ Y.\mathcal{X}+\mathcal{Y} = \langle X\cup Y, \mu_X+\mu_Y\rangle.
  • The product of multisets (turning them into a rig) is the multiset whose cardinality is given by the product of cardinal numbers

    𝒳𝒴=XY,μ Xμ Y.\mathcal{X}\mathcal{Y} = \langle X\cap Y, \mu_X\mu_Y\rangle.

    Note that if 𝒳\mathcal{X} is a set, then 𝒳𝒳=𝒳.\mathcal{X}\mathcal{X} = \mathcal{X}.

  • The inner product of multisets is given by

    𝒳,𝒴= eXYμ X(e)μ Y(e).\langle\mathcal{X},\mathcal{Y}\rangle = \sum_{e\in{X\cap Y}} \mu_X(e) \mu_Y(e).

    Note that the inner product corresponds to the cardinality of the product

    𝒳,𝒴=|𝒳𝒴|.\langle\mathcal{X},\mathcal{Y}\rangle = |\mathcal{X}\mathcal{Y}|.

Examples

References

Last revised on August 8, 2021 at 20:07:08. See the history of this page for a list of all contributions to it.