Multiset

In mathematics, a multiset is a structure that expands the traditional idea of a set. In a standard set, each element is unique and can only appear once. A multiset, however, allows for multiple instances of the same element. This concept is often called a bag, an mset, or a heap. It is useful because it tracks not just what is present, but how many times each item appears.

To understand how a multiset works, you must understand multiplicity. Multiplicity is the number of times a specific element occurs within the multiset. For example, if you have a multiset containing the elements {a, a, b}, the element 'a' has a multiplicity of 2. The element 'b' has a multiplicity of 1. The total size of the multiset is called its cardinality. To find the cardinality, you simply sum the multiplicities of all its elements. In the example {a, a, b}, the cardinality is 3.

Mathematically, a multiset is defined as an ordered pair. The first part is a set called the universe or the underlying set. The second part is a function that maps each element to a non-negative integer. This function provides the multiplicity for every element in the universe. If an element is not in the multiset, its multiplicity is 0. The collection of elements with a multiplicity greater than zero is called the support, root, or carrier of the multiset.

Multisets follow specific rules for combining and comparing. Unlike tuples, the order of elements does not matter. The multiset {a, b} is identical to {b, a}. You can perform several operations on them. The union of two multisets takes the maximum multiplicity for each element found in either set. The intersection takes the minimum multiplicity. The sum of two multisets adds their multiplicities together. Finally, the difference subtracts the multiplicities of one multiset from another.

While the term "multiset" was coined by Nicolaas Govert de Bruijn in the 1970s, the concept is ancient. Early humans used multisets implicitly when they used tally marks to represent numbers. In a collection of tally marks, each mark is an indistinguishable unit. The first formal study of multisets is attributed to the Indian mathematician Bhāskarāchārya around 1150. He explored the permutations of multisets. Later, Marius Nizolius mentioned the concept in the 1500s. In the 1600s, Athanasius Kircher and Jean Prestet studied multiset permutations. John Wallis provided more detail on these rules in 1685.

Modern mathematics has expanded these ideas significantly. In the 20th century, Hassler Whitney described generalized sets. In 1987, Monro investigated the category of multisets. He defined a multiset using an equivalence relation between elements of the same sort. He also introduced the term "multinumber," which is a function representing multiplicity. These formal structures allow mathematicians to handle complex data where repetition is essential.

We see multisets in action in many scientific fields. One common example is the prime factorization of a number. The number 120 can be represented as the multiset of its prime factors: {2, 2, 2, 3, 5}. In algebra, the fundamental theorem of algebra states that the complex solutions of a polynomial equation of degree $n$ form a multiset with a cardinality of $n$. This ensures that even if solutions repeat, the total count remains accurate.

Another advanced application involves the eigenvalues of a matrix. An eigenvalue can have different types of multiplicities. There is the multiplicity as a root of the characteristic polynomial. There is also the multiplicity as a root of the minimal polynomial. Finally, there is the geometric multiplicity, which relates to the dimension of the kernel. These different values can define three entirely different multisets of eigenvalues for the same matrix. This complexity shows why multisets are such a vital tool in higher mathematics.