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.


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.

  • $\begingroup$ I assume that by "sets that cannot be separated into two infinite sets," you mean infinite sets? Since if AC implies {} can be separated into two infinite sets, that blows the Banach-Tarski paradox out of the water. Regardless, I don't see how it follows from any model such a set exists? I'm assuming it has something to do with Levy's strict chain of infinities, but I'm not sure where. $\endgroup$ – user361424 Oct 8 '18 at 0:48
  • $\begingroup$ Yes, of course that I mean infinite sets, thanks. I don't understand the second part of your comment. And I am also unfamiliar with "Levy's strict chain of infinities", or at least I'm not familiar with the term. $\endgroup$ – Asaf Karagila Oct 8 '18 at 7:59
  • $\begingroup$ I don't know if there is a real term for it - Levy collected a number of different notions of infinity (e.g., cardinality, Tarski, Dedekind), all equivalent under AC, and showed that for each pair there's a model in which one is strictly contained in the other. "The Independence of Various Definitions of Finiteness," 1958. $\endgroup$ – user361424 Oct 10 '18 at 8:45
  • $\begingroup$ Ah. Yeah, those are notion of finiteness. John Truss later studied them in the context of ZF (Levy only did so in the context of ZF+Atoms). Amorphous sets are on that list, I don't remember if it's $\Delta_2$ or $\Delta_1$, but it's there somewhere at the bottom. It's a pretty extreme form of finiteness. $\endgroup$ – Asaf Karagila Oct 10 '18 at 8:47

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.