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

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

## Multiset union

May 28, 2008

Over the past two weeks, we’ve introduced three operations on families of multisets: sums, products, and intersections. The other basic operation on families of multisets, unions, is today’s topic. As we did with the other operations, we’ll revisit the characteristic function and then adapt this to the context of multisets.

The union of two sets $A, B\in \wp\left(X\right)$ can, as we’ve already seen, be represented in terms of the characteristic function as

$C=A\cup B \:\Leftrightarrow\: \chi_C = \max\left(\chi_A, \chi_B\right)$

where the maximum is taken in the ordered field $\mathbb{F}_2$ (just as we took the minimum in this field when looking at the intersection). This maximum is, in fact, a supremum:

$\sup\left\{\chi_A\left(x\right), \chi_B\left(x\right)\right\}$ for each $x\in X$.

For any family of functions $f_i: X\to Y$, we let

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

provided that the supremum exists for each $x\in X$. Since $\mathbb{F}_2$ is finite—which ensures the existence of the suprema—and the characteristic functions are taken over a common domain, the representation of union 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 = \bigcup_{i\in I}{A_i} \:\Leftrightarrow\: \chi_A = \sup\left\{\chi_{A_i}\right\}$.

This is completely analogous to the situation we encountered with the intersection of a family of subsets of $X$, including the avoidance of the algebraic properties of $\mathbb{F}_2$.

With the intersection, we were able to construct a definition on $\mathbf{MSet}_X$ that was analogous to the definition on $\mathbf{SSet}_X$ because both codomains—$\mathbb{F}_2$ and $\mathbf{Card}$—were well-ordered, so the necessary infima were guaranteed to exist. In $\mathbb{F}_2$, we know that the suprema exist because the set is linearly ordered and finite. $\mathbf{Card}$ is linearly ordered, but not finite. This raises a question: does every set of cardinals have a supremum?

The answer to this question depends on the set theory in which one is working. In our case, the axiom of choice allows us to actually define cardinals in terms of ordinals; in particular, cardinals are defined to be the initial ordinals. An ordinal is an initial ordinal if it is not equinumerous with any smaller ordinal. Moreover, every set of ordinals has a supremum. Since cardinals are ordinals, any set $\mathcal{K}$ of cardinals has an ordinal supremum $\omega$. The cardinal $\kappa$ which is equinumerous with $\omega$ is the cardinal supremum of $\mathcal{K}$.

With this in hand, we’re ready to define the union of a family of multisets.

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 union of $\mathrm{M}$ is the set

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

The multiplicity functions $f_i$ are defined on a common domain, and every set of cardinals has a supremum. This ensures that the multiset union is well-defined on $\mathbf{MSet}_X$. We’ll deal with the properties of this operation in my next post on multisets.