Multiset products

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.


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.


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.


One Response to Multiset products

  1. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: