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:
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.
Copyright © 2008 Michael L. McCliment.