Suppose $\le$ is a partial ordering of $A$ and $S$ is a subset of $A$. If we restrict $\le$ to $S$, we have an ordering of $S$.
Lemma 5.4.1 Suppose $\le$ is a partial ordering of $A$ and $S$ is a subset of $A$. Then
a) $\le$ is a partial ordering of $S$;
b) if $A$ is totally ordered by $\le$, so is $S$;
c) if $A$ is well ordered by $\le$, so is $S$.
Proof. If $x\in S$, then since $x\in A$, $x\le x$, so $\le$ is reflexive on $S$. Similarly, transitivity, anti-symmetry, total ordering or well ordering on $S$ follow from the corresponding property on $A$. $\qed$
Example 5.4.2 Any collection of subsets of $X$ forms a subset of ${\cal P}(X)$, so the subsets are partially ordered by inclusion. $\square$
Example 5.4.3 Any subset of the rational numbers is countable and totally ordered by the usual ordering of $\Q$. $\square$
Suppose $\le_1$ is a partial ordering of $A$ and $\le_2$ is a partial ordering of $B$. On $A\times B$, let $(a,b)\le (x,y)$ mean $a< _1 x$, or $a= x$ and $b\le_2 y$. This is called the lexicographic ordering; the name is derived from its similarity to ordering words alphabetically. Note that if $(a,b)\le (x,y)$ then $a\le_1 x$.
Theorem 5.4.4 Suppose $\le_1$ is a partial ordering of $A$, $\le_2$ is a partial ordering of $B$ and $\le$ is the lexicographic ordering.
a) $\le$ is a partial ordering of $A\times B$.
b) If $\le_1$ and $\le_2$ are total orderings, so is $\le$.
c) If $\le_1$ and $\le_2$ are well orderings, so is $\le$.
Proof. (a) Since $a\le_1 a$ and $b\le_2 b$, $(a,b)\le (a,b)$, i.e., $\le $ is reflexive. Transitivity is left as an exercise. To show anti-symmetry, suppose $(a,b)\le (x,y)$ and $(x,y)\le (a,b)$. Looking at the first coordinates, we have $a\le_1 x$ and $x\le_1 a$. Since $\le_1$ is anti-symmetric, $a=x$; in particular, it is not true that $a< _1 x$ or $x< _1 a$. So looking at second coordinates, $b\le_2 y$ and $y\le_2 b$, so $b=y$, as desired.
We leave part (b) to the exercises. As to part (c), suppose $S$ is a non-empty subset of $A\times B$. Let $T=\{a:\exists b\in B ((a,b)\in S)\}$. Since $S$ is non-empty, so is $T$. Let $a_0$ be the least element of $T$. Let $U=\{b:(a_0,b)\in S\}$. Since $a_0\in T$, $U$ is non-empty. Let $b_0$ be the least element of $U$. We claim that $(a_0,b_0)$ is the least element of $S$. If $(x,y)\in S$, then by the definition of $T$, $x\in T$, so $a_0\le_1 x$. If $a_0< _1 x$, then $(a_0,b_0) \le (x,y)$, as required. Otherwise, $a_0=x$ and $(x,y)=(a_0,y)$. So $y\in U$, and by definition, $b_0\le y$. This means $(a_0,b_0)\le (x,y)$, as required. $\qed$
Corollary 5.4.5 The lexicographic ordering on $\N\times \N$ is a well ordering.
Exercises 5.4
Ex 5.4.1 If $A=\{a,b,c\}$ and $B=\{a,b,c,d\}$ are ordered alphabetically, write down the lexicographic ordering of $A\times B$ (i.e., order the elements from smallest to largest).
Ex 5.4.2 If $A$ and $B$ are partially ordered and $a_0$ and $b_0$ are the least elements of $A$ and $B$, show that $(a_0,b_0)$ is the least element of $A\times B$ in the lexicographic ordering.
Ex 5.4.3 Suppose $A$ is partially ordered, and every proper subset of $A$ is totally ordered. Show that if $|A|\ge 3$, then $A$ is totally ordered. What about $|A|=2$?
Ex 5.4.4 Suppose $A=B\cup C$ is totally ordered. Show that $A$ is well ordered if and only if $B$ and $C$ are well ordered.
Ex 5.4.5 Suppose $A$ and $B$ are non-empty partially ordered sets and $A\times B$ (ordered lexicographically) is totally ordered. Show that $A$ and $B$ are totally ordered.
Ex 5.4.6 Suppose $A$ and $B$ are non-empty partially ordered sets and $A\times B$ (ordered lexicographically) is well ordered. Show that $A$ and $B$ are well ordered.
Ex 5.4.7 Prove transitivity in 5.4.4(a).
Ex 5.4.8 Prove 5.4.4(b).