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












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.










share|cite|improve this question









New contributor




LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 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 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 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 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 at 0:21










  • $begingroup$
    What about Is every set linearly ordered in ZF
    $endgroup$
    – YuiTo Cheng
    Apr 16 at 0:57


















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.










share|cite|improve this question









New contributor




LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 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 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 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 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 at 0:21










  • $begingroup$
    What about Is every set linearly ordered in ZF
    $endgroup$
    – YuiTo Cheng
    Apr 16 at 0:57
















5












5








5


1



$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.










share|cite|improve this question









New contributor




LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




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.







set-theory axiom-of-choice






share|cite|improve this question









New contributor




LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited Apr 16 at 0:22







LGar













New contributor




LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked Apr 15 at 19:21









LGarLGar

506




506




New contributor




LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 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 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 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 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 at 0:21










  • $begingroup$
    What about Is every set linearly ordered in ZF
    $endgroup$
    – YuiTo Cheng
    Apr 16 at 0:57
















  • 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 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 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 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 at 0:21










  • $begingroup$
    What about Is every set linearly ordered in ZF
    $endgroup$
    – YuiTo Cheng
    Apr 16 at 0:57










1




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 at 19:23




$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 at 19:23




1




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 at 21:35




$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 at 21:35




1




1




$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 at 23:04




$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 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 at 0:21




$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 at 0:21












$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57






$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57












2 Answers
2






active

oldest

votes


















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 ${ain Amid atext{ 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.






share|cite|improve this answer









$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.







    share|cite|improve this answer









    $endgroup$









    • 1




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












    Your Answer








    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });






    LGar is a new contributor. Be nice, and check out our Code of Conduct.










    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3189095%2fmodels-of-set-theory-where-not-every-set-can-be-linearly-ordered%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    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 ${ain Amid atext{ 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.






    share|cite|improve this answer









    $endgroup$


















      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 ${ain Amid atext{ 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.






      share|cite|improve this answer









      $endgroup$
















        9












        9








        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 ${ain Amid atext{ 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.






        share|cite|improve this answer









        $endgroup$



        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 ${ain Amid atext{ 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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Apr 15 at 19:30









        Asaf KaragilaAsaf Karagila

        309k33441775




        309k33441775























            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.







            share|cite|improve this answer









            $endgroup$









            • 1




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
















            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.







            share|cite|improve this answer









            $endgroup$









            • 1




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














            7












            7








            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.







            share|cite|improve this answer









            $endgroup$



            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.








            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Apr 15 at 19:39









            Andrés E. CaicedoAndrés E. Caicedo

            66.1k8160252




            66.1k8160252








            • 1




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














            • 1




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








            1




            1




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




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










            LGar is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            LGar is a new contributor. Be nice, and check out our Code of Conduct.













            LGar is a new contributor. Be nice, and check out our Code of Conduct.












            LGar is a new contributor. Be nice, and check out our Code of Conduct.
















            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3189095%2fmodels-of-set-theory-where-not-every-set-can-be-linearly-ordered%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Plaza Victoria

            Puebla de Zaragoza

            Musa