# Order Relations

A partial order on a set is, roughly speaking, a relation that behaves like the relation on .

Definition. Let X be a set, and let be a relation on X. is a partial order if:

(a) (Reflexive) For all , .

(b) (Antisymmetric) For all , if and , then .

(c) (Transitive) For all , if and , then .

Example. For each relation, check each axiom for a partial order. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

(a) The relation is a partial order on .

(b) The relation is not a partial order on .

(a) For all , : Reflexivity holds.

For all , if and , then : Antisymmetry holds.

For all , if and , then : Transitivity holds.

Thus, is a partial order.

(b) For no x is it true that , so reflexivity fails.

Antisymmetry would say: If and , then . However, for no is it true that and . Therefore, the first part of the conditional is false, and the conditional is true. Thus, antisymmetry is vacuously true.

If and , then . Therefore, transitivity holds.

Hence, is not a partial order.

Example. Let X be a set and let be the power set of X --- i.e. the set of all subsets of X. Show that the relation of set inclusion is a partial order on .

Subsets A and B of X are related under set inclusion if .

If , then . The relation is reflexive.

Suppose . If and , then by definition of set equality, . The relation is symmetric.

Finally, suppose . If and , then . (You can write out the easy proof using elements.) The relation is transitive.

Here's a particular example. Let . This is a picture of the set inclusion relation on :

Definition. Let be a partially ordered set. The lexicographic order (or dictionary order) on is defined as follows: means that

(a) , or

(b) and .

Note that implies .

You can extend the definition to two different partially ordered sets X and Y, or a sequence , , ..., of partially ordered sets in the same way. The name dictionary order comes from the fact that it describes the way words are ordered alphabetically in a dictionary. For instance, "aardvark" comes before "banana" because "a" comes before "b". If the first letters are the same, as with "mystery" and "meat", then you look at the second letters: "e" comes before "y", so "meat" comes before "mystery".

In the picture above, , because . And because the x-coordinates are equal and .

Proposition. The lexicographic order on is a partial order.

Proof. First, , since and . is reflexive.

Next, suppose and . Now means that either or . The first case is impossible, since this would contradict . Therefore, . Then implies and implies . Hence, . Therefore, . is antisymmetric.

Finally, suppose and . To keep things organized, I'll consider the four cases.

(a) If and , then , so .

(b) If and , then , so .

(c) If and , then , so .

(d) If and , then and . This implies and , so .

Hence, is transitive, and this completes the proof that is a partial order.

A common mistake in working with partial orders --- and in real life --- consists of assuming that if you have two things, then one must be bigger than the other. When this is true about two things, the things are said to be comparable. However, in an arbitrary partially ordered set, some pairs of elements are comparable and some are not.

Definition. Let be a relation on a set X. x and y in X are comparable if either or .

Here's a pictorial example to illustrate the idea. You can sometimes describe an order relation by drawing a graph like the one below:

This picture shows a relation on the set

Two elements are comparable if they're joining by a sequence of edges that goes upward "without reversing direction". (Think of "bigger" elements being above and "smaller" elements being below.) It's also understood that every element satisfies .

For example, , since there's an upward segment connecting f to c. And , since there's an upward path of segments connecting f to a.

On the other hand, there are elements which are not comparable. For example, d and e are not comparable, because there is no upward path of segments connecting one to the other. Likewise, and , but h and i are not comparable.

Notice that a is comparable to every element of the set, and that for all .

Definition. Let X be a partially ordered set.

(a) An element which is comparable to every other element of X and satisfies for all is the largest element of the set.

(b) An element which is comparable to every other element of X and satisfies for all is the smallest element of the set.

In some cases, we only care that an element be "bigger than" or "smaller than" elements to which it is comparable.

Definition. Let X be a partially ordered set. If an element x satisfies for all y to which it is comparable, then x is a maximal element. Likewise, if an element x satisfies for all y to which it is comparable, then x is a minimal element.

Note that a largest or smallest element, if it exists, is unique. On the other hand, there may be many maximal or minimal elements.

Example. Define a relation on by

Check each axiom for a partial order. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

for all , so for all . Therefore, is reflexive.

Suppose and . Is is true that ?

, since . Likewise, , since . But , so is not antisymmetric.

Finally, suppose and . This means that and . Hence, . Therefore, , so is transitive.

Example. Define a relation on by

Check each axiom for a partial order. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

Since for all , it follows that for all . Therefore, is reflexive.

, since . Likewise, , since . However, . Therefore, is not antisymmetric.

Finally, suppose and . Then and . Hence, . Therefore, . Hence, is transitive.

Definition. A relation on a set X is a total order if:

(a) (Trichotomy) For all , exactly one of the following holds: , , or .

(b) (Transitivity) For all , if and , then .

The usual less than relation is a total order on , on , and on . Likewise, you can use the total order relation on to define a lexicographic order on which is a total order. Specifically, define a total order on as follows: means that

(a) , or

(b) and .

You can check that the axioms for a total order hold.

Example. Consider the relation defined by the graph below:

Thus, means that , and there is an upward path of segments from x to y.

Is this relation a total order? You can check cases, using the picture, that the relation is transitive. (This amounts to saying that if there's an upward path from x to y and one from y to z, then there's such a path from x to z. In fact, if you define a relation using a graph in this way, the relation will be transitive.)

However, this graph does not define a total order. Trichotomy fails for d and e, since , , and are all false.

Definition. Let S be a partially ordered set, and let T be a subset of S.

(a) is an upper bound for T if for all .

(b) is a lower bound for T if for all .

Thus, an upper bound for a subset is an element which is greater than or equal to everything in the subset; a lower bound for a subset is an element which is less than or equal to everything in the subset. Note that unlike the largest element or smallest element of a subset, upper and lower bounds don't need to belong to the subset.

For instance, consider the subset of . 2 is an upper bound for T, since for all . 1 is also an upper bound for T. Note that 2 is not an element of T while 1 is an element of T. In fact, any real number greater than or equal to 1 is an upper bound for T.

Likewise, any real number less than or equal to 0 is a lower bound for T.

T has a largest element, namely 1. It does not have a smallest element; the obvious candidate 0 is not in T.

This example shows that a subset may have many --- even infinitely many --- upper or lower bounds. Among all the upper bounds for a set, there may be one which is smallest.

Definition. Let S be a partially ordered set, and let T be a subset of S. An element is a least upper bound for T if:

(a) is an upper bound for T.

(b) If s is an upper bound for T, then .

The idea is that is an upper bound by (a); it's the least upper bound, since (b) says is smaller than any other upper bound.

Definition. Let S be a partially ordered set, and let T be a subset of S. An element is a greatest lower bound for T if:

(a) is an lower bound for T.

(b) If s is an lower bound for T, then .

The concepts of least upper bound and greatest lower bound come up often in analysis. I'll give a simple example.

Example. Determine the least upper bound and greatest lower bound for the following sets (if they exist):

(a) The subset of .

(b) The subset of . (Thus, T is the positive real axis, not including 0.)

(a) Any real number greater than or equal to 1 is an upper bound for T. Among the upper bounds for S, it's clear that 1 is the smallest, so 1 is the least upper bound for S.

Likewise, any real number less than or equal to 0 is a lower bound for S. But among the lower bounds for S, it's clear that 0 is the largest, so 0 is the greatest lower bound for S.

Notice that , but . The least upper bound and greatest lower bound may be contained, or not contained, in the set.

(b) T has no least upper bound in ; in fact, T has no upper bound in .

0 is the greatest lower bound for T in .

Contact information