Models of set theory where not every set can be linearly ordered

Can anybody point me towards a model of set theory where not every set can be linearly ordered, and a corresponding proof. I have seen it claimed that in Fraenkels second permutation model that there is a set that cannot be linearly ordered, but cannot find a proof.

Essentially, I am asking for a proof that without choice sometimes the linear ordering principle fails.

• In the case of the Fraenkel model, would this just come down to saying that any linear ordering would have a finite support, and then we just consider a permutation of two atoms outside of said support? – LGar Apr 15 at 19:23
• Yes, by the way, a direct argument in both the models of Fraenkel is that any linear order would have a finite support and we can find a permutation that moves some things in an incongruous way. – Asaf Karagila Apr 15 at 21:35
• Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice – YuiTo Cheng Apr 15 at 23:04
• This question is not as far as I can tell a duplicate - that question is asking for a proof of the linear ordering principle without choice, while I was asking for a proof that the linear ordering principle can sometimes fail in the abscence of choice. – LGar Apr 16 at 0:21
• What about Is every set linearly ordered in ZF – YuiTo Cheng Apr 16 at 0:57

Yes, both of Fraenkel's models are examples of such models. To see why note that:

1. In the first model, the atoms are an amorphous set. Namely, there cannot be split into two infinite sets. An amorphous set cannot be linearly ordered. To see why, note that $$\{a\in A\mid a\text{ defines a finite initial segment}\}$$ is either finite or co-finite. Assume it's co-finite, otherwise take the reverse order, then by removing finitely many elements we have a linear ordering where every proper initial segment is finite. This defines a bijection with $$\omega$$, of course. So the set can be split into two infinite sets after all.

2. In the second model, the atoms can be written as a countable union of pairs which do not have a choice function. If the atoms were linearly orderable in that model, then we could have defined a choice function from the pairs: take the smallest one.

For models of $$\sf ZF$$ one can imitate Fraenkel's construction using sets-of-sets-of Cohen reals as your atoms. This can be found in Jech's "Axiom of Choice" book in Chapter 5, as Cohen's second model.

An interesting example of a different kind is any model where all sets of reals have the Baire property. In any such set the quotient of $$\mathbb R$$ by the Vitali equivalence relation is not linearly orderable. See here for a sketch.

Examples of such models are Solovay's model where all sets of reals are Lebesgue measurable, or natural models of the axiom of determinacy, or Shelah's model from section 7 of

MR0768264 (86g:03082a). Shelah, Saharon. Can you take Solovay's inaccessible away? Israel J. Math. 48 (1984), no. 1, 1–47.

• Good examples, albeit significantly more complicated! :-) – Asaf Karagila Apr 15 at 21:33