4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your proof is okay, as I see. $\endgroup$ – Hanul Jeon Oct 6 '13 at 12:12
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for your answer! $\endgroup$ – topsi Oct 7 '13 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.