set theory - Are all sets totally ordered ?

No. The Ordering Principle known to be independent of ZF. It is however strictly weaker than the Axiom of Choice.

Indeed, the Ordering Principle follows from the Ultrafilter Theorem. To see this consider the propositional theory $T_X$ with variables $P_{x,y}$ for $x, y in X$ whose axioms are:

• $P_{x,y} land P_{y,z} to P_{x,z}$.


• $P_{x,y} lor P_{y,x}$ when $x neq y$.


• $lnot P_{x,x}$.

This theory is obviously finitely consistent, so by the Propositional Completeness Theorem (which is equivalent to the Ultrafilter Theorem) it has a model. The set of all pairs $(x,y)$ such that $P_{x,y}$ is true in that model gives a linear ordering of the set $X$.

Also, the Ordering Principle implies the Axiom of Finite Choice: Every family of nonempty finite sets has a choice function. To see this, let ${x_i : i in I}$ be a family of nonempty finite sets. Let ${<}$ be a linear ordering of $X = bigcup_{i in I} x_i$. For each $i$, let $a_i$ be the ${<}$-minimal element of $x_i$, which exists since $x_i$ is finite. Then $i mapsto a_i$ is a choice function for the family ${x_i : i in I}$.