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

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

• Your proof is okay, as I see. Oct 6, 2013 at 12:12

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