Can we find a well ordering on an infinite set with no largest element?












5












$begingroup$


According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.

My question is:




For a given infinite set, can we find a well ordering on it such that there is no largest element?











share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Set of natural numbers.
    $endgroup$
    – Wuestenfux
    Jul 2 '17 at 18:54






  • 2




    $begingroup$
    Induce the well-order by a bijection with a cardinal number.
    $endgroup$
    – Daniel Fischer
    Jul 2 '17 at 18:55










  • $begingroup$
    Use Choice + transfinite induction to define it one at a time?
    $endgroup$
    – Chappers
    Jul 2 '17 at 19:02










  • $begingroup$
    math.stackexchange.com/questions/6501/…
    $endgroup$
    – Count Iblis
    Jul 2 '17 at 19:16










  • $begingroup$
    @CountIblis That question is not related to this one at all.
    $endgroup$
    – Noah Schweber
    Jul 2 '17 at 20:02
















5












$begingroup$


According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.

My question is:




For a given infinite set, can we find a well ordering on it such that there is no largest element?











share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Set of natural numbers.
    $endgroup$
    – Wuestenfux
    Jul 2 '17 at 18:54






  • 2




    $begingroup$
    Induce the well-order by a bijection with a cardinal number.
    $endgroup$
    – Daniel Fischer
    Jul 2 '17 at 18:55










  • $begingroup$
    Use Choice + transfinite induction to define it one at a time?
    $endgroup$
    – Chappers
    Jul 2 '17 at 19:02










  • $begingroup$
    math.stackexchange.com/questions/6501/…
    $endgroup$
    – Count Iblis
    Jul 2 '17 at 19:16










  • $begingroup$
    @CountIblis That question is not related to this one at all.
    $endgroup$
    – Noah Schweber
    Jul 2 '17 at 20:02














5












5








5


2



$begingroup$


According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.

My question is:




For a given infinite set, can we find a well ordering on it such that there is no largest element?











share|cite|improve this question











$endgroup$




According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.

My question is:




For a given infinite set, can we find a well ordering on it such that there is no largest element?








elementary-set-theory well-orders






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jul 2 '17 at 22:52









RQM

1213




1213










asked Jul 2 '17 at 18:53









BumblebeeBumblebee

9,74912551




9,74912551








  • 2




    $begingroup$
    Set of natural numbers.
    $endgroup$
    – Wuestenfux
    Jul 2 '17 at 18:54






  • 2




    $begingroup$
    Induce the well-order by a bijection with a cardinal number.
    $endgroup$
    – Daniel Fischer
    Jul 2 '17 at 18:55










  • $begingroup$
    Use Choice + transfinite induction to define it one at a time?
    $endgroup$
    – Chappers
    Jul 2 '17 at 19:02










  • $begingroup$
    math.stackexchange.com/questions/6501/…
    $endgroup$
    – Count Iblis
    Jul 2 '17 at 19:16










  • $begingroup$
    @CountIblis That question is not related to this one at all.
    $endgroup$
    – Noah Schweber
    Jul 2 '17 at 20:02














  • 2




    $begingroup$
    Set of natural numbers.
    $endgroup$
    – Wuestenfux
    Jul 2 '17 at 18:54






  • 2




    $begingroup$
    Induce the well-order by a bijection with a cardinal number.
    $endgroup$
    – Daniel Fischer
    Jul 2 '17 at 18:55










  • $begingroup$
    Use Choice + transfinite induction to define it one at a time?
    $endgroup$
    – Chappers
    Jul 2 '17 at 19:02










  • $begingroup$
    math.stackexchange.com/questions/6501/…
    $endgroup$
    – Count Iblis
    Jul 2 '17 at 19:16










  • $begingroup$
    @CountIblis That question is not related to this one at all.
    $endgroup$
    – Noah Schweber
    Jul 2 '17 at 20:02








2




2




$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54




$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54




2




2




$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55




$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55












$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02




$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02












$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16




$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16












$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02




$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02










3 Answers
3






active

oldest

votes


















9












$begingroup$

Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.



Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.



It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.



If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff




  • $a, bin I_X$ and $a<b$ in the original sense of $X$; or


  • $a, bin F_X$ and $a<b$ in the original sense of $X$; or


  • $ain F_X, bin I_X$.







share|cite|improve this answer











$endgroup$





















    3












    $begingroup$

    If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.






    share|cite|improve this answer









    $endgroup$









    • 2




      $begingroup$
      As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
      $endgroup$
      – Noah Schweber
      Jul 2 '17 at 21:48






    • 1




      $begingroup$
      @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
      $endgroup$
      – Orest Bucicovschi
      Jul 2 '17 at 23:44



















    2












    $begingroup$

    In the usual development of ZFC, a cardinal is defined to the the
    least ordinal with a given cardinality. Infinite cardinals are "limit
    ordinals" --- as ordered sets they have no largest element.






    share|cite|improve this answer









    $endgroup$














      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      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
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2344254%2fcan-we-find-a-well-ordering-on-an-infinite-set-with-no-largest-element%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      3 Answers
      3






      active

      oldest

      votes








      3 Answers
      3






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      9












      $begingroup$

      Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.



      Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.



      It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.



      If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff




      • $a, bin I_X$ and $a<b$ in the original sense of $X$; or


      • $a, bin F_X$ and $a<b$ in the original sense of $X$; or


      • $ain F_X, bin I_X$.







      share|cite|improve this answer











      $endgroup$


















        9












        $begingroup$

        Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.



        Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.



        It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.



        If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff




        • $a, bin I_X$ and $a<b$ in the original sense of $X$; or


        • $a, bin F_X$ and $a<b$ in the original sense of $X$; or


        • $ain F_X, bin I_X$.







        share|cite|improve this answer











        $endgroup$
















          9












          9








          9





          $begingroup$

          Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.



          Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.



          It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.



          If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff




          • $a, bin I_X$ and $a<b$ in the original sense of $X$; or


          • $a, bin F_X$ and $a<b$ in the original sense of $X$; or


          • $ain F_X, bin I_X$.







          share|cite|improve this answer











          $endgroup$



          Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.



          Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.



          It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.



          If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff




          • $a, bin I_X$ and $a<b$ in the original sense of $X$; or


          • $a, bin F_X$ and $a<b$ in the original sense of $X$; or


          • $ain F_X, bin I_X$.








          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Jul 2 '17 at 21:47

























          answered Jul 2 '17 at 20:05









          Noah SchweberNoah Schweber

          128k10152294




          128k10152294























              3












              $begingroup$

              If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.






              share|cite|improve this answer









              $endgroup$









              • 2




                $begingroup$
                As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
                $endgroup$
                – Noah Schweber
                Jul 2 '17 at 21:48






              • 1




                $begingroup$
                @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
                $endgroup$
                – Orest Bucicovschi
                Jul 2 '17 at 23:44
















              3












              $begingroup$

              If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.






              share|cite|improve this answer









              $endgroup$









              • 2




                $begingroup$
                As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
                $endgroup$
                – Noah Schweber
                Jul 2 '17 at 21:48






              • 1




                $begingroup$
                @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
                $endgroup$
                – Orest Bucicovschi
                Jul 2 '17 at 23:44














              3












              3








              3





              $begingroup$

              If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.






              share|cite|improve this answer









              $endgroup$



              If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.







              share|cite|improve this answer












              share|cite|improve this answer



              share|cite|improve this answer










              answered Jul 2 '17 at 19:58









              Orest BucicovschiOrest Bucicovschi

              28.6k31748




              28.6k31748








              • 2




                $begingroup$
                As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
                $endgroup$
                – Noah Schweber
                Jul 2 '17 at 21:48






              • 1




                $begingroup$
                @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
                $endgroup$
                – Orest Bucicovschi
                Jul 2 '17 at 23:44














              • 2




                $begingroup$
                As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
                $endgroup$
                – Noah Schweber
                Jul 2 '17 at 21:48






              • 1




                $begingroup$
                @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
                $endgroup$
                – Orest Bucicovschi
                Jul 2 '17 at 23:44








              2




              2




              $begingroup$
              As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
              $endgroup$
              – Noah Schweber
              Jul 2 '17 at 21:48




              $begingroup$
              As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
              $endgroup$
              – Noah Schweber
              Jul 2 '17 at 21:48




              1




              1




              $begingroup$
              @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
              $endgroup$
              – Orest Bucicovschi
              Jul 2 '17 at 23:44




              $begingroup$
              @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
              $endgroup$
              – Orest Bucicovschi
              Jul 2 '17 at 23:44











              2












              $begingroup$

              In the usual development of ZFC, a cardinal is defined to the the
              least ordinal with a given cardinality. Infinite cardinals are "limit
              ordinals" --- as ordered sets they have no largest element.






              share|cite|improve this answer









              $endgroup$


















                2












                $begingroup$

                In the usual development of ZFC, a cardinal is defined to the the
                least ordinal with a given cardinality. Infinite cardinals are "limit
                ordinals" --- as ordered sets they have no largest element.






                share|cite|improve this answer









                $endgroup$
















                  2












                  2








                  2





                  $begingroup$

                  In the usual development of ZFC, a cardinal is defined to the the
                  least ordinal with a given cardinality. Infinite cardinals are "limit
                  ordinals" --- as ordered sets they have no largest element.






                  share|cite|improve this answer









                  $endgroup$



                  In the usual development of ZFC, a cardinal is defined to the the
                  least ordinal with a given cardinality. Infinite cardinals are "limit
                  ordinals" --- as ordered sets they have no largest element.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Jul 2 '17 at 18:56









                  Lord Shark the UnknownLord Shark the Unknown

                  108k1162135




                  108k1162135






























                      draft saved

                      draft discarded




















































                      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%2f2344254%2fcan-we-find-a-well-ordering-on-an-infinite-set-with-no-largest-element%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

                      Bressuire

                      Cabo Verde

                      Gyllenstierna