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.


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.

Copyright © 2008 Michael L. McCliment.


Multiset sums

May 14, 2008

On Monday, we considered how the sets A\in\wp\left(X\right) can be represented as functions \chi_A: X\to \mathbb{F}_2. In fact, for every function \chi:X\to\mathbb{F}_2, we can define A_\chi = \left\{x\in X \:|\:\chi\left(x\right) = 1\right\}. Combining this with the definition of the characteristic function, we have the identities

A_{\chi_A} = A and \chi_{A_\chi} = \chi.

This actually provides the bijection between \wp\left(X\right) and the functions \chi that I mentioned immediately following the definition of the characteristic function.

Structurally, the class

\mathbf{SSet}_X := \left\{\left(X, \chi\right) \:|\: \chi: X\to\mathbb{F}_2\right\}

is very similar to the class

\mathbf{MSet}_X := \left\{(\left(X, f\right) \:|\: f: X\to\mathbf{Card}\right\}

of multisets over X. Our ability to represent the set operations on \mathbf{SSet}_X by well-defined operations in the ordered field \mathbb{F}_2 suggests that we look at some of the well-defined operations on \mathbf{Card} as a basis for formally defining the multiset operations on \mathbf{MSet}_X.

One operation on \mathbf{Card} that we have already used is the cardinal sum \sum_{i\in I}\kappa_i, which is defined for every set of cardinals \left\{\kappa_i\right\}_{i\in I}.


Let \mathcal{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I} be an indexed family of multisets. The multiset sum of \mathcal{M} is the multiset

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

Since \mathrm{dom}\left(f_i\right) = X for all i\in I, the cardinal sum on the right is well-defined and the multiset sum does indeed give us another multiset over X. For a pair of multisets, we will generally write the multiset sum in infix notation as \mathcal{M}_1 \uplus \mathcal{M}_2.

As the notation suggests, the multiset sum is related to the union operation on sets. Multiset sums, like the union of sets are both commutative and associative—these follow directly from the corresponding properties of the cardinal sum. Cardinal sums are also monotonic nondecreasing; for any cardinal sum \kappa = \sum_{i\in I} {\kappa_i} we have \kappa_i \leq \kappa for all i\in I. One consequence of this is that a cardinal sum is 0 if and only if all of its summands are 0, and so we have the following relationship between support, multiset sums, and set unions:

\mathrm{support}\left(\biguplus_{i\in I} {\mathcal{M}_i}\right) = \bigcup_{i\in I} {\mathrm{support}\left(\mathcal{M}_i\right)}.

The monotonicity of cardinal sums also ensures that the multiset sum of a family of multisets contains each of the multisets in the family:

\mathcal{M} = \biguplus_{i\in I}{\mathcal{M}_i}\:\Rightarrow\:\left(\forall i\in I\right)\left(\mathcal{M}_i\subseteq\mathcal{M}\right).

Here’s a way in which the multiset sum differs from the union of sets. Set union is idempotent—for any set X, we have X\cup X = X. The multiset sum, on the other hand, is not idempotent, as we can see by considering the sum

\left\{a\right\}\uplus\left\{a\right\} = \left\{a, a\right\} \neq \left\{a\right\}.

This last example also shows that the class of multisets with all multiplicities equal to 1 is not closed under multiset sums.

Copyright © 2008 Michael L. McCliment.

The characteristic function of a subset

May 12, 2008

Before we talk about operations (union, intersection, etc.) on multisets, it will be helpful to talk a bit more about a particular construction associated with the power set of a set.

To start with, let’s look at the finite field \mathbb{F}_2. The operation tables for \mathbb{F}_2 are:

\begin{array}{r|rr} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} and \begin{array}{r|rr} \cdot & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \\ \end{array}

If we take 0 as false and 1 as true, then multiplication corresponds to conjunction \left(\wedge\right) in classical logic and addition corresponds to exclusive disjunction \left(\underline{\vee}\right).


Let X be a set and A\subseteq X. The characteristic function of A (relative to X) is the function \chi_A: X\to \mathbb{F}_2 defined by

\chi_A: x\mapsto \left\{ \begin{array}{r@{\quad:\quad}l} 0 & x\not\in A \\ 1 & x\in A \end{array} \right.

With this definition, we actually have a bijective correspondence between the power set \wp\left(X\right) and the functions \left\{\chi \: | \: \chi: X\to\mathbb{F}_2\right\}.

Let’s consider the sums and products of characteristic functions. If A, B\subseteq X, then \chi_A + \chi_B and \chi_A\chi_B are both well defined functions from X to \mathbb{F}_2—in other words, the sum and the product of two characteristic functions are again characteristic functions for some subsets of X.

For the product \chi_C = \chi_A\chi_B, we will have \chi_C\left(x\right) = 1 if and only if \chi_A\left(x\right) = \chi_B\left(x\right) = 1, so the product yields the characteristic function of the set C = A \cap B. This isn’t particularly surprising, since multiplication in \mathbb{F}_2 corresponds to logical conjunction. The sum, however, does not correspond to intersection (remember that the sum in \mathbb{F}_2 corresponds to exclusive disjunction). If \chi_D = \chi_A + \chi_B, then \chi_D\left(x\right) = 1 whenever exactly one of \chi_A\left(x\right) and \chi_B\left(x\right) equals 1, so we have D = A\vartriangle B, the symmetric difference.

Using these two results, we can easily determine the formulas involving characteristic functions that correspond to the other typical set operations. For the difference (relative complement) of two subsets of a set X, we have

C = A - B = A\vartriangle \left(A\cap B\right) \:\Leftrightarrow\:\chi_C = \chi_A + \chi_A\chi_B.

One of the identities among the set operations applied to \wp\left(X\right) is A \cup B = X - \left(\left(X-A\right)\cap\left(X-B\right)\right). The characteristic function \chi_X is the constant value 1; combining this identity with the previous results, we find that

\begin{aligned} A\cup B &\Leftrightarrow 1 + 1\left(1+1\chi_A\right)\left(1+1\chi_B\right)\\ &\Leftrightarrow \chi_A+\chi_B+\chi_A\chi_B.\end{aligned}

Incidentally, in \mathbb{F}_2 each element is its own additive inverse, so we have a - b = a + b for all a, b\in \mathbb{F}_2, so each of the formulas we have derived above can also be expressed in terms of subtraction.

If we further consider \mathbb{F}_2 as an ordered field, we obtain two additional ways to represent unions and intersections in terms of their characteristic functions:

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


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

One final observation. If A \subseteq B \subseteq C and \chi_A: B\to \mathbb{F}_2 is the characteristic function of A relative to B, then \chi_A has a unique extension \chi^{\,\prime}_A: C\to \mathbb{F}_2 defined by

\chi^{\,\prime}_A: x\mapsto\left\{ \begin{array}{r@{\quad:\quad}l} 0 & x\not\in B \\ \chi_A\left(x\right) & x\in B \end{array} \right.

In order for the sums and products of characteristic functions to be well-defined, they must have a common domain. The existence of this unique extension ensures that we can always find a common domain in which to represent any family of sets by their characteristic functions.

Copyright © 2008 Michael L. McCliment.