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
6
-
19$\begingroup$ The questioner only asks for a total order, not a well-ordering. $\endgroup$– Dan PetersenCommented Aug 31, 2010 at 16:13
-
3$\begingroup$ The existence of a total order on any set is equivalent to a well-order on any set, essentially by Hartogs theorem of 1915. $\endgroup$– John StillwellCommented Aug 31, 2010 at 16:30
-
4$\begingroup$ John, your answer seems to contradict mine. Am I mistaken? What I can prove from Hartog's theorem is that AC is equivalent to the assertion that any two sets are comparable in cardinality. Is that what you meant? $\endgroup$– Joel David HamkinsCommented Aug 31, 2010 at 16:53
-
3$\begingroup$ Joel, you're right. I confused the total order of cardinalities with the total ordering of an arbitrary set. $\endgroup$– John StillwellCommented Aug 31, 2010 at 18:50
-
3$\begingroup$ We might add by way of clarification, with regard to the original question, that ZF in itself does not determine whether all sets are totally ordered. We have no example of a nonempty set that has no total order because the Ordering Principle is independent of ZF (if ZF is consistent). $\endgroup$– MikeCCommented Sep 1, 2010 at 5:09
|
Show 1 more comment
4 Answers
$\begingroup$
$\endgroup$
2
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.)
answered Aug 31, 2010 at 16:47
-
$\begingroup$ I think DO should say that every infinite set has a dense linear order. $\endgroup$ Commented Aug 31, 2010 at 17:04
-
$\begingroup$ Yes, you are right, that is what he says. And the same for DPO, where he requires nontriviality---the pure antichain partial order doesn't count. $\endgroup$ Commented Aug 31, 2010 at 17:10
$\begingroup$
$\endgroup$
6
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\}$.
answered Aug 31, 2010 at 16:58
-
$\begingroup$ François, this is a very clear way to see it. Do you know to whom this result (on linear orders) is due? Gonzalez is focused mainly on dense orders, and doesn't seem to say who did the linear order case first. $\endgroup$ Commented Aug 31, 2010 at 17:15
-
$\begingroup$ I don't have the references with me, but I think for permutation models this is due to Läuchli, the corresponding standard model might be due to Jech. $\endgroup$ Commented Aug 31, 2010 at 18:58
-
2$\begingroup$ The Howard/Rubin book cites: James D. Halpern and Azriel Levy, The ordering theorem does not imply the axiom of choice, Notices of the AMS 11 (1964), 56. $\endgroup$ Commented May 19, 2013 at 16:20
-
2$\begingroup$ If one works in ZFA, the version of ZF that allows atoms, then the basic Fraenkel model and the second Fraenkel model (as defined in Jech's book "The Axiom of Choice") show the consistency of "there is a set with no linear order", while Mostowski's linearly ordered model shows that linear orderings of all sets don't yield the axiom of choice. So these ZFA consistency results go back to 1922 and 1937 respectively. The former transfers automatically to ZF by the Jech-Sochor metatheorem. I haven't checked whether perhaps the latter transfers also by Pincus's stronger metatheorems. $\endgroup$ Commented May 19, 2013 at 19:11
-
2$\begingroup$ @ArkaGhosh: No, see Jech's book. $\endgroup$ Commented Nov 19, 2021 at 22:08
$\begingroup$
$\endgroup$
1
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? :-)).
answered Aug 31, 2010 at 17:50
-
7$\begingroup$ Just to avoid a possible misunderstanding: This equivalence was used in that paper, but it isn't due to me. I don't know who first noticed it. $\endgroup$ Commented May 24, 2013 at 5:27
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ You might want to check math.stackexchange.com/q/271003/622 for an explanation of Francois' answer (recall that the ultrafilter theorem is equivalent to the compactness theorem of first-order logic). $\endgroup$– Asaf Karagila ♦Commented May 19, 2013 at 7:39
-
$\begingroup$ The trouble, as I said, is that I've not yet learned enough logic to be able to feel like I really understand an argument appealing to the compactness theorem. It's a deficiency in my skill set, not the proof technique. I posted an alternative in case anyone else is more comfortable with the approach I used. $\endgroup$– dfeuerCommented May 19, 2013 at 8:34