0
$\begingroup$

If a nonempty set $A$ is fully ordered but not well ordered, prove there is a sequence of elements such that $a_1 \gt a_2 \gt a_3 \gt ...$

I know the intuition behind this that since $A$ is not well ordered, there does not exist a least element in $A$. And since $A$ is fully ordered, any two elements in $A$ are comparable. But is this enough to prove that there is such a sequence?

How would I write this out mathematically?


Added work:

Consider a finite set $\{a_i\}$ that is fully ordered. Than, any two $a_1,a_2 \in \{a_i\}$ are comparable. $\implies a_1 \le a_2$ or $a_2 \le a_1$.

$\implies$(?)every subset of $\{a_i\}$ will have a least element. Thus it is well ordered. This shows that if A is fully ordered but not well ordered, then there exists an infinite sequence of the elements.

$\endgroup$
  • $\begingroup$ Prove that finite sets must be well-ordered if they are fully-ordered, complete the proof. $\endgroup$ – DHMO Apr 19 '17 at 18:24
  • $\begingroup$ @DHMO I have tried to complete the proof but is the implication (where the question mark is) correct? I don't know if I can deduce that statement from the two elements being comparable. $\endgroup$ – Suhy Suh Apr 19 '17 at 18:38
2
$\begingroup$

$A$ not being well-ordered does not imply $A$ has no least element. For example $[0,1]$ is not well-ordered but does have a least element.

However, since $A$ is not well-ordered, but is linearly-ordered (fully-ordered, totally-ordered, completely-ordered, terminology-de-jour-ordered), there has to be some $B\subset A$ such that $B$ has no least element (if no such set existed, then $A$ would satisfy all requirements to be well-ordered).

So choose an arbitrary $a_1 \in B$. But $a_1$ is not lowest, so pick an arbitrary $a_2 \in \{ b \in B\mid b < a_1\}$. Repeat inductively.

$\endgroup$

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.