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 .

Copyright 2018 by Bruce Ikenaga