In defining multisets, we have already used the class 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 , the cardinality of , written , is the unique that is equinumerous with .

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

Definition

Let be a set, be a family of cardinals, and be a family of pariwise disjoint sets such that for . The sum of this family of cardinals is

The axiom of union ensures that exists as a set, so it has a unique cardinal. It can also be proven that does not depend on the choice of sets , so the sum is well defined.

Definition

Let be a multiset. The cardinality of is

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

If , then . This is exactly what we would expect of the multisets that correspond to their underlying sets.

This entry was posted on Wednesday, April 30th, 2008 at 4:00 am and is filed under Mathematics, Multisets. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.