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 and the operations on . At the time, we noted that the intersection of two sets is represented in terms of the characteristic function as

where the minimum is taken in the ordered field . For each , this minimum is just .

Given a family of functions , we let

.

Since 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 . That is, for any family where each , we have

.

We also saw a representation of intersections as the product of the characteristic functions. When dealing with sets in , the two representations correspond to the same objects and operations in the class . 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 and arithmetic on 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:

Definition

Let be a family of multisets over a set . The multiset intersection of is the set

.

The multiplicity functions are defined on a common domain, and is well-ordered by the usual relation . Just as we found with the characteristic function, these facts are sufficient to ensure that the multiset intersection is always well-defined on .

As usual, when contains only two multisets, we will use the infix notation for the intersection. In this case, is an associative and commutative binary operation on . Next time, we’ll look at some of the properties of multiset intersections.

This entry was posted on Monday, May 26th, 2008 at 4:00 am and is filed under Mathematics, Multisets. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

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

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