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 .

Copyright 2008 by Bruce Ikenaga