This question already has an answer here:

Can anyone please help me in this?

Prove that every well ordered set is a totally ordered set.

To start this proof will this be sufficient:

Let $x_1, x_2 \in X.$

Let $A=\{ x_1, x_2 \}$.

If $x_1$ is the least element, then $x_1\le x2$. If $x_2$ is the least element, then $x_1\ge x_2$.

How do I end the proof?


marked as duplicate by Michael Greinecker Aug 12 '13 at 20:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ You will need to give us your definitions of "well ordered set" and "totally ordered set". There are several definitions of each, some of which are equivalent to each other but all of which give different proof obligations. $\endgroup$ – dfeuer Aug 9 '13 at 4:28

To end the proof:

Thus either $x_1\le x_2$ or $x_2 \le x_1$.

As this holds for all $x_1,x_2\in X$, and as we have (perhaps?) assumed that $\le$ is an ordering, $(X,\le)$ is a totally ordered set.


Here is one possible definition and consequences:

Let $S$ be a totally-ordered set. $S$ is well-ordered if for every nonempty subset of $S$, there is a least element.

From the definition, $S$ is well-ordered $\Rightarrow$ there is a total-order on $S$ is trivial.

However, the converse is not necessarily true. For example, consider the reals, for which there is the usual total-order. Take any subset $A=\left(a,b\right)$. Clearly, this subset has no least element ($a \notin A$ and for every $p\in A$ there exists $q\in A$ with $q<p$).

  • 1
    $\begingroup$ This doesn't work. $S$ needn't be finite. The approach in the original incomplete question is actually a sensible one. $\endgroup$ – dfeuer Aug 9 '13 at 7:02
  • $\begingroup$ Thanks. I'll remove the edit. $\endgroup$ – parsiad Aug 9 '13 at 8:17

It sounds like your definition of a well-order is as follows (and what we will use in this answer):

A set is well-ordered if and only if every nonempty subset $S$ has a least and minimal element: exactly one element $x$ such that $x \le y$ and $y \not < x$ for all $y \in S$.

We take $x < y$ to mean $x \le y$ and $x \ne y$.

Your approach is good. You have prove linearity. Now we need to prove that $\le $ is a partial order.

To prove that $x \le x$, set $S = \{ x \}$. Then we only have one choice for a least element, so $x \le x$.

Now suppose $x \le y$ and $y \le x$. Then set $S = \{ x,y \}$ and assume $x \ne y$. Either $x$ or $y$ is a minimal element, so suppose $x$ is a minimal element (the same argument will work for $y$). Then $y \not < x$ so $x = y$.

Now finally, let $x \le y$ and $y \le z$. Set $S = \{ x,y,z \}$. If $y$ is a least element then $x = y$, in which case $x \le z$ as desired. If $x$ is a least element, then $x \le z$ trivially. And if $z$ is a least element, then $z = y$ and $x \le z$, as desired.

  • $\begingroup$ Something about that antisymmetry bit smells a bit fishy. What's the definition of $<$? $\endgroup$ – dfeuer Aug 9 '13 at 12:44
  • $\begingroup$ @dfeuer I have clarified this in my answer. $\endgroup$ – A.S Aug 9 '13 at 13:17

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