Show that the lexicographic ordering $≤_l$ on $A\times B$ for $A$ well ordered by $≤$ and $B$ well-ordered by $≤'$ is well-ordered. Q: Show that the lexicographic ordering $≤_l$ on $A\times B$ for $A$ well ordered by $≤$ and $B$ well-ordered by $≤'$ is well-ordered. A: I have previously shown that this lexicographic ordering is totally ordered, and I am aware that any finite totally ordered set is well-ordered, but $A$ and $B$ aren't necessarily finite, so I'm not sure how to show that any subset of $A\times B$ has a least element.  Any help is appreciated.
A: Let $\pi_A: A \times B \to A$ and $\pi_B: A \times B \to B$ be the projection maps.
Suppose $C \subseteq A \times B$ is non-empty, then $\pi_A[C]$ is a non-empty subset of $A$ and so has a $\le$-minimal element $a_0 \in \pi_A[C]$.
Then the set $(\{a_0 \} \times B) \cap C$ (all points of $C$ with first coordinate equal to $a_0$) is also non-empty and $\pi_B[(\{a_0 \} \times B) \cap C]$ has a $\le'$-minimum $b_0 \in B$.
Claim: $(a_0, b_0) = \min(C)$. To see this, let $(a,b)\in C$ be arbitrary. Then $a \in \pi_A[C]$ and so $a_0 \le a$ by minimility of $a_0$ in that set. If $a_0 < a$ we are done, as then $(a_0, b_0) \le_l (a,b)$ by the definition of the lexicographic order. So it remains to consider the case $a_0=a$, but then $(a,b) \in (\{a_0 \} \times B) \cap C$ and so $b \in \pi_B[(\{a_0 \} \times B) \cap C]$ and $b_0 \le' b$ by minimality of $b_0$ again. Now, from $a_0 \le a$ and $b_0 \le' b$ we conclude $(a_0, b_0) \le_l (a,b)$ again by the definition of $\le_l$.
The claim has been shown.
