Multiset

Imagine you have a bag of fruit.

You might have two red apples. You might also have three green pears.

In math, this is called a multiset. In a normal set, you only list each thing once. But in a multiset, you can have many of the same thing.

We call the number of items a multiplicity. If you have three pears, the multiplicity is three.

You can also find the size of the group. Just add up all the items in your bag. This helps us count everything we have.

Imagine you have a bag of fruit.

You might have two red apples and three green pears. In math, this is called a multiset. A normal set only lists each item once. But a multiset lets you have many of the same thing.

We call the number of times an item appears its multiplicity. If you have three pears, the multiplicity of pears is three. You can also find the size of the group. This is called cardinality. To find it, just add up all the multiplicities. For example, a bag with two apples and three pears has a size of five.

In a multiset, the order does not matter. A bag with an apple and a pear is the same as a pear and an apple.

People have used multisets for a long time. Ancient people used tally marks to count. These marks are like multisets because they are all the same. An Indian mathematician named Bhāskarāchārya studied them around the year 1150. The word multiset was a new name given in the 1970s. Before that, people used names like bag, heap, or bunch.

Imagine you have a bag of fruit. In a normal math set, you only list each item once. But a multiset is different because it allows for repeats. You can have two red apples and three green pears in one bag. The number of times an item appears is called its multiplicity. If you have three pears, the multiplicity of pears is three. To find the total size, or cardinality, you just add the multiplicities together.

Multisets follow a few simple rules. The order of the items does not matter at all. A bag with an apple and a pear is the same as a bag with a pear and an apple. You can also combine multisets in different ways. You can find the union by taking the highest multiplicity for each item. You can find the intersection by taking the lowest multiplicity. If you want to find the sum, you simply add the multiplicities together.

People have used these ideas since the very beginning of counting. In ancient times, people used tally marks to show numbers. These marks are like multisets because they are all the same. An Indian mathematician named Bhāskarāchārya studied them around the year 1150. He looked at how to arrange these items in different ways. Later, Marius Nizolius wrote about them in the 1500s. Other thinkers like Jean Prestet and John Wallis also studied them.

Math has many names for this idea. Some people call it a bag, a heap, or a bunch. In early computer science, people called them bags. The specific word "multiset" was created in the 1970s by Nicolaas Govert de Bruijn. Even though the name is new, the math is very old. Scientists use these structures to solve hard problems. They help us understand how many ways we can pick items from a group.

You can see multisets working in many places. One example is looking at the prime factors of a number. The number 120 can be broken down into a multiset of prime factors. Another example is in algebra with the solutions to equations. Sometimes an equation has two solutions that are actually the same number. This means the solution has a multiplicity of two. This helps mathematicians keep track of every single piece of a puzzle.

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.