Multiset
A multiset (a.k.a. bag, mset) is a generalization of a set where repetition of elements matters. For instance, and can be seen as the same multiset, but is different multiset due to repetition of the element . Multisets have a lot of similarities with sets and can be useful in applications where normal sets aren't enough, for example, in prime factorizations of numbers.
Definition of a Multiset
A multiset is a set-like, unordered collection where multiplicity of elements matters. Multiplicity of an element is defined as the number of times it occurs in the multiset. It is usually denoted by listing its elements, separated by commas, between curly braces: for example, . It can also be denoted by listing the elements and their multiplicities as colon-separated pairs: for example, which avoids confusing it with a normal set.
Terminology
- We can write if element occurs in the multiset at least times.
- For example, , ,
- Multiplicity of an element is denoted by , where multiplicity means the number of times the element occurs in the multiset. If the element is not in the multiset, its multiplicity is zero.
- For example, if , then
- We say that multisets are equal, denoted , if and only if multiplicities of all elements are the same in and
- We say that multiset is a multisubset of , denoted , if and only if multiplicities of all elements in are less than or equal to the multiplicities of those elements in .
- For example,
- is a proper multisubset of , denoted , if and only if and .
- For example, , but
- Cardinality of multiset is defined as the number of elements in it, where each element might be counted multiple times due to its multiplicity.
- For example,
- Empty multiset can be denoted by or .
- Powerset of a multiset is a set consiting of all multisubsets of set .
- For example,
- Universal multiset is a multiset containing all relevant elements with relevant multiplicities.
Operations with Multisets
Union: is a multiset where multiplicity of each element is .
- For example,
Intersection: is a multiset where multiplicity of each element is .
- For example,
Sum: is a multiset where multiplicity of each element is .
- For example,
Difference: is a multiset where multiplicity of each element is .
- For example, and
Complement: is a defined to be , where is the universal set.
- For example, if , then
Applications
Multisets are ideal for handling prime factorizations of numbers.
For example, can be thought of as multiset which is its prime factorization.
Now,
- multiplication of two integers is similar to summing their prime factorizations;
- division is similar to difference;
- lcm is similar to union;
- gcd is similar to intersection;
- integer dividing other integer can be thought of as prime factorization of one being subset of other's prime factorization.