Infima, suprema, and well-orders

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

1. to mean that there exists an injective (one-to-one) mapping of sets and
2. to mean that there exists a bijective (one-to-one and onto) mapping of sets

Partial orders: reflexive and irreflexive

There are two common, non-equivalent definitions for a partial order on a set. The two are related in precisely the way one would expect from considering the normal order relations and on the real numbers.

A reflexive partial order on a class is a relation on that is reflexive, transitive, and antisymmetric. An arbitrary reflexive partial order is usually written as This may also be called a non-strict or weak partial order.

An irreflexive partial order on a class is a relation on that is irreflexive and transitive. An arbitrary irreflexive partial order is usually written as This may also be called a strict or strong partial order. Irreflexive partial orders are necessarily asymmetric.

(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

reflexive

for all

transitive

for all

antisymmetric

for all and

total

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.

Definition

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:

Definition

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.

---

Possibly related posts: (automatically generated)

• Orders
• Halmos 1.1, page 11
• Partial classes vs. plugin architecture for extensibility