Multiset intersection

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:


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.


2 Responses to Multiset intersection

  1. […] Today, we’ll examine the properties of the multiset intersection that we defined […]

  2. […] of multiset union We defined the union of a family of multisets last week. Today we’re going to look at some basic properties […]

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: