Multiset operations as binary operations (part 1)

June 9, 2008

Review: Associativity, commutativity, and idempotence

A binary operation \cdot on a set X is a function \cdot: X\times X \to X. It is usually written using an infix notation x\cdot y rather than a functional notation such as \cdot\left(x, y\right).

The operation \cdot is associative if and only if a\cdot\left(b\cdot c\right) = \left(a\cdot b\right)\cdot c for all a,b,c\in X. It is commutative if and only if a\cdot b = b\cdot a for all a,b\in X. It is idempotent if and only if a\cdot a = a for all a\in X.

We’ve defined four operations on families of multisets \left\{\mathcal{M}_i\right\}_{i\in I} where \mathcal{M}_i \in \mathbf{MSet}_X for all i\in I: sums, products, intersections, and unions. As I’ve already commented in a couple of places, we can restrict our attention to families where \left|I\right| = 2. This provides us with four binary operations on \mathbf{MSet}_X. Today’s post collects together the properties of these binary operations.

Proposition 1: The operations \uplus, \:\cdot\!\!\!\!\cup, \cap, and \cup on \mathbf{MSet}_X are all associative and commutative.

Proof:

Let \mathcal{M}_1, \mathcal{M}_2, \mathcal{M}_3 \in \mathbf{MSet}_X. The first four parts follow directly from the associativity and commutativity of + and \cdot as binary operations on \mathbf{Card}.

Associativity of \uplus.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \uplus \left(\mathcal{M}_2 \uplus  \mathcal{M}_3\right) & \left(X, f_1 + \left(f_2 + f_3\right)\right) \\ & \left(X, \left(f_1 + f_2\right) + f_3\right) \\ & \left(\mathcal{M}_1 \uplus \mathcal{M}_2\right) \uplus \mathcal{M}_3\end{array}

Commutativity of \uplus.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \uplus \mathcal{M}_2& \left(X, f_1 + f_2\right) \\ & \left(X, f_2 + f_1\right) \\ & \mathcal{M}_2 \uplus \mathcal{M}_1\end{array}

Associativity of \:\cdot\!\!\!\!\cup.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \left(\mathcal{M}_2 \:\cdot\!\!\!\!\cup\: \mathcal{M}_3\right) & \left(X, f_1 \cdot \left(f_2 \cdot f_3\right)\right) \\ & \left(X, \left(f_1 \cdot f_2\right) \cdot f_3\right) \\ & \left(\mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \mathcal{M}_2\right) \:\cdot\!\!\!\!\cup\: \mathcal{M}_3\end{array}

Commutativity of \:\cdot\!\!\!\!\cup.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \mathcal{M}_2& \left(X, f_1 \cdot f_2\right) \\ & \left(X, f_2 \cdot f_1\right) \\ & \mathcal{M}_2 \:\cdot\!\!\!\!\cup\: \mathcal{M}_1\end{array}

The remaining parts follow from the following facts:

  1. Let A, B be partially ordered sets. Then \inf \left(A \cup \left\{\inf B\right\}\right) = \inf\left(A\cup B\right) and \sup \left(A \cup \left\{\sup B\right\}\right) = \sup \left(A\cup B\right) whenever the suprema and infima exist.
  2. The supremum and infimum of every set of cardinals exist.

Associativity of \cap.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cap \left(\mathcal{M}_2 \cap \mathcal{M}_3\right) & \left(X, \inf \left\{f_1, \inf\left\{f_2, f_3\right\}\right\}\right) \\ & \left(X, \inf\left\{f_1, f_2, f_3\right\}\right) \\  & \left(X, \inf \left\{\inf\left\{f_1, f_2\right\}, f_3\right\}\right) \\ & \left(\mathcal{M}_1 \cap\mathcal{M}_2\right) \cap \mathcal{M}_3\end{array}

Commutativity of \cap.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cap \mathcal{M}_2& \left(X, \inf \left\{f_1, f_2\right\}\right) \\ & \mathcal{M}_2 \cap \mathcal{M}_1\end{array}

Associativity of \cup.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cup \left(\mathcal{M}_2 \cup \mathcal{M}_3\right) & \left(X, \sup \left\{f_1, \sup\left\{f_2, f_3\right\}\right\}\right) \\ & \left(X, \sup\left\{f_1, f_2, f_3\right\}\right) \\ & \left(X, \sup \left\{\sup\left\{f_1, f_2\right\}, f_3\right\}\right) \\ & \left(\mathcal{M}_1 \cup\mathcal{M}_2\right) \cup \mathcal{M}_3\end{array}

Commutativity of \cup.

\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cup \mathcal{M}_2& \left(X, \sup \left\{f_1, f_2\right\}\right) \\ & \mathcal{M}_2 \cup \mathcal{M}_1\end{array}

Proposition 2: The operations \cap and \cup on \mathbf{MSet}_X are idempotent.

Proof:

Let \mathcal{M}\in \mathbf{MSet}_X.

Idempotence of \cap.

\begin{array}{r@{\:=\:}l} \mathcal{M} \cap \mathcal{M}& \left(X, \inf \left\{f, f\right\}\right) \\ & \left(X, f\right) \\ & \mathcal{M}\end{array}

Idempotence of \cup.

\begin{array}{r@{\:=\:}l} \mathcal{M} \cup \mathcal{M}& \left(X, \sup \left\{f, f\right\}\right) \\ & \left(X, f\right) \\ & \mathcal{M}\end{array}

The other two operations—sum and product—are not idempotent. One counterexample is the multiset \mathcal{M} = \left\{a^3\right\}, for which we have

\mathcal{M}\uplus\mathcal{M} = \left\{a^6\right\} \neq \mathcal{M}

and

\mathcal{M}\:\cdot\!\!\!\!\cup\:\mathcal{M} = \left\{a^9\right\} \neq \mathcal{M}.

Copyright © 2008 Michael L. McCliment.


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.


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 intersection

May 26, 2008

Last Monday, I mentioned that multiset products are not the best available extension of the intersection of a family of sets so that it applies to multisets. Now that we’ve talked about the concepts of infima and well-ordering, we’re ready to define multiset intersections.

A bit further back, we discussed how characteristic functions can be used to represent subsets of a set X and the operations on \wp\left(X\right). At the time, we noted that the intersection of two sets A, B\in \wp\left(X\right) is represented in terms of the characteristic function as

C=A\cap B \:\Leftrightarrow\: \chi_C = \min\left(\chi_A,\chi_B\right)

where the minimum is taken in the ordered field \mathbb{F}_2. For each x\in X, this minimum is just \inf\left\{\chi_A\left(x\right), \chi_B\left(x\right)\right\}.

Given a family of functions f_i: X\to Y, we let

\begin{array}{lrl}\inf \left\{f_i\right\} := &g:& X\to Y \\ &&x\mapsto \inf \left\{f_i\left(x\right)\right\} \end{array}.

Since \mathbb{F}_2 is well-ordered and the characteristic functions are taken over a common domain, our representation of intersection in terms of characteristic functions extends to any family of subsets of X. That is, for any family \left\{A_i\right\}_{i\in I} where each A_i \in \wp\left(X\right), we have

A = \bigcap_{i\in I}{A_i} \:\Leftrightarrow\: \chi_A = \inf\left\{\chi_{A_i}\right\}.

We also saw a representation of intersections as the product of the characteristic functions. When dealing with sets in \wp\left(X\right), the two representations correspond to the same objects and operations in the class \mathbf{SSet}_X. However, there is an important difference between the two: the representation in terms of products relies (exclusively) on the algebraic properties of the codomain, while the representation in terms of infima relies (exclusively) on the order properties of the codomain.

The algebraic properties of the field \mathbb{F}_2 and arithmetic on \mathbf{Card} are quite different. However, both of them are well-ordered classes, so their order properties are similar in many respects. This leads us to the following definition:

Definition

Let \mathrm{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I} be a family of multisets over a set X. The multiset intersection of \mathrm{M} is the set

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

The multiplicity functions f_i are defined on a common domain, and \mathbf{Card} is well-ordered by the usual relation \leq. Just as we found with the characteristic function, these facts are sufficient to ensure that the multiset intersection is always well-defined on \mathbf{MSet}_X.

As usual, when \mathrm{M} contains only two multisets, we will use the infix notation \mathcal{M}_1 \cap \mathcal{M}_2 for the intersection. In this case, \cap is an associative and commutative binary operation on \mathbf{Mset}_X. Next time, we’ll look at some of the properties of multiset intersections.

Copyright © 2008 Michael L. McCliment.