# Multiset

A **multiset** (a.k.a. bag, mset) is a *generalization* of a set where repetition of elements matters. For instance, \(\{1, 2, 3\}\) and \(\{2, 1, 3\}\) can be seen as the same multiset, but \(\{1, 1, 2, 3\}\) is different multiset due to repetition of the element \(1\). 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, \(\{a, a, b, c, b\}\). It can also be denoted by listing the elements and their multiplicities as colon-separated pairs: for example, \(\{a: 2, b:2, c: 1\},\) which avoids confusing it with a normal set.

## Terminology

- We can write \(a \in^n A\) if element \(a\) occurs in the multiset \(A\)
**at least**\(n\) times.

- For example, \(1 \in^2 \{1,2,3,1,1\}\), \(1 \in^3 \{1,2,3,1,1\}\), \(4 \in^0 \{1,2,3,1,1\}.\)

- Multiplicity of an element \(a \in A\) is denoted by \(\nu_A(a)\), 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 \(A = \{1,2,3,1,1\}\), then \(\nu_A(1) = 3, \nu_A(2) = 1, \nu_A(4) = 0.\)

- We say that multisets \(A, B\) are equal, denoted \(A = B\), if and only if multiplicities of
**all**elements are the same in \(A\) and \(B.\) - We say that multiset \(A\) is a
**multisubset**of \(B\), denoted \(A \subseteq B\), if and only if multiplicities of**all**elements in \(A\) are**less than or equal to**the multiplicities of those elements in \(B\).

- For example, \(\{1, 1, 2\} \subseteq \{1, 2, 2, 3, 1\}.\)

- \(A\) is a proper multisubset of \(B\), denoted \(A \subset B\), if and only if \(A \subseteq B\) and \(A \neq B\).

- For example, \(\{1, 1, 2\} \subset \{1, 1, 2, 3\}\), but \(\{1, 1, 2\} \not\subset \{1, 1, 2\}.\)

- Cardinality of multiset \(|A|\) is defined as the number of elements in it, where each element might be counted multiple times due to its multiplicity.

- For example, \(\big|\{1, 2, 3, 3, 1, 2\}\big| = 6.\)

- Empty multiset can be denoted by \(\emptyset\) or \(\{\}\).
- Powerset of a multiset \(\mathcal{P}(A)\) is a
**set**consiting of all multisubsets of set \(A\).

- For example, \(\mathcal{P}\big(\{1, 1, 2\}\big) = \big\{\emptyset, \{1\}, \{2\}, \{1, 1\}, \{1, 2\}, \{1, 1, 2\}\big\}.\)

- Universal multiset \(U\) is a multiset containing all relevant elements with relevant multiplicities.

## Operations with Multisets

**Union:** \(A \cup B\) is a multiset where multiplicity of each element is \(\max\{\nu_A, \nu_B\}\).

- For example, \(\{1, 1, 2\} \cup \{2, 2, 3\} = \{1, 1, 2, 2, 3\}.\)

**Intersection:** \(A \cap B\) is a multiset where multiplicity of each element is \(\min\{\nu_A, \nu_B\}\).

- For example, \(\{1, 1, 2\} \cap \{2, 2, 3\} = \{2\}.\)

**Sum:** \(A + B\) is a multiset where multiplicity of each element is \(\nu_A + \nu_B\).

- For example, \(\{1, 1, 2\} + \{2, 2, 3\} = \{1,1,2,2,2,3\}.\)

**Difference:** \(A - B\) is a multiset where multiplicity of each element is \(\max\{\nu_A - \nu_B, 0\}\).

- For example, \(\{1, 1, 2\} - \{2, 2, 3\} = \{1, 1\}\) and \(\{2, 2, 3\} - \{1,1,2\} = \{2, 3\}.\)

**Complement:** \(A^c\) is a defined to be \(U - A\), where \(U\) is the universal set.

- For example, if \(U = \{1, 1, 1, 2, 2, 3\}, A = \{1, 2, 3\}\), then \(A^c = \{1, 1, 2\}.\)

## Applications

Multisets are ideal for handling prime factorizations of numbers.

For example, \(630 = 2 \times 3^2 \times 5 \times 7\) can be thought of as multiset \(\{2:1, 3:2, 5:1, 7:1\},\) 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.