Properties of multiset union

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$ .

Like this:

Be the first to like this post.

This entry was posted on Wednesday, June 4th, 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.

M	T	W	T	F	S	S
« May
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

A Singular Contiguity

Properties of multiset union

Like this:

Leave a Reply Cancel reply

Pages

Recent Posts

Archives

Blogroll

Follow “A Singular Contiguity”