Multisets

A multiset extends the concept of a standard set by allowing elements to repeat.

Multisets are used to manage collections where the number of occurrences of each object is important.

Unlike a traditional set, where each element is unique and appears only once, a multiset allows duplicates.

Note: Multisets are particularly valuable in fields like combinatorics and group theory, where counting configurations with repetitions is often necessary.

Formally, a multiset is defined as a pair $ M = (A, m) $, consisting of:

$ A $, a set known as the "support set".
$ m: A \rightarrow \mathbb{N} $, a "multiplicity function" that assigns a positive integer to each element in the support set, indicating its frequency in the multiset. This function, $ m $, shapes the structure of the multiset.

Note: If $ m $ assigns the value 1 to every element, the multiset corresponds precisely to the support set and functions as a regular set.

The cardinality of a multiset is the total of the multiplicities for all elements, reflecting the overall number of elements, including duplicates.

A multiset can also be represented as a set of ordered pairs:

$$ M = \{ (x,m(x)): x \in A \} $$

Here, x is an element from the support set and m(x) represents how many times that element occurs.

An Example in Practice

Consider a multiset with the elements \{a, a, b, b, b, c\}

This can formally be described as $ M = (A, m) $, where:

$ A = \{a, b, c\} $ serves as the support set.
The multiplicity functions are $ m(a) = 2 $, $ m(b) = 3 $, and $ m(c) = 1 $.

The total cardinality of multiset M is determined by adding the multiplicities of its elements:

$$ |M| = m(a) + m(b) + m(c) = 6 $$

This reflects that set A consists of six items.

In this example, the set of ordered pairs is:

$$ M = \{ (a,2), (b,3), (c,1) \} $$

Example 2

Consider the number 360. Its prime factorization is:

$$ 360 = 2^3 \times 3^2 \times 5 $$

This can be represented as a multiset of 360's prime factors as follows:

$$ A = \{(2, 3), (3, 2), (5, 1)\} $$

Each pair indicates the frequency of each prime factor in the composition of 360, illustrating the application of multisets to represent repeated factors.

Example 3

Consider the polynomial:

$$ x^4 - 7x^3 + 18x^2 - 20x + 8 $$

This polynomial has two roots that appear three times, and one that appears once.

This formulation allows us to express the polynomial as:

$$ (x-2)^3 \cdot (x-1) $$

The roots can be represented as multiset elements:

$$ M = \{(2, 3), (1, 1)\} $$

Here, the pairs indicate the multiplicity of each root, underscoring how multisets can represent repeated elements within polynomial roots.

And so forth.