If $M_1$ and $M_2$ are well ordered then $ M = M_1 \times M_2$ is well ordered too.

with the orders $$ (a_1,b_1) \leq (a_2,b_2) \ iff \ b_1 \leq b_2 \ in \ M_2 \ and \ a_1 \leq a_2 \ in \ M_1 \ ,\ b_1=b_2$$

I prove that this is a total order, I prove trichotomy, transitive, but how can I prove that there existe a first element in M.

I tried this by contradiction if $(a_0,b_0) \in M$ is first element but I don't know how continue this idea.

Someone can help me please. Thanks for your time and help.

  • $\begingroup$ To show that $M$ is well-ordered you need to show that any non-empty subset has a least element, not just $M$ itself. $\endgroup$
    – Rob Arthan
    Mar 16, 2017 at 23:37
  • $\begingroup$ Could you clarify the definition of the order in the product, please? Specifically, what is the role of that $b_1 = b_2$ at the end of the line? $\endgroup$
    – amrsa
    Mar 17, 2017 at 12:53

1 Answer 1


The "and" in your definition should be "or", in which case it works. Let $a_0$ be the first element in $M_1$ and $b_0$ be the first element in $M_2$. You are guaranteed they exist because $M_1,M_2$ are well ordered. Then $(a_0,b_0)$ is the first element. You can use your definition to show it is less than ore equal to any element of $M$. For a well order every subset of $M$ must have a least element, but you take any collection, take the elements with the smallest second items, and take the one of those that has the smallest first item.

  • $\begingroup$ yea I have that but I don't know how to relate with the order in $M$ $\endgroup$ Mar 16, 2017 at 23:18
  • $\begingroup$ You use your definition. Given a point $(a,b)$ you always have $(a_0,b_0) \le (a,b)$ because you have both $a_0 \le a, b_0 \le b$ $\endgroup$ Mar 16, 2017 at 23:24
  • $\begingroup$ but what happen if b_0=b ? $\endgroup$ Mar 16, 2017 at 23:37
  • $\begingroup$ But shouldn't a well-ordered set be also totally ordered? (See the comment of Rob Arthan above.) If both $M_1$ and $M_2$ have more than one element, and $a_0 < a_1 \in M_1$ and $b_0 < b_1 \in M_2$, what is the first element of the set $\{ (a_0, b_1), (a_1, b_0) \}$? $\endgroup$
    – amrsa
    Mar 17, 2017 at 12:43
  • $\begingroup$ @amrsa: yes. I took the definition of the order to be a bit poorly written and be lexicographic order starting with the second element. More correctly it would be $(a_1,b_1) \lt (a_2,b_2) if either $b_1 \lt b_2 or ($b_1=b_2$ and $a_1 \lt a_2$) This is a total order and a well order as long as the underlying orders are well orders. $\endgroup$ Mar 17, 2017 at 13:53

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.