Infinite, totally ordered and well ordered sets

524 Views Asked by At

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.

2

There are 2 best solutions below

1
On BEST ANSWER

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".

7
On

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.