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.

Advertisements

Properties of multiset intersection

May 27, 2008

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.


Multiset products

May 19, 2008

When we looked at the characteristic function for the subset of a set, we started by examining both sums and products of the characteristic function in \mathbb{F}_2. Last week, we looked at the multiset sum, which we defined in terms of the cardinal sum that we’ve been using for a while now. To consider the multiset analogue of the products of characteristic functions, we need another bit of cardinal arithmetic.

Definition

Let I be a set, \left\{\kappa_i\right\}_{i\in I} be a family of cardinals, and \left\{A_i\right\}_{i\in I} be a family of sets such that \left|A_i\right| = \kappa_i for i\in I. The product of this family of cardinals is

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

For infinite index sets i\in I, the axiom of choice ensures that the set product \mathcal{A} = \prod_{i\in I}{A_i} is not empty. As with the sum, it is possible to prove that \left|\mathcal{A}\right| does not depend on the choice of sets A_i, and so the product is well-defined.

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 product of \mathcal{M} is the multiset

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

As we saw with the multiset sum, \mathrm{dom}\left(f_i\right) = X for all i\in I. The cardinal product on the right is therefore well-defined, and the result is again a multiset over X. Unsurprisingly, we also use the infix notation \mathcal{M}_1 \cdot\!\!\!\!\cup\, \mathcal{M}_2 when dealing with just a pair of multisets. This binary operation on \mathbf{MSet}_X is both commutative and associative.

The cardinal product satisfies the equation 0\cdot\kappa = 0 for all \kappa\in\mathbf{Card}. It follows that x\in\mathrm{support}\left(\mathcal{M}\right) if and only if f_i(x) \neq 0 for all i\in I. This gives us the following identity:

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

As a binary operation on \mathbf{MSet}_X, the multiset product is not in general idempotent. Unlike the multiset sum, however, the class of multisets \left(X, f_i\right) where f_i\left(X\right)\subseteq\left\{0,1\right\} is closed under multiset products. For this class, it is even idempotent. Even more suggestive is the fact that x\in \mathcal{M}_1 \cdot\!\!\!\!\cup\, \mathcal{M}_2 if and only if x\in\mathcal{M}_1 and x\in\mathcal{M}_2.

These observations raise a question: is the multiset product a good candidate to be viewed as an extension to multisets of the intersection of sets? Let’s consider the set X = \left\{a, b, c\right\} and the multisets \mathcal{M}_1 = \left\{a^2, b^4, c^2\right\} and \mathcal{M}_1 = \left\{a, b^0,  c^5\right\} (the expression x^\kappa indicates that \kappa = f\left(x\right) is the multiplicity of x in the given multiset). Here, we have

\mathcal{M}_1 \cdot\!\!\!\!\cup\, \mathcal{M}_2 = \left\{a^2, b^0, c^{10}\right\} \not\subseteq \mathcal{M}_1.

This is contrary to the intuitive idea that an intersection should always be contained in every multiset that participates in the intersection. Counterintuitive results aren’t always wrong. Given the notation, however, we can easily guess that we will soon see an operation that is a better choice to consider as an intersection of multisets.

Copyright © 2008 Michael L. McCliment.