Finite and Infinite Multisets
Recall that a set is a collection of elements. However, regular sets do not account for repetitions of elements, that is if $A = \{a, b, c \}$ and $B = \{ a, a, b, c \}$ then $A = B$ despite the set $B$ listing the element $a$ twice. In some cases, we would prefer to note that the element $a$ is contained in $B$ multiple times. If we do consider repeated elements to be counted in a set the number of times they're repeated, then we get a special type of set that we define below.
| Definition: A Multiset $A$ is a collection of elements, some of which may be repeated. If $x \in A$ then the Repetition Number of $x$ is the number of times $x$ appears in $A$. If $x$ appears an infinite number of times in $A$ then the repetition number of $x$ is $\infty$. |
Suppose that we consider the multiset of $\{ x, y, y, z, z, z \}$. Another way of representing this set is by writing corresponding repetition for each repeated element. Thus, another way to write the multiset above is:
(1)We could alternatively (but generally will not) use raised powers as the notation indicating the repetition numbers of each element:
(2)If an element, say $z$, appears an infinite number of times in a multiset then we use the following notation for compactness:
(3)Like with sets - we can define a multiset to be either a finite multiset or an infinite multiset.
| Definition: A multiset $A$ is said to be a Finite Multiset if $A$ has a finite number of distinct elements and the repetition numbers of the elements in $A$ are all finite. The multiset $A$ is said to be an Infinite Multiset otherwise. |
For example, the multiset $\{ 2 \cdot x, 4 \cdot y, 3 \cdot z \}$ is a finite multiset because this multiset has a finite number of distinct elements ($3$) and every repetition number is finite ($2$, $4$, and $3$).
The multiset $\{2 \cdot x_1, 1 \cdot x_2, ... \}$ is an infinite multiset because there are an infinite number of distinct elements. The multiset $\{ \infty \cdot x, y \}$ is also an infinite multiset because not every repetition number is finite.
We can also form what are called submultisets from multisets.
| Definition: If $A$ is a multiset then $B$ is said to be a Submultiset of $A$ if every element in $B$ is containing in $A$ and for each element $x$ in $B$ we have that the repetition number of $x$ in $B$ is less than or equal to the repetition number of $x$ in $A$. |
For example, consider the multiset $A = \{3 \cdot x, 1 \cdot y, 1 \cdot z \}$. Then $B = \{ 2 \cdot x, 1 \cdot z \}$ is a submultiset of $A$ since every element in $B$ is contained in $A$ and the repetition number of elements in $B$ are less than or equal to corresponding repetition numbers of those elements in $A$.