In the last couple of posts about multisets, we’ve looked at two types of operations we can perform on the class Sums and products of multisets are defined in terms of sums and products on the class When we talked about the characteristic function as a way to represent the subsets of a given set, we also considered what happens when we take the maximum and minimum values of the function. This gave us another way to represent intersections and unions of subsets in which we’re now going to adapt to the context of multisets.
When we discussed cardinals for the first time, we began by taking
- to mean that there exists an injective (one-to-one) mapping of sets and
- to mean that there exists a bijective (one-to-one and onto) mapping of sets
(Since we’re using results about cardinals rather than discussing the theory of cardinals, I’m still going to sidestep the construction that justifies a number of assertions about them. I might put together a series of posts on that subject sometime later.) The class admits a (total, reflexive) order that is consistent with these ideas. That is, is
- for all
- for all
- for all and
- for all
The last property is often expressed by saying that every pair of cardinals are comparable. The pair is a special case of a (reflexive) partially-ordered class. The relation in such a class is reflexive, transitive, and antisymmetric, but not necessarily total.
We need just a bit more of the vocabulary of partially-ordered classes.
Let be a reflexive partially-ordered class, and is called a lower bound of in If, furthermore, for all , then is called the infimum of and is denoted .
In general, there is no guarantee that either a lower bound or an infimum exist. If exists, however, it is unique. (To see this, consider what happens if there are two infima for a particular set.) We also have the following dual relationship:
Let be a reflexive partially-ordered class, and is called an upper bound of in If, furthermore, for all then is called the supremum of and is denoted
As with lower bounds and infima, upper bounds and the supremum do not necessarily exist, and the supremum is unique whenever it does exist.
has an additional property (at least in NBG set theory, including the axiom of choice): for every subclass exists. Since has this property and is a total order on it well-orders and the partially-ordered class is said to be well-ordered.
Copyright © 2008 Michael L. McCliment.