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.
On
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.
Yes, both of Fraenkel's models are examples of such models. To see why note that:
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.
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.