A multiset is like a set, just allowing that the elements have multiplicities. Thus the multiset $\{1,1,2\}$ differs from the multiset $\{1,2\}$, while $\{1,2,1\}$ is the same as $\{1,1,2\}$. Multisets are useful in combinatorics. See wikipedia.
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 $\mathcal{X} = \langle X,\mu_X\rangle$,can be defined as a set $X$ (its underlying set) together with a function $\mu_X$ (giving each element its multiplicity) from $X$ 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 $X$ 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 $X$ above).
If we are only interested in multisets with elements drawn from a given set $U$ (as is common in combinatorics), then an alternative definition is very useful: a multisubset of $U$ is a function $f\colon B \to U$, where two multisubsets $f\colon B \to U$ and $f'\colon B' \to U$ are considered equal if there is a bijection $g\colon B \to B'$ that makes a commutative triangle. In other words, a multisubset of $U$ is an isomorphism class in the slice category $Set/U$. (Compare this to the structural definition of subset of $U$ as an injective function to $U$.)
A multisubset of $U$ is locally finite if every fibre is finite; it is finite if additionally the image of $f$ (which corresponds to $A$ in the original definition) is finite. A locally finite multisubset can also be described as a function from $U$ to the set of natural numbers; this is just the multiplicity function $\mu$ again, now with $U$ (rather than $X$) specified as the domain and allowing the value $0$ to be taken.
The operations on cardinal numbers induce operations on multisets (or on multisubsets of any given set $U$).
In the following, let $\mathcal{X} = \langle X,\mu_X\rangle$ and $\mathcal{Y} = \langle Y,\mu_Y\rangle$ be multisets.
The cardinality of a multiset is given by
The intersection of multisets is the multiset whose cardinality is given by the infimum operation on cardinal numbers.
The union of multisets is the multiset whose cardinality is given by the supremum operation on cardinal numbers.
The set difference of multisets is the multiset given by
The sum of multisets is the multiset whose cardinality is given by addition of cardinal numbers; this has no analogue for ordinary sets.
The product of multisets (turning them into a rig) is the multiset whose cardinality is given by the product of cardinal numbers
Note that if $\mathcal{X}$ is a set, then $\mathcal{X}\mathcal{X} = \mathcal{X}.$
The inner product of multisets is given by
Note that the inner product corresponds to the cardinality of the product
…
Mathematics of Multisets, Apostolos Syropoulos
Categorical Models of Multisets, Apostolos Syropoulos
An Overview of the Applications of Multisets, D. Singh, A. M. Ibrahim, T. Yohanna and J. N. Singh
Last revised on December 9, 2022 at 18:44:30. See the history of this page for a list of all contributions to it.