Multiset union

Over the past two weeks, we’ve introduced three operations on families of multisets: sums, products, and intersections. The other basic operation on families of multisets, unions, is today’s topic. As we did with the other operations, we’ll revisit the characteristic function and then adapt this to the context of multisets.

The union of two sets A, B\in \wp\left(X\right) can, as we’ve already seen, be represented in terms of the characteristic function as

C=A\cup B \:\Leftrightarrow\: \chi_C = \max\left(\chi_A, \chi_B\right)

where the maximum is taken in the ordered field \mathbb{F}_2 (just as we took the minimum in this field when looking at the intersection). This maximum is, in fact, a supremum:

\sup\left\{\chi_A\left(x\right), \chi_B\left(x\right)\right\} for each x\in X.

For any family of functions f_i: X\to Y, we let

\begin{array}{lrl}\sup \left\{f_i\right\} := &g:& X\to Y \\ &&x\mapsto \sup \left\{f_i\left(x\right)\right\} \end{array}

provided that the supremum exists for each x\in X. Since \mathbb{F}_2 is finite—which ensures the existence of the suprema—and the characteristic functions are taken over a common domain, the representation of union in terms of characteristic functions extends to any family of subsets of X. That is, for any family \left\{A_i\right\}_{i\in I} where each A_i \in \wp\left(X\right), we have

A = \bigcup_{i\in I}{A_i} \:\Leftrightarrow\: \chi_A = \sup\left\{\chi_{A_i}\right\}.

This is completely analogous to the situation we encountered with the intersection of a family of subsets of X, including the avoidance of the algebraic properties of \mathbb{F}_2.

With the intersection, we were able to construct a definition on \mathbf{MSet}_X that was analogous to the definition on \mathbf{SSet}_X because both codomains—\mathbb{F}_2 and \mathbf{Card}—were well-ordered, so the necessary infima were guaranteed to exist. In \mathbb{F}_2, we know that the suprema exist because the set is linearly ordered and finite. \mathbf{Card} is linearly ordered, but not finite. This raises a question: does every set of cardinals have a supremum?

The answer to this question depends on the set theory in which one is working. In our case, the axiom of choice allows us to actually define cardinals in terms of ordinals; in particular, cardinals are defined to be the initial ordinals. An ordinal is an initial ordinal if it is not equinumerous with any smaller ordinal. Moreover, every set of ordinals has a supremum. Since cardinals are ordinals, any set \mathcal{K} of cardinals has an ordinal supremum \omega. The cardinal \kappa which is equinumerous with \omega is the cardinal supremum of \mathcal{K}.

With this in hand, we’re ready to define the union of a family of multisets.

Definition

Let \mathrm{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I} be a family of multisets over a set X. The multiset union of \mathrm{M} is the set

\mathcal{M} = \bigcup_{i\in I}{\mathcal{M}_i} := \left(X, \sup\left\{f_i\right\}\right).

The multiplicity functions f_i are defined on a common domain, and every set of cardinals has a supremum. This ensures that the multiset union is well-defined on \mathbf{MSet}_X. We’ll deal with the properties of this operation in my next post on multisets.

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: