## Cardinality

In defining multisets, we have already used the class $\mathbf{Card}$ of cardinals. Cardinals arise in set theory as a measure of the ‘size’ of a set; every set is equinumerous with a unique cardinal. (The formal definition of the cardinals relies on quite a bit more than I’m presenting here; see, for example, Chapter 3 of Mendelson’s Introduction to Mathematical Logic, 4th ed. (1997) for a discussion of the formal definition of the ordinals, and how to use the axiom of choice to define the cardinals in terms of the ordinals.) For any set $S$, the cardinality of $S$, written $\left|S\right|$, is the unique $\kappa \in \mathbf{Card}$ that is equinumerous with $S$.

In order to define the cardinality of a multiset, we’ll need a definition related to cardinal arithmetic.

Definition

Let $I$ be a set, $\left\{\kappa_i\right\}_{i\in I}$ be a family of cardinals, and $\left\{A_i\right\}_{i\in I}$ be a family of pariwise disjoint sets such that $\left|A_i\right| = \kappa_i$ for $i\in I$. The sum of this family of cardinals is

$\sum_{i\in I} \kappa_i := \left| \bigcup_{i\in I} A_i \right|.$

The axiom of union ensures that $\mathcal{A} = \bigcup_{i\in I} A_i$ exists as a set, so it has a unique cardinal. It can also be proven that $\left|\mathcal{A}\right|$ does not depend on the choice of sets $A_i$, so the sum is well defined.

Definition

Let $\mathcal{M} = \left(S, f\right)$ be a multiset. The cardinality of $\mathcal{M}$ is

$\left|\mathcal{M}\right| := \sum_{x\in S} f\left(x\right).$

Based on their cardinality, sets can be classified as finite, infinite, denumerable, etc. This classification extends to multisets in the obvious way.

If $\mathcal{M} = \left(S, f: x\mapsto 1\right)$, then $\left|S\right| = \left|\mathcal{M}\right|$. This is exactly what we would expect of the multisets that correspond to their underlying sets.