If $A$ is a set, then a relation $\le$ on $A$ is a partial ordering if
1) for all $x\in A$, $x\le x$ ($\le$ is reflexive),
2) for all $x,y,z\in A$, if $x\le y$ and $y\le z$, then $x\le z$ ($\le$ is transitive),
3) for all $x,y\in A$, if $x\le y$ and $y\le x$, then $x=y$, ($\le$ is anti-symmetric).
WARNING: we are appropriating the familiar symbol "$\le$'' to mean something new. The usual orderings of $\N$, $\Z$, $\Q$, and $\R$ denoted by $\le$ are partial orderings, so this use is "backwards compatible,'' but there are many other partial orderings, as we will see.
Example 5.3.1 If $A=\N$ and $x\le y$ means $x|y$, then $\le$ is a partial ordering, so $\N$ has more than one "natural'' partial ordering defined on it. (Unless we say otherwise, we will continue to use $\le$ to denote the usual order for $\N$.) $\square$
Example 5.3.2 Suppose $S$ is a set and $A$ is the set of all functions $f\colon S\to \R$. Let $f\le g$ mean $f(x)\le g(x)$ for all $x\in S$; $\le$ is a partial ordering of $A$. Notice that we have used the symbol $\le$ in two different ways! $\square$
Example 5.3.3 Suppose $S$ is a set and $A={\cal P}(S)$ is the power set of $S$. Let $X\le Y$ mean $X\subseteq Y$; $\le$ is a partial ordering. $\square$
Definition 5.3.4 If $\le$ is a partial ordering on $A$, we say it is a total ordering if for all $x,y\in A$, either $x\le y$ or $y\le x$. $\square$
Example 5.3.5 The familiar partial orderings of $\N$, $\Z$, $\Q$, and $\R$ are total orderings. Those of examples 5.3.1, 5.3.2 and 5.3.3 are not. $\square$
Definition 5.3.6 If $\le$ is a partial ordering on $A$, and $S\subseteq A$, we say $x\in S$ is a least element of $S$ if $x\le y$ for all $y\in S$. We say $x\in S$ is a greatest element of $S$ if $y\le x$ for all $y\in S$. $\square$
Theorem 5.3.7 If $\le$ is a total ordering on $A$, then every non-empty finite subset $S$ of $A$ has a least element and a greatest element.
Proof. We show there is a least element and leave the rest to an exercise. By induction. Let $P(n)$ be the statement "every subset of $A$ having $n$ elements has a least element.'' Clearly $P(1)$ is true. Suppose $P(n)$ is true. If $S$ has $n+1$ elements, let $S=S'\cup \{y\}$, for some $y\in S$ and $S'$ with $n$ elements (namely, $S'=S\backslash\{y\}$, or $S$ with $y$ removed). By induction, $S'$ has a least element, call it $x$. Since $\le$ is a total ordering, either $x\le y$ or $y\le x$. In the first case, $x$ is a least element of $S$. On the other hand, if $y\le x$ we claim that $y$ is a least element of $S$: If $z\in S$, then either $z=y$, or $z\in S'$ and $y\le x\le z$. In either case, $y\le z$, as desired.$\qed$
Definition 5.3.8 We say $\le$ is a well ordering of $A$ if every non-empty subset $S$ of $A$ has a least element. $\square$
Theorem 5.3.9 If $\le$ is a well ordering of $A$ then it is a total ordering.
Proof. Suppose $x,y\in A$. Let $S=\{x,y\}\ne \emptyset$. By hypothesis, $S$ has a smallest element. If it is $x$, then $x\le y$, and if it is $y$, then $y\le x$. $\qed$
Example 5.3.10 Since the partial orderings of examples 5.3.1, 5.3.2 and 5.3.3 are not total orderings, they are not well orderings. Since there is no smallest integer, rational number or real number, $\Z$, $\Q$ and $\R$ are not well ordered.$\square$
The following important fact is called the well ordering principle.
Proof. Let $S$ be a non-empty subset of $\N$. Choose $n\in S$, and let $S_n=\{s\in S: s\le n\}$. $S_n$ is not empty, since it contains $n$, and has a finite number of elements, so by theorem 5.3.7 it has a least element $x$. Then $x$ is, in fact, a least element of $S$, since if $y\in S-S_n$, then $x\le n\le y$, so $x\le y$.$\qed$
If $\le$ is a partial ordering of $A$, then $x< y$ means $x\le y$ and $x\ne y$, $x\ge y$ means $y\le x$ and $x>y$ means $y< x$. These have some familiar properties, explored in the exercises.
Exercises 5.3
In the following exercises, assume $\le$ is a partial ordering of a set $A$.
Ex 5.3.1 Show that if $a< b$ then it is not true that $b\le a$.
Ex 5.3.2 Show that at most one of the three properties $a< b$, $a=b$, $b< a$ is true.
Ex 5.3.3 If $a< b$ and $b\le c$, show $a< c$.
Ex 5.3.4 If $a\le b$ and $b< c$, show $a< c$.
Ex 5.3.5 Suppose $S\subseteq A$ has a least element. Show that it is unique.
Ex 5.3.6 Show that $A$ is totally ordered if and only if every non-empty finite subset of $A$ has a least element.
Ex 5.3.7 If $A$ is totally ordered but not well ordered, prove there is a sequence of elements such that $a_1>a_2>a_3>\cdots$. (Hint: start with a non-empty subset that does not contain a least element.)
Ex 5.3.8 Suppose $A$ has the property that every non-empty countable subset has a least element. Show that $A$ is well ordered. (Hint: show first that $A$ is totally ordered, then use problem 7.)
Ex 5.3.9 Finish the proof of theorem 5.3.7.