Properties of multiset intersection

Today, we’ll examine the properties of the multiset intersection that we defined yesterday.

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(\bigcap_{i\in I}{\mathcal{M}_i}\right) = \bigcap_{i\in I}{\mathrm{support}\left(\mathcal{M}_i\right)}.

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

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

(iv) \bigcap_{i\in I}{\mathcal{M}_i} \subseteq \:\cdot\!\!\!\!\!\!\;\bigcup_{i\in I}{\mathcal{M}_i}.

The proof of part (i) is a straightforward series of equivalencies:

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

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

Recalling that the cardinal sum is a monotonic nondecreasing operation, we see that

\inf f_i\left(x\right) \leq f_i\left(x\right) \leq \sum_{i\in I}{f_i\left(x\right)}

for all x\in X, which proves part (iii).

Part (iv) requires only slightly more work. To begin with, consider a family \left\{\kappa_i\right\}_{i\in I} of cardinals. If there exists some i\in I such that \kappa_i = 0, then \prod_{i\in I}{\kappa_i} = 0. If, however, no such i\in I exists, then

\kappa_i\leq\prod_{i\in I}{\kappa_i} for all i\in I.

(This relies on the axiom of choice, which we have been assuming from the outset.) In other words, the product of any family of nonzero cardinals is monotonic nondecreasing.

Let x\in\bigcap_{i\in I}{\mathcal{M}_i}. If there exists some i\in I such that x\not\in\mathcal{M}_i, then the multiplicity of x in the intersection would be 0, contradicting the fact that x is a member of the intersection. Since f_i\left(x\right)\neq 0 for all i\in I, we have

\inf f_i\left(x\right) \leq f_i\left(x\right) \leq \prod_{i\in I}{f_i\left(x\right)}.

For x\not\in\bigcap_{i\in I}{\mathcal{M}_i}, we have

\inf f_i\left(x\right) = 0 = \prod_{i\in I}{f_i\left(x\right)}.

In either case, \inf f_i\left(x\right) \leq \prod_{i\in I}{f_i\left(x\right)} for all x\in X, and (iv) holds.

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: