Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
12  
The questioner only asks for a total order, not a well-ordering. –  Dan Petersen Aug 31 '10 at 16:13
3  
The existence of a total order on any set is equivalent to a well-order on any set, essentially by Hartogs theorem of 1915. –  John Stillwell Aug 31 '10 at 16:30
3  
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? –  Joel David Hamkins Aug 31 '10 at 16:53
3  
Joel, you're right. I confused the total order of cardinalities with the total ordering of an arbitrary set. –  John Stillwell Aug 31 '10 at 18:50
2  
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). –  MikeC Sep 1 '10 at 5:09
show 1 more comment

4 Answers 4

up vote 21 down vote accepted

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.)

share|improve this answer
    
I think DO should say that every infinite set has a dense linear order. –  François G. Dorais Aug 31 '10 at 17:04
    
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. –  Joel David Hamkins Aug 31 '10 at 17:10
add comment

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\}$.

share|improve this answer
    
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. –  Joel David Hamkins Aug 31 '10 at 17:15
    
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. –  François G. Dorais Aug 31 '10 at 18:58
1  
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. –  András Salamon May 19 '13 at 16:20
1  
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. –  Andreas Blass May 19 '13 at 19:11
add comment

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? :-)).

share|improve this answer
    
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. –  Andreas Blass May 24 '13 at 5:27
add comment

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.

share|improve this answer
    
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). –  Asaf Karagila May 19 '13 at 7:39
    
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. –  dfeuer May 19 '13 at 8:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.