## Multiset union

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.