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