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.

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.

• 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.

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\}.\)

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.