The question is the title.
Working in ZF, is it true that: for every nonempty set X, there exists a total order on X ?
If it is false, do we have an example of a nonempty set that has no total order?
Thanks
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityThe question is the title.
Working in ZF, is it true that: for every nonempty set X, there exists a total order on X ?
If it is false, do we have an example of a nonempty set that has no total order?
Thanks
In the paper Dense orderings, partitions and weak forms of choice, by Carlos G. Gonzalez FUNDAMENTA MATHEMATICAE 147 (1995), the author states the following theorem, where AC is the Axiom of Choice, DO is the assertion that every infinite set has a dense linear order, O is the assertion that every set has a linear order, and DPO is the assertion that every infinite set has a (nontrivial) dense partial order.
Theorem 1. AC implies DO implies O implies DPO. Moreover, none of the implications is reversible in ZF and DPO is independent of ZF.
Thus, in particular, the assertion that every set has a total order is strictly weaker than AC.
(Also, it would seem that Gonzalez means to assume Con(ZF) for the latter claims of his theorem.)
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:
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\}$.
This is rather a comment than an answer.
The axiom of choice is equivalent(!) to the statement that every total ordered set can be well ordered.
This is proven in
A. Blass, Existence of bases implies the axiom of choice, Axiomatic set theory (Boulder, Colo., 1983), 31--33, Contemp. Math., 31, Amer. Math. Soc., Providence, RI, 1984.
(A. Blass sent me this article by mail six years ago ... perhaps he reads this here as a MO member? :-)).
I'm just a student, so the deep logical principles behind François G. Dorais's answer are a drop over my head. However, I was able to find another Ultrafilter Lemma/Boolean Prime Ideal Theorem equivalent that seems a natural fit to the problem: the restricted Tukey-Teichmüller Theorem. Specifically, let $\mathscr A$ be the set of all relations on $X$ whose transitive closures are strict (partial) orderings. It's not hard to show that $\mathscr A$ satisfies the premises of rTT, where $(x,y)'$ is defined as $(y,x)$ for each $(x,y) \in S \times S$. Then rTT effectively shows that some element of $\mathscr A$ is connected, and thus its transitive closure is a strict total ordering of $S$ (in fact it is itself transitive, but this is not important). I've written up a more detailed outline on ProofWiki.