Order Relations

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

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

(a) (Reflexive) For all $x \in X$ , $x
   \sim x$ .

(b) (Antisymmetric) For all $x, y \in X$ , if $x
   \sim y$ and $y \sim x$ , then $x = y$ .

(c) (Transitive) For all $x, y, z \in X$ , if $x \sim y$ and $y \sim z$ , then $x \sim z$ .


Example. (a) The relation $\le$ is a partial order on $\real$ .

For all $x \in \real$ , $x \le x$ : Reflexivity holds.

For all $x, y \in \real$ , if $x \le y$ and $y
   \le x$ , then $x = y$ : Antisymmetry holds.

For all $x, y, z \in \real$ , if $x \le y$ and $y
   \le z$ , then $x \le z$ : Transitivity holds.

Thus, $\le$ is a partial order.

(b) The relation $<$ is not a partial order on $\real$ .

For no x is it true that $x < x$ , so reflexivity fails.

Antisymmetry would say: If $x < y$ and $y
   < x$ , then $x = y$ . However, for no $x, y \in \real$ is it true that $x < y$ and $y < x$ . Therefore, the first part of the conditional is false, and the conditional is true. Thus, antisymmetry is vacuously true.

If $x < y$ and $y < z$ , then $x < z$ . Therefore, transitivity holds.

Hence, $<$ is not a partial order.


Example. Let X be a set and let $\powerset(X)$ be the power set of X --- i.e. the set of all subsets of X. Set inclusion if a partial order on $\powerset(X)$ .

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

If $A \subset X$ , then $A \subset A$ .

Suppose $A, B \subset X$ . If $A \subset
   B$ and $B \subset A$ , then by definition of set equality, $A = B$ .

Finally, suppose $A, B, C \subset X$ . If $A \subset B$ and $B \subset C$ , then $A \subset C$ . (You can write out the easy proof using elements.)

Here's a particular example. Let $X =
   \{a, b, c\}$ . This is a picture of the set inclusion relation on $\powerset(X)$ :

$$\hbox{\epsfysize=2in \epsffile{poset1.eps}}\quad\halmos$$


Example. Let $X
   = \integer^2 = \integer \times \integer$ . Define a partial order $\sim$ on X as follows: $(x_1,y_1) \sim (x_2,y_2)$ means that

(a) $x_1 < x_2$ , or

(b) $x_1 = x_2$ and $y_1 \le y_2$ .

Note that $(x_1,y_1) \sim (x_2,y_2)$ implies $x_1 \le x_2$ .

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

$$\hbox{\epsfysize=2in \epsffile{poset2.eps}}$$

In the picture above, $(-2,2) \sim
   (-1,-2)$ , because $-2 < -1$ . $(2,1) \sim (2,4)$ because the x-coordinates are equal and $1 < 4$ .

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

First, $(x,y) \sim (x,y)$ , since $x =
   x$ and $y \le y$ . $\sim$ is reflexive.

Next, suppose $(x_1,y_1) \sim (x_2,y_2)$ and $(x_2,y_2) \sim (x_1,y_1)$ . $(x_1,y_1) \sim (x_2,y_2)$ means that either $x_1 < x_2$ or $x_1 = x_2$ . $x_1 < x_2$ is impossible, since this would contradict $(x_2,y_2) \sim (x_1,y_1)$ . Therefore, $x_1 = x_2$ . Then $(x_1,y_1) \sim (x_2,y_2)$ implies $y_1
   \le y_2$ and $(x_2,y_2) \sim (x_1,y_1)$ implies $y_2
   \le y_1$ . Hence, $y_1 = y_2$ . Therefore, $(x_1,y_1) =
   (x_2,y_2)$ . $\sim$ is antisymmetric.

Finally, suppose $(x_1,y_1) \sim
   (x_2,y_2)$ and $(x_2,y_2) \sim (x_3,y_3)$ . To keep things organized, I'll consider the four cases.

(a) If $x_1 < x_2$ and $x_2 < x_3$ , then $x_1 <
   x_3$ , so $(x_1,y_1) \sim (x_3,y_3)$ .

(b) If $x_1 < x_2$ and $x_2 = x_3$ , then $x_1 <
   x_3$ , so $(x_1,y_1) \sim (x_3,y_3)$ .

(c) If $x_1 = x_2$ and $x_2 < x_3$ , then $x_1 < x_3$ , so $(x_1,y_1) \sim (x_3,y_3)$ .

(d) If $x_1 = x_2$ and $x_2 = x_3$ , then $y_1 \le y_2$ and $y_2 \le y_3$ . This implies $x_1 =
   x_3$ and $y_1 \le y_3$ , so $(x_1,y_1) \sim (x_3,y_3)$ .

Hence, $\sim$ is transitive, and this completes the proof that $\sim$ 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 $\sim$ be a relation on a set X. x and y in X are comparable if either $x \sim y$ or $y \sim x$ .


Example. It's often convenient to describe an order relation by drawing a graph like the one below.

$$\hbox{\epsfysize=2in \epsffile{poset3.eps}}$$

This picture shows a relation $\sim$ on the set

$$S = \{a, b, c, d, e, f, g, h, i\}.$$

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 $x \sim x$ .

For example, $f \sim c$ , since there's an upward segment connecting f to c. And $f \sim a$ , since there's an upward path of segments $f \to c \to b \to a$ 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, $g \sim h$ and $g \sim i$ , but h and i are not comparable.

Notice that a is comparable to every element of the set, and that $x \sim a$ for all $x \in S$ . 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 $\sim$ on $\real$ by

$$x \sim y \quad\hbox{means}\quad x^3 - 4x \le y^3 - 4y.$$

Which of the axioms for a partial order does $\sim$ satisfy?

$x^3 - 4x \le x^3 - 4x$ for all $x \in
   \real$ , so $x \sim x$ for all $x \in \real$ . Therefore, $\sim$ is reflexive.

Suppose $x \sim y$ and $y \sim x$ . Is is true that $x = y$ ?

$2 \sim -2$ , since $2^3 - 4\cdot 2
   \le (-2)^3 - 4\cdot (-2)$ . Likewise, $-2 \sim 2$ , since $(-2)^3 - 4\cdot (-2) \le 2^3 - 4\cdot 2$ . But $2 \ne -2$ , so $\sim$ is not antisymmetric.

Finally, suppose $x \sim y$ and $y \sim
   z$ . This means that $x^3 - 4x \le y^3 - 4y$ and $y^3 - 4y \le z^3 -
   4z$ . Hence, $x^3 - 4x \le z^3 - 4z$ . Therefore, $x \sim z$ , so $\sim$ is transitive.


Example. Define a relation $\sim$ on $\real^2$ by

$$(a,b) \sim (c,d) \quad\hbox{means}\quad |ab| \ge |cd|.$$

Which of the axioms for a partial order does $\sim$ satisfy?

Since $|ab| \ge |ab|$ for all $(a,b)
   \in \real^2$ , it follows that $(a,b) \sim (a,b)$ for all $(a,b) \in
   \real^2$ . Therefore, $\sim$ is reflexive.

$(1,2) \sim (-1,2)$ , since $|1\cdot 2| \ge
   |(-1)\cdot 2|$ . Likewise, $(-1,2) \sim (1,2)$ , since $|(-1)\cdot 2|
   \ge |1\cdot 2|$ . However, $(1,2) \ne (-1,2)$ . Therefore, $\sim$ is not antisymmetric.

Finally, suppose $(a,b) \sim (c,d)$ and $(c,d) \sim (e,f)$ . Then $|ab| \ge |cd|$ and $|cd| \ge |ef|$ . Hence, $|ab| \ge |ef|$ . Therefore, $(a,b) \sim (e,f)$ . Hence, $\sim$ is transitive.


Definition. Let $\sim$ be a relation on a set X. $\sim$ is a total order if:

(a) (Trichotomy) For all $x, y \in X$ , exactly one of the following holds: $x \sim y$ , $y \sim x$ , or $x = y$ .

(b) (Transitivity) For all $x, y, z \in
   X$ , if $x \sim y$ and $y \sim z$ , then $x \sim z$ .


Example. The usual less than relation $<$ is a total order on $\integer$ , on $\rational$ , and on $\real$ .


Example. Let $X
   = \integer^2 = \integer \times \integer$ . Define a total order $\sim$ on X as follows: $(x_1,y_1) \sim (x_2,y_2)$ means that

(a) $x_1 < x_2$ , or

(b) $x_1 = x_2$ and $y_1 < y_2$ .

This is the dictionary order on $\integer^2$ with $\le$ replaced by $<$ .


Example. Consider the relation defined by the graph below:

$$\hbox{\epsfysize=1.75in \epsffile{poset4.eps}}$$

Thus, $x < y$ means that $x \ne y$ , 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 $d < e$ , $e < d$ , and $d = e$ are all false.


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

(a) $s \in S$ is an upper bound for T if $s \ge t$ for all $t \in T$ .

(b) $s \in S$ is a lower bound for T if $s \le t$ for all $t \in T$ .

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 $T = (0,1]$ of $\real$ . 2 is an upper bound for T, since $2 \ge x$ for all $x \in T$ . 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. $s_0
   \in S$ is a least upper bound for T if:

(a) $s_0$ is an upper bound for T.

(b) If s is an upper bound for T, then $s_0 \le s$ .

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

Likewise, $s_0 \in S$ is a greatest lower bound for T if:

(a) $s_0$ is an lower bound for T.

(b) If s is an lower bound for T, then $s_0 \ge s$ .


Example. (a) Consider the subset $T = (0,1]$ of $\real$ . 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 $1 \in T$ , but $0
   \notin T$ . The least upper bound and greatest lower bound may be contained, or not contained, in the set.

(b) Consider the subset $T =
   (0,+\infty)$ of $\real$ . (Thus, T is the positive real axis, not including 0.)

T has no least upper bound in $\real$ ; in fact, T has no upper bound in $\real$ .

0 is the greatest lower bound for T in $\real$ .


Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga