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.

Copyright © 2008 Michael L. McCliment.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: