Properties of multiset union

June 4, 2008

We defined the union of a family of multisets last week. Today we’re going to look at some basic properties of the union operation on \mathbf{MSet}_X.

Suppose \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I} is a family of multisets over X. Then the following relationships hold:

(i) \mathrm{support}\left(\bigcup_{i\in I}{\mathcal{M}_i}\right) = \bigcup_{i\in I}{\mathrm{support}\left(\mathcal{M}_i\right)}.

(ii) \mathcal{M}_i \subseteq \bigcup_{i\in I}{\mathcal{M}_i} for all i\in I.

(iii) \bigcup_{i\in I}{\mathcal{M}_i} \subseteq \biguplus_{i\in I}{\mathcal{M}_i}.

(iv) \bigcup_{i\in I}{\mathcal{M}_i} \subseteq \:\cdot\!\!\!\!\!\!\;\bigcup_{i\in I}{\mathcal{M}_i} provided that all of the multisets \mathcal{M}_i have the same support.

(v) \bigcap_{i\in I}{\mathcal{M}_i} \subseteq \bigcup_{i\in I}{\mathcal{M}_i}.

The proof of part (i), like the similar result for multiset intersections, is a straightforward series of equivalencies:

\begin{array}{r@{\:\Leftrightarrow\:}l} x\in \mathrm{support}\left(\bigcup_{i\in I}{\mathcal{M}_i}\right) & \sup f_i(x) \neq 0 \\ & \left(\exists i\in I\right)\: f_i\left(x\right)\neq 0 \\ & \left(\exists i\in I\right)\: x\in\mathrm{support}\left(\mathcal{M}_i\right) \\ & x\in\bigcup_{i\in I}{\mathrm{support}\left(\mathcal{M}_i\right)}. \end{array}

Part (ii) follows directly from the definition of the supremum of a set, since f_i\left(x\right) \leq \sup f_i\left(x\right) for all x\in X and i\in I.

To prove part (iii), start by recalling that the sum of a family of cardinals \left\{\kappa_i\right\}_{i\in I} is given by

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

where the sets A_i are disjoint and \kappa_i = \left|A_i\right| for all i\in I. Therefore, letting A_{i,x} be a family of disjoint sets such that \left|A_{i,x}\right| = f_i\left(x\right), we have

\kappa_x = \sum_{i\in I}{f_i\left(x\right)} = \left|\bigcup_{i\in I}{A_{i,x}}\right| \geq \left|A_{i,x}\right| = f_i\left(x\right)

for all i\in I and x\in X. This establishes that \kappa_x is an upper bound for f_i\left(x\right) in the linearly ordered set \left(\mathbf{Card}, \leq\right), and so \kappa_x \geq \sup f_i\left(x\right). The result in part (iii) follows immediately since this holds for all x\in X.

The proof of part (iv) is similar, but relies on the definition of the product of a family of cardinals. The product of a family of cardinals \left\{\kappa_i\right\}_{i\in I} is given by

\prod_{i\in I}{\kappa_i} = \left|\prod_{i\in I}{A_i}\right|

where \kappa_i = \left|A_i\right| for all i\in I. Letting A_{i,x} be a family of sets such that \left|A_{i,x}\right| = f_i\left(x\right), we have

\kappa_x = \prod_{i\in I}{f_i\left(x\right)} = \left|\prod_{i\in I}{A_{i,x}}\right| \geq \left|A_{i,x}\right| = f_i\left(x\right)

for all i\in I and x\in X, provided that A_{i,x} \neq \emptyset for all i\in I. This establishes that \kappa_x is an upper bound for f_i\left(x\right) in the linearly ordered set \left(\mathbf{Card}, \leq\right) whenever x\in\mathrm{support}\left(\bigcup_{i\in I}{\mathcal{M}_i}\right), which is the common support of all multisets in the family \left\{\mathrm{M}_i\right\}_{i\in I}. If x is not in this support, then \prod_{i\in I}{f_i\left(x\right)} = 0 = \sup f_i\left(x\right). In either case, \kappa_x \geq \sup f_i\left(x\right), and part (iv) follows immediately since this holds for all x\in X.

The requirement that all multisets in the family have the same support is necessary; you can see this by considering the product and union of the multisets \left\{a\right\} and \left\{b\right\}.

Finally, part (v) follows immediately from the fact that

\inf f_i\left(x\right) \leq f_i\left(x\right) \leq \sup f_i\left(x\right)

for all i\in I and x\in X.

Copyright © 2008 Michael L. McCliment.

Leave a Comment » | Mathematics, Multisets | Tagged: , , , , , , | Permalink
Posted by Michael McCliment

Multiset sums

May 14, 2008

On Monday, we considered how the sets A\in\wp\left(X\right) can be represented as functions \chi_A: X\to \mathbb{F}_2. In fact, for every function \chi:X\to\mathbb{F}_2, we can define A_\chi = \left\{x\in X \:|\:\chi\left(x\right) = 1\right\}. Combining this with the definition of the characteristic function, we have the identities

A_{\chi_A} = A and \chi_{A_\chi} = \chi.

This actually provides the bijection between \wp\left(X\right) and the functions \chi that I mentioned immediately following the definition of the characteristic function.

Structurally, the class

\mathbf{SSet}_X := \left\{\left(X, \chi\right) \:|\: \chi: X\to\mathbb{F}_2\right\}

is very similar to the class

\mathbf{MSet}_X := \left\{(\left(X, f\right) \:|\: f: X\to\mathbf{Card}\right\}

of multisets over X. Our ability to represent the set operations on \mathbf{SSet}_X by well-defined operations in the ordered field \mathbb{F}_2 suggests that we look at some of the well-defined operations on \mathbf{Card} as a basis for formally defining the multiset operations on \mathbf{MSet}_X.

One operation on \mathbf{Card} that we have already used is the cardinal sum \sum_{i\in I}\kappa_i, which is defined for every set of cardinals \left\{\kappa_i\right\}_{i\in I}.

Definition

Let \mathcal{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I} be an indexed family of multisets. The multiset sum of \mathcal{M} is the multiset

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

Since \mathrm{dom}\left(f_i\right) = X for all i\in I, the cardinal sum on the right is well-defined and the multiset sum does indeed give us another multiset over X. For a pair of multisets, we will generally write the multiset sum in infix notation as \mathcal{M}_1 \uplus \mathcal{M}_2.

As the notation suggests, the multiset sum is related to the union operation on sets. Multiset sums, like the union of sets are both commutative and associative—these follow directly from the corresponding properties of the cardinal sum. Cardinal sums are also monotonic nondecreasing; for any cardinal sum \kappa = \sum_{i\in I} {\kappa_i} we have \kappa_i \leq \kappa for all i\in I. One consequence of this is that a cardinal sum is 0 if and only if all of its summands are 0, and so we have the following relationship between support, multiset sums, and set unions:

\mathrm{support}\left(\biguplus_{i\in I} {\mathcal{M}_i}\right) = \bigcup_{i\in I} {\mathrm{support}\left(\mathcal{M}_i\right)}.

The monotonicity of cardinal sums also ensures that the multiset sum of a family of multisets contains each of the multisets in the family:

\mathcal{M} = \biguplus_{i\in I}{\mathcal{M}_i}\:\Rightarrow\:\left(\forall i\in I\right)\left(\mathcal{M}_i\subseteq\mathcal{M}\right).

Here’s a way in which the multiset sum differs from the union of sets. Set union is idempotent—for any set X, we have X\cup X = X. The multiset sum, on the other hand, is not idempotent, as we can see by considering the sum

\left\{a\right\}\uplus\left\{a\right\} = \left\{a, a\right\} \neq \left\{a\right\}.

This last example also shows that the class of multisets with all multiplicities equal to 1 is not closed under multiset sums.

Copyright © 2008 Michael L. McCliment.

7 Comments | Mathematics, Multisets | Tagged: , , , , | Permalink
Posted by Michael McCliment