6
$\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$
1
  • $\begingroup$ Your proof is okay, as I see. $\endgroup$
    – Hanul Jeon
    Oct 6, 2013 at 12:12

1 Answer 1

5
$\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$
1
  • $\begingroup$ Thank you for your answer! $\endgroup$
    – topsi
    Oct 7, 2013 at 8:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .