# 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. (a) The relation is a partial order on .

For all , : Reflexivity holds.

For all , if and , then : Antisymmetry holds.

For all , if and , then : Transitivity holds.

Thus, is a partial order.

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

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. Set inclusion if a partial order on .

Set inclusion is the relation of being a subset; thus, subsets A and B of X are related under set inclusion if . I'll check the axioms for a partial order.

If , then .

Suppose . If and , then by definition of set equality, .

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

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

Example. Let . Define a partial order on X as follows: means that

(a) , or

(b) and .

Note that implies .

This order relation is called the lexicographic order or dictionary order on X. The name comes from the way words are listed in a dictionary. "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 . because the x-coordinates are equal and .

Here's the proof that this is a partial order.

First, , since and . is reflexive.

Next, suppose and . means that either or . 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 .

Example. It's often convenient to 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 . An element with these properties is said to be the largest element of the set.

The smallest element of a partially ordered set is an element which is comparable to every other element and less than or equal to every other element. This set does not have a smallest element.

Example. Define a relation on by

Which of the axioms for a partial order does satisfy?

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

Which of the axioms for a partial order does satisfy?

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. Let be 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 .

Example. The usual less than relation is a total order on , on , and on .

Example. Let . Define a total order on X as follows: means that

(a) , or

(b) and .

This is the dictionary order on with replaced by .

Example. Consider the relation defined by the graph below:

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

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.

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

The previous 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. 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.

Likewise, 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 .

Example. (a) Consider the subset of . Any real number greater than or equal to 1 is an upper bound for T. Among the upper bounds for T, 1 is the smallest, so 1 is the least upper bound for T.

Likewise, any real number less than or equal to 0 is a lower bound for T. But among the lower bounds for T, 0 is the largest, so 0 is the greatest lower bound for T.

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

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

T has no least upper bound in ; in fact, T has no upper bound in .

0 is the greatest lower bound for T in .