6
$\begingroup$

It's quite easy to show that a finite set is well ordered iff it is totally ordered. Is the converse also true? That is: is it true that a set is infinite iff it admits a total order which is not a well order? (For the sake of brevity, I shall write t.o. and w.o. for total order and well order, respectively)

The if part follows from the previous observation (t.o.+finiteness implies w.o.), so the question becomes

Is it true that a set is infinite only if it admits a total order which is not a well order?

I know that every set admits a w.o. (and thus a t.o.); still, answering the question requires to prove (or to disprove) that t.o.≠w.o., and this is out of my reach.

The question supposes ZFC but every other set theory is accepted.

$\endgroup$
5
$\begingroup$

It is easy to prove that $A$ is finite if and only if there is an order $<$ on $A$, such that $(A,<)$ and the reverse order $(A,>)$ are both well-orders.

Now, note that the reverse order of a total order is again a total order, and so if $A$ is infinite, there is a well-ordering on $A$, $<$, such that $(A,>)$ is not a well-order itself. (Of course, one can show that this is true for any well-ordering of an infinite set.)


Just a remark on the Axiom of Choice, the above holds for $\sf ZF$ as well, although it is consistent with $\sf ZF$ that there are sets which do not admit any total orders, let alone well-orders.

But a curious thing is that if we change "there exists an order ..." to "every well-order $<$ satisfies ...", then any set which cannot be well-ordered satisfies the definition vacuously. And therefore the Axiom of Choice is equivalent to the statement "a set $A$ is finite if and only if for every well-order on $A$, the reverse order is also a well-order".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Please participate here $\endgroup$ – Bill Dubuque Oct 31 '19 at 16:29
6
$\begingroup$

Not my area of expertise but I will suggest an answer.

If a $S$ is infinite, well order it. An initial segment will be the natural numbers with their usual order. Then reorder that initial segment using a bijection to the rational numbers to transfer the not-well-ordered numerical order on the rationals.

If this is wrong someone will point that out. Then I can delete it, or leave it as an instructive false start.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Looks correct to me. $\endgroup$ – rawbacon Oct 28 '19 at 13:07
  • $\begingroup$ How can we be sure that rearranging the order gives as an order? $\endgroup$ – Caffeine Oct 28 '19 at 13:14
  • $\begingroup$ @GabrieleCassese You create a new ordering on the target space effectively ordered by the base space. The ordering may not be the same as the typical ordering on $\Bbb Q$. $\endgroup$ – Cameron Williams Oct 28 '19 at 13:15
  • $\begingroup$ You can even exchange the initial segment $\Bbb N$ to $\Bbb Z$. $\endgroup$ – Berci Oct 28 '19 at 13:21
  • $\begingroup$ @CameronWilliams I'm sorry, but I do not understand: how can we be sure that in this new order $\Bbb Q$ is not well ordered? After all, we know there is a order in which it is (thanks to AC) $\endgroup$ – Caffeine Oct 28 '19 at 13:29

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.