If $A$ is well ordered and $B$ is well ordered then $A\times B$ with the lexicographic order is well ordered

Question

I am trying to prove that: Given that $A,B$ are well ordered sets, also $A \times B$ is a well ordered set.

(A set $A$ is well ordered if a linear order is defined on it, and every non empty subset $B$ of $A$ has a minimal element.)

I was thinking about the following proof: To show that $A \times B$ is well ordered: Take two elements: $(a_1,b_1),(a_2,b_2) \in A \times B$. Then there are three cases: 1. $a_1 < a_2$. in this case $(a_1,b_1) < (a_2,b_2)$ 2. $a_1 > a_2$. in this case $(a_1,b_1) > (a_2,b_2)$ 3. $a_1 = a_2$. in this case: if $ b_1 > b_2$ then $(a_1,b_1) > (a_2,b_2)$. if $b_1 < b_2$ then $(a_1,b_1) < (a_2,b_2)$. and if $b_1 = b_2$ then $(a_1,b_1) = (a_2,b_2)$.

To show that $U$ has a minimal element: Take $U \subseteq A \times B$, a non empty set. $U = \{ (a_i,b_j)| a_i \in A, b_j \in B \}$. Where $i,j \in I$ and $I$ is a linearly ordered set of indexes. Then the set $\{a_i | (a_i,b_j) \in A \times B\}$ has a minimal element: $a_{i_0}$. Also the set $\{ b_j | (a_{i_0},b_j) \}$ has a minimal element $b_{j_0}$. So the element $(a_{i_0},b_{i_0})$ is a minimal element of $U$.

My question is: what do you think about this proof. is it ok?

Thank you! shir

Answer 1

Your proof is okay, but I would slightly modify a couple of things:

1. The definition of $a_{i_0}$ is slightly cumbersome, and the reason is that you are trying to use the set index set for both the $a_i$ and the $b_j$. It's better to just say that $U$ is a non-empty set of pairs.

   Then you can simply define $a_i=\min\{a\in A\mid\exists b(a,b)\in U\}$.

2. Similarly, the use of $i_0$ as the index for both $a$ and $b$ is confusing and unclear. It is better to define $b_j$ as $\min\{b\in B\mid (a_i,b)\in U\}$.

   Note that in both the definition of $a_i$ and $b_j$ you omitted the condition that the pairs are taken from $U$.