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

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.

Example 5.4.3 Any subset of the rational numbers is countable and totally ordered by the usual ordering of $\Q$.

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.

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