Does linear ordering need the Axiom of Choice?

Question

Consider this statement: "every set can be linearly ordered." Can we prove it without AC?

Answer 1

It’s weaker than the full axiom of choice, but it implies the axiom of choice for finite sets. It follows, for instance, from the ultrafilter extension theorem (equivalently, the Boolean prime ideal theorem or the Tikhonov product theorem for Hausdorff spaces). A proof of these implications can be found at Proposition 4.39 of Horst Herrlich, Axiom of Choice, Lecture Notes in Mathematics 1876, Springer, 2006.

Answer 2

The independence of the linear ordering principle was first given by Mostowski (in ZF+Atoms) and later by Halpern and Levy (ZF).

The linear ordering principles were further investigated, and the implications are as follows:

Every set can be well-ordered$\implies$Every infinite set can be linearly ordered in a dense order$\implies$Every set can be linearly ordered.

None of these principles can be reversed. We can add another choice principle into the chain called the Kinna-Wagner principle which is equivalent to the statement that every set can be mapped into the power set of an ordinal. This principle is strictly between the first (axiom of choice) and the second (dense linear order).

Here is an interesting paper which proves and describes some of these results:

David Pincus The Dense Linear Ordering Principle. The Journal of Symbolic Logic , Vol. 62, No. 2 (Jun., 1997), pp. 438-456

It is also worth noting that all of these principles cannot be proved without some form of the axiom of choice. This is known from a very early point, e.g. if you have a set which can be partitioned into a countable collection of pairs, then by linearly ordering this set you obtain a choice function from the pairs, namely the minimal point from each pair.

It was proved by Fraenkel (with atoms, and later by Cohen without atoms) that it is consistent that a set which can be partitioned into pairs, but have no choice function from the pairs.

One may think that perhaps linearly ordering a set may be equivalent to choice from finite sets, but this is also not true. It is consistent that every family of finite sets admits a choice function, but there are sets which cannot be linearly ordered.