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 \mathbf{MSet}_X. Sums and products of multisets are defined in terms of sums and products on the class \mathbf{Card}. 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 \mathbf{SSet}_X, 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. \left|A\right| \leq \left|B\right| to mean that there exists an injective (one-to-one) mapping of sets A\to B; and
  2. \left|A\right| = \left|B\right| to mean that there exists a bijective (one-to-one and onto) mapping of sets A\to B.

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 \leq on the real numbers.

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

An irreflexive partial order on a class X is a relation on X 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 \mathbf{Card} admits a (total, reflexive) order that is consistent with these ideas. That is, \left(\mathbf{Card}, \leq\right) is

\kappa\leq\kappa for all \kappa\in\mathbf{Card};
\kappa\leq\lambda \wedge \lambda\leq\nu \:\Rightarrow\: \kappa\leq\nu for all \kappa,\lambda,\nu\in\mathbf{Card};
\kappa\leq\lambda \wedge \lambda\leq\kappa \:\Rightarrow\: \kappa = \lambda for all \kappa,\lambda\in\mathbf{Card}; and
\kappa\leq\lambda \vee \lambda\leq\kappa for all \kappa,\lambda\in\mathbf{Card}.

The last property is often expressed by saying that every pair of cardinals are comparable. The pair \left(\mathbf{Card}, \leq\right) is a special case of a (reflexive) partially-ordered class. The relation \leq 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 \mathcal{X} = \left(X,\leq\right) be a reflexive partially-ordered class, A\subseteq X, and L_A = \left\{x\in X \:|\: \left(\forall a\in A\right)x\leq a\right\}. l\in L_A is called a lower bound of A in \mathcal{X}. If, furthermore, x\leq l for all x\in L_A, then l is called the infimum of A and is denoted \inf{A}.

In general, there is no guarantee that either a lower bound or an infimum exist. If \inf{A} 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 \mathcal{X} = \left(X,\leq\right) be a reflexive partially-ordered class, A\subseteq X, and U_A = \left\{x\in X \:|\: \left(\forall a\in A\right)a\leq x\right\}. u\in U_A is called an upper bound of A in \mathcal{X}. If, furthermore, u\leq x for all x\in U_A, then u is called the supremum of A and is denoted \sup{A}.

As with lower bounds and infima, upper bounds and the supremum do not necessarily exist, and the supremum is unique whenever it does exist.

\left(\mathbf{Card}, \leq\right) has an additional property (at least in NBG set theory, including the axiom of choice): for every subclass X \subseteq\mathbf{Card}, \inf X exists. Since \leq has this property and is a total order on \mathbf{Card}, it well-orders \mathbf{Card}, and the partially-ordered class is said to be well-ordered.

Copyright © 2008 Michael L. McCliment.


3 Responses to Infima, suprema, and well-orders

  1. pschiu says:

    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!

  2. 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?

  3. pschiu says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: