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
Are All Sets Totally Ordered? – Set Theory and Axiom of Choice
axiom-of-choiceset-theory
Related Solutions
Something very close to François' conditions achieves the desired if-and-only-if version of the theorem for partial orders, providing an induction-like characterization of the complete partial orders, just as Pete's theorem characterizes the complete total orders.
Suppose that $(P,\lt)$ is a partial order. We say that it is complete if every subset $A$ has a least upper bound $sup(A)$ and a greatest lower bound $inf(A)$. This implies that $(P,\lt)$ has a least and greatest element, and in this case, it is easy to see that completeness is equivalent to the assertion that every set has a greatest lower bound (the least upper bound of a set with upper bounds is the greatest lower bound of its upper bounds). The complete partial orders are exactly the complete lattices.
For the purpose of this question, let us define that $S\subset P$ is inductive if the following occur:
- (1) $S$ is downward closed: $y\lt x\in S\to y\in S$;
- (2) $S$ has no largest element, except possibly the largest element of $P$;
- (3) If $d=sup(A)$ for some $A\subset S$, then $d\in S$.
In (2), by a largest element, I mean an element that is larger than all other elements (in distinction with maximal element, a weaker concept). Conditions (2) and (3) are both slightly weaker than François' conditions. The difference in (2) is that we no longer assume that a condition $x\in S$ can be extended in any particular direction, and the difference in (3) is that we are not assuming here that $P$ is complete, but only that $S$ contains the suprema of its subsets, when these suprema exist.
Lastly, define that a partial order $(P,\lt)$ has partial-order induction if the only inductive set is all of $P$.
Theorem. For any partial order $(P,\lt)$, the following are equivalent:
- $(P,\lt)$ is complete.
- $(P,\lt)$ has least and greatest elements and satisfies partial-order induction.
Proof. For the forward implication, suppose $(P,\lt)$ is complete. It follows that $(P,\lt)$ has least and greatest elements, since these are the sup and inf of the emptyset. Suppose that $S\subset P$ is inductive. By (3) we know $sup(S)\in S$, which would make it the largest element of $S$, contrary to (2), unless $sup(S)$ is largest in $P$, in which case $S=P$ by (1). So $(P,\lt)$ has partial-order induction.
Conversely, suppose that $(P,\lt)$ has least and greatest elements and satisfies partial-order induction. We want to prove completeness. Suppose $B\subset P$ is nonempty and has no greatest lower bound. Let $S$ be the set of lower bounds of $B$. This is closed downwards, and so (1) holds. Since $B$ has no greatest lower bound, it follows that $S$ has no largest element, and so (2) holds. Finally, if $A\subset S$ and $sup(A)$ exists in $P$, then it remains a lower bound of $B$, since every element of $B$ is an upper bound of $A$ and $sup(A)$ is the least upper bound of $A$. Thus, (3) holds and so $S$ is inductive, contrary to the fact that it contains no elements of $B$. Thus, $B$ must have a greatest lower bound after all, and so $(P,\lt)$ is complete. QED
Note that when $(P,\lt)$ is a total order, then these concepts reduce to the conditions Pete mentions in the question (adding a least and greatest element if necessary). Thus, this theorem seems to be the desired generalization.
(I have deleted my other answer to the question, as it was based on a misunderstanding of the question.)
First I'll remark that for the first question, note that the or cannot be exclusive since $\omega$ is both even and odd.
Now to take some definitions from [1] if $A$ is an amorphous set, let $U$ be a partition of $A$ into infinitely many parts. It follows that every $A\in U$ is finite, and all but finitely many have the same size. Let $n$ be that size (Truss calls this gauge of $U$).
We say that $A$ is strictly amorphous (also known as strongly amorphous) if there are no partitions with gauge $>1$; we say that $A$ is bounded amorphous if there is a finite bound on the possible gauges; and unbounded amorphous otherwise.
Some remarks about the first question:
Note that if $A$ is strictly amorphous then it is neither odd nor even. Also note that if $A$ is bounded amorphous (say by gauge $n$) then taking $U$ a partition of $A$ into parts of size $n$ and perhaps discarding a few elements gives us that $A/U$ is strictly amorphous:
Otherwise we could partition $A/U$ into pairs (or more) and the union of each part would give a partition of $A$ whose gauge is $>n$.
Therefore, to answer this question one first has to assure that no bounded amorphous set exists. If no bounded amorphous exists (which is consistent) then every amorphous set is either odd or even (depending on the partitions with gauge $2$).
There are a handful of examples to answer the second question in the paper.
I'll add a final remark that a bounded amorphous cannot have a group structure, but an unbounded amorphous can. In particular it is possible to have vector spaces which are amorphous sets (see my answers here and here).
Bibliography:
- J.K.Truss, The structure of amorphous sets, Annals of Pure and Applied Logic, 73 (1995), 191-233.
Best Answer
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.)