# Does linear ordering need the Axiom of Choice?

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

• Hi. I made a minor language fix to the post. (I've noticed the same habit in some other east asian language speakers.) Using this new version make you sound more fluent, so I hope it is useful for you. – rschwieb Feb 22 '13 at 15:32
• Asaf's answer alludes to this partial result but I thought I might mention it explicitly: ZF proves that the power set of every ordinal $\kappa$ is linearly ordered by the lexicographical ordering. – Trevor Wilson Feb 22 '13 at 19:20
• Following Trevor comment: But, on the other hand, ZF does not prove that $\mathcal P(\mathbb R)$ (equivalently, $\mathcal P^2(\omega)$) is linearly orderable. – Andrés E. Caicedo Feb 23 '13 at 0:10
• Following @Andres comment, while it's definitely a beautiful argument that under AD $\cal P(\Bbb R)$ cannot be linearly ordered; it's also worth noting that Cohen's second model (to which I refer in the end of my answer) is such that the family of pairs without a choice function is actually a family of sets of subsets of $\Bbb R$, that is, it's a subset of $\cal P(\Bbb R)$ and as a consequence $\cal P(\Bbb R)$ cannot be linearly ordered in that model. – Asaf Karagila Feb 23 '13 at 0:54

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.

• axiom of choice for finite sets!! for finite sets axiom of choice is not needed. – user59671 Feb 22 '13 at 15:13
• @CutieKrait: The axiom of choice for finite sets says that an arbitrary set $\{X_i:i\in I\}$ of non-empty finite sets has a choice function. This does not follow from ZF alone and does require some of the strength of AC. – Brian M. Scott Feb 22 '13 at 15:15
• Linearly ordering is weaker the UFT, so it's weaker than AC. Thanks – Chao Chen Feb 22 '13 at 15:32
• @ChaoChen: That’s right. But it doesn’t follow from ZF alone. You’re welcome. – Brian M. Scott Feb 22 '13 at 15:36
• @CutieKrait I think you were thinking of the finite axiom of choice, that says that if $I$ is finite, then any collection $\{X_i\mid i\in I\}$ of non-empty sets admits a choice function. This indeed follows from $\mathsf{ZF}$. – Andrés E. Caicedo Feb 22 '13 at 15:43

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.

• In the second principle it seems like you need something about the set being infinite (or Dedekind-infinite perhaps?) – Trevor Wilson Feb 22 '13 at 19:22
• Oh, you are correct. Dedekind-finite sets may be linearly ordered in a rather high density. You can arrange that for every regular $\kappa$ there is a Dedekind-finite set dense in $2^\kappa$. – Asaf Karagila Feb 22 '13 at 19:30