Let us first propose the following axiom,

Axiom of Ordering $(\sf{AO})$. If $S$ be a non-empty set. Let $a,b\in S$. Then the set $\{a,b\}$ can be totally ordered.

Now let us consider $\sf{ZFO}$ set theory where $\sf{AC}$ is replaced by $\sf{AO}$. Then,

Can every non-empty set satisfying the axioms of $\sf{ZFO}$ be totally ordered?

By the principle of mathematical induction it follows that every finite set can be totally ordered. Intuitively it also seems to me that every infinite set can be totally ordered but I am unable to write a proof (assuming it exists).

Can anyone help?

Edit:- In view of the answer below, the question should be modified as,

Can every non-empty set satisfying the axioms of $\sf{ZF}$ be totally ordered?

  • 1
    $\begingroup$ Also $\sf AO$ makes no sense. You're only ordering two elements at a time. Maybe you want to assert that $S$ itself has a total ordering (and to avoid triviality you probably want to claim that it is irreflexive and transitive, namely a linear ordering)? $\endgroup$ – Asaf Karagila Jan 9 '16 at 16:24
  • 4
    $\begingroup$ It's a trivial consequence that every two elements set can be linearly ordered. It says nothing about whether or not the entire set can be linearly ordered. $\endgroup$ – Asaf Karagila Jan 9 '16 at 16:46
  • 1
    $\begingroup$ If $\{a,b\}$ is a two elements set, then $\{(a,a),(a,b),(b,b)\}$ is a total ordering of that set. Or if you prefer irrelefexive ones, $\{(a,b)\}$. There, it's totally ordered! But did I tell you anything about whether or not any larger set can be totally ordered? I did not. $\endgroup$ – Asaf Karagila Jan 9 '16 at 16:49
  • 3
    $\begingroup$ Let me write it again. $\sf ZF+AO$ does not prove that every set can be linearly ordered. It just proves that every two-elements set can be linearly ordered, an incredibly uninteresting statement. $\endgroup$ – Asaf Karagila Jan 9 '16 at 16:52
  • 3
    $\begingroup$ @user170039 As a side note, even ZFC can't prove that the whole model can be linearly ordered. So "every set in the model is orderable" does not imply "the whole model is orderable." (Technically this statement is a bit wrong - I should say either that there is a model of ZFC with no definable ordering, or talk about some class theory extending ZFC - but the point stands.) $\endgroup$ – Noah Schweber Jan 10 '16 at 6:04

The answer is maybe negative. It depends on your universe of sets outside the model.

  1. There might not be any models of $\sf ZF$ to begin with. In that case there is a vacuous positive answer.

  2. The meta theory might include the axiom of choice, in which case every set can be ordered, in particular models of $\sf ZF$.

  3. But it could be that the answer is negative, too. If $\kappa$ is inaccessible, and we add a set which cannot be linearly ordered of rank $<\kappa$, then $V_\kappa$ still satisfies the axioms of $\sf ZF$, but it cannot be linearly ordered since a linear ordering will imply every set inside $V_\kappa$ can be ordered as well.

    One can do even more, and by being careful make $V_\kappa$ non-linearly orderable, while at the same time not violate the axiom of choice below $\kappa$. So not even if you have a model of $\sf ZFC$ you cannot guarantee it to be linearly orderable.

  • $\begingroup$ Actually, my intuition went on as follows: Let $a,b\in S$. Then introduce a total order $\le_{ab}$ on $\{a,b\}$. I would define the total order $\le$ on $S$ as $\le =\displaystyle\bigcup_{a,b\in S} \le_{ab}$. But it seems to be a very stupid idea now. $\endgroup$ – user 170039 Jan 10 '16 at 5:55
  • 3
    $\begingroup$ @user170039 Here's why that doesn't work. In order for $\le$ to actually be a total order on $S$, it needs to be transitive - so we can't have e.g. $a\le_{ab}b, b\le_{bc}c, c\le_{ca}a$. So we need to pick the orderings on pairs "compatibly." But in order to do this, we already need an ordering on $S$! Even ignoring compatability, though, we have a problem: clearly you want $\le_{ab}$ to be one of the two possible orderings on $\{a, b\}$. The set of possible orderings on a given pair, of course, has two elements. But the axiom of choice for families of pairs is already independent of ZF. $\endgroup$ – Noah Schweber Jan 10 '16 at 5:58

$\operatorname{ZF}$ already proves $\operatorname{AO}$. Given two sets $a,b$ we have the total ordering $\preceq := \{ (a,a), (a,b), (b,b) \}$ on $\{a,b\}$.

What you probably have in mind is the following: Define a set of socks $S$ to be a set that consists entirely of pair $\{x,y\} \in S$. Let $\operatorname{AOS}$ state that there is a linear order on every set of socks.

We know that $\operatorname{ZF+ \neg AOS}$ is consistent relative to $\operatorname{ZF}$. I suspect that $\operatorname{ZF + AOS + \neg AC}$ is also consistent, but I'm not aware of a suitable model ( and I further conjecture that Asaf is).

Regarding the consistency of $\operatorname{ZF} \text{ + not every set has a linear order}$: It is indeed possible that there is a model of $\operatorname{ZF}$ which contains a set without a linear order. See the post over at mathoverflow for a reference and further discussions.

  • $\begingroup$ But that doesn't answer my question. $\endgroup$ – user 170039 Jan 9 '16 at 14:29
  • $\begingroup$ @user170039 So your question is whether $\operatorname{ZF} \text{ + 'not every set has a linear order'}$ is consistent relative to $\operatorname{ZF}$? $\endgroup$ – Stefan Mesken Jan 9 '16 at 14:37
  • $\begingroup$ Why $\neg \sf{AC}$ comes in picture? $\endgroup$ – user 170039 Jan 9 '16 at 14:42
  • $\begingroup$ @user170039 Now my comment might fit your question. $\endgroup$ – Stefan Mesken Jan 9 '16 at 14:43
  • $\begingroup$ Yes, I think so. $\endgroup$ – user 170039 Jan 9 '16 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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