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

**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.

Hey, thanks for replying over at my blog. I’m sad to say that when I first read your comment, I didn’t know what was a “class”, or what the distinction was between a class and a set. I picked up my set theory textbook, looked through it and verified that it made no mention of classes. Then I wikied it and realised that what I had been self-studying was probably naive set theory.

I have just started an undergraduate programme in mathematics and I am rather interested in set theory. While I regret that I still don’t have enough knowledge to understand your reply, at least now I know a little bit more about what I’m lacking and what direction I can head towards. Thanks again!

pschiu—

Set theory can get pretty interesting. I first started digging into it because I got curious about the “don’t worry about the paradoxes, everything we’ll use are actually sets” caveat in several textbooks.

Which set theory text are you using?

Oh wow….. so sorry, I totally did not see this comment until now. I used to use “Set Theory” by Lipschutz. Since then, I’ve taken an undergraduate course in Set theory (and still am taking at the moment) and realised that that textbook was much too basic. :S I’ve learnt what are classes, but the “biggest” set I’ve learnt to create so far are all inductive sets, and I’m not even sure how to construct, say, the set of real numbers. (or code a real number as a set) It also doesn’t seem immediately obvious to me how to prove that the “collection” of all countably infinite sets is not a set, though I guess with some hard thought I might be able to prove it. But yeah, at least now I’ve been trained enough to always verify that something is a set first before talking about its cardinality. And yeah, we’re only learning ZFC (+AC) in the course I’m taking.