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

• Go component by component. If $C\subset A\times B$ is non-empty, then its projection onto the first component is a non-empty subset of $A$. Therefore, this projection has a minimum $a$. Take the subset of $C$ of elements that have $a$ as their first component. This set is non-empty. Look at the projection onto the second component. This is a non-empty subset of $B$, which therefore, has a minimum $b$. Then $(a,b)\in C$. Show that $(a,b)$ is the minimum of $C$, and therefore $C$ has a minimum. – user647486 Apr 28 at 5:18
• @user647486. Let A = {0,1} = B, C = { (0,1), (1,0), (1,1) }. Notice that (0,0) is not the minimum as you claimed. – William Elliot Apr 28 at 6:28
• @WilliamElliot Run the algorithm that I said. Notice why you ran it wrong if you got $(0,0)$ – user647486 Apr 28 at 6:30

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.