5
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – LGar
    Apr 15, 2019 at 19:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila ♦
    Apr 15, 2019 at 21:35
  • 1
    $\begingroup$ Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice $\endgroup$
    – YuiTo Cheng
    Apr 15, 2019 at 23:04
  • $\begingroup$ 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. $\endgroup$
    – LGar
    Apr 16, 2019 at 0:21
  • $\begingroup$ What about Is every set linearly ordered in ZF $\endgroup$
    – YuiTo Cheng
    Apr 16, 2019 at 0:57

2 Answers 2

Reset to default
9
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Good examples, albeit significantly more complicated! :-) $\endgroup$
    – Asaf Karagila ♦
    Apr 15, 2019 at 21:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .