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 can, as we’ve already seen, be represented in terms of the characteristic function as
where the maximum is taken in the ordered field (just as we took the minimum in this field when looking at the intersection). This maximum is, in fact, a supremum:
for each .
For any family of functions , we let
provided that the supremum exists for each . Since 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 . That is, for any family where each , we have
This is completely analogous to the situation we encountered with the intersection of a family of subsets of , including the avoidance of the algebraic properties of .
With the intersection, we were able to construct a definition on that was analogous to the definition on because both codomains— and —were well-ordered, so the necessary infima were guaranteed to exist. In , we know that the suprema exist because the set is linearly ordered and finite. 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 of cardinals has an ordinal supremum . The cardinal which is equinumerous with is the cardinal supremum of .
With this in hand, we’re ready to define the union of a family of multisets.
Let be a family of multisets over a set . The multiset union of is the set
The multiplicity functions are defined on a common domain, and every set of cardinals has a supremum. This ensures that the multiset union is well-defined on . We’ll deal with the properties of this operation in my next post on multisets.
Copyright © 2008 Michael L. McCliment.