Can all sets be totally ordered (not well-ordered) in ZF

axiom-of-choiceset-theory

It seems like an interesting question, and bizarrely, one I haven't been able to find the answer to. Of course, it's extremely well-known that the statement that all sets can be well-ordered is equivalent to AC, but looking through the proofs of this, I haven't been able to find a model that says sets can't be ordered at all, and trying it by my own hand, every approach I take seems to lead the notion that an ordering implies an ordering of the power set, and that I can't show. This site is giving me a possible counterexample involving an inaccessible cardinal, but the author doesn't really flesh it out, and since inaccessible cardinals I understand are independent of AC, if that's the counterexample I'd really like to see it fleshed out.

Best Answer

I wrote a somewhat technical answer to the question several years ago. The answer is no, and you can find a proof in that link.

Let me not entirely flesh out the whole proof, but instead rely on several well-known examples.

  1. Russell sets, or generally, when you cannot choose from a family of finite sets. Suppose that you have a family of sets, each of them is finite, say of size $2$. Let $A$ be the union of all these sets. If $A$ can be linearly ordered, this provides a uniform linear ordering of all your finite sets (and then some), letting you pick the least member of each of these finite sets.

    And indeed, it is consistent that there is a countable set of pairwise disjoint pairs, which does not admit a choice function. Therefore, the union of these pairs cannot be linearly ordered.

  2. Amorphous sets. These are sets which cannot be split into two infinite sets. Clearly their existence contradicts even the most basic principles of choice. If $A$ is an amorphous set, it cannot be linearly ordered. Suppose $<$ was in fact a linear ordering of an amorphous set. Then every point defines a cut, one side of which is finite, and the other is infinite. If all but finitely many points have finitely many predecessors, then this linear ordering is isomorphic to an ordinal of the form $\omega+n$, where $n$ is finite. But then it is countable, so no. If all but finitely many points have infinitely many predecessors, consider the reverse linear ordering and derive a contradiction yet again.

  3. $\mathcal P(\omega)/\rm fin$, the equivalence classes of sets of natural numbers modulo finite changes. This one is trickier, and harder to prove. Andrés Caicedo gave a very good proof on MathOverflow to this fact. In short, if this set can be linearly ordered, there is a set without the Baire Property and a set which is not Lebesgue measurable. Since it is consistent that every set has the Baire Property, or if you're willing to accept inaccessible cardinals into your life, that every set is Lebesgue measurable, it follows that $\mathcal P(\omega)/\rm fin$ is consistently without a linear ordering.

There are many other possible examples, but these are the three "obvious" examples.

Related Question