Two conflicting (?) versions of the Downward Löwenheim-Skolem Theorem












2












$begingroup$


I found two definitions of the Downward Löwenheim-Skolem Theorem:




Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
infinite.




From Zach et al.




Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.




From Weiss et al.



What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".



Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?



Looking forward to the responses 😊.










share|cite|improve this question











$endgroup$

















    2












    $begingroup$


    I found two definitions of the Downward Löwenheim-Skolem Theorem:




    Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
    infinite.




    From Zach et al.




    Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.




    From Weiss et al.



    What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".



    Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?



    Looking forward to the responses 😊.










    share|cite|improve this question











    $endgroup$















      2












      2








      2





      $begingroup$


      I found two definitions of the Downward Löwenheim-Skolem Theorem:




      Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
      infinite.




      From Zach et al.




      Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.




      From Weiss et al.



      What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".



      Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?



      Looking forward to the responses 😊.










      share|cite|improve this question











      $endgroup$




      I found two definitions of the Downward Löwenheim-Skolem Theorem:




      Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
      infinite.




      From Zach et al.




      Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.




      From Weiss et al.



      What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".



      Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?



      Looking forward to the responses 😊.







      logic first-order-logic model-theory






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 26 at 13:39







      Rafael Bankosegger

















      asked Jan 26 at 12:08









      Rafael BankoseggerRafael Bankosegger

      595




      595






















          1 Answer
          1






          active

          oldest

          votes


















          3












          $begingroup$

          Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.



          Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.



          With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.



          In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.



          From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.



          Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.



          Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.



          I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
            $endgroup$
            – Berci
            Jan 26 at 12:30










          • $begingroup$
            @Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
            $endgroup$
            – Max
            Jan 26 at 12:53






          • 7




            $begingroup$
            This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:13






          • 5




            $begingroup$
            Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:17












          • $begingroup$
            @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
            $endgroup$
            – Max
            Jan 26 at 13:19











          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%2f3088179%2ftwo-conflicting-versions-of-the-downward-l%25c3%25b6wenheim-skolem-theorem%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          3












          $begingroup$

          Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.



          Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.



          With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.



          In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.



          From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.



          Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.



          Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.



          I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
            $endgroup$
            – Berci
            Jan 26 at 12:30










          • $begingroup$
            @Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
            $endgroup$
            – Max
            Jan 26 at 12:53






          • 7




            $begingroup$
            This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:13






          • 5




            $begingroup$
            Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:17












          • $begingroup$
            @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
            $endgroup$
            – Max
            Jan 26 at 13:19
















          3












          $begingroup$

          Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.



          Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.



          With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.



          In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.



          From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.



          Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.



          Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.



          I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
            $endgroup$
            – Berci
            Jan 26 at 12:30










          • $begingroup$
            @Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
            $endgroup$
            – Max
            Jan 26 at 12:53






          • 7




            $begingroup$
            This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:13






          • 5




            $begingroup$
            Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:17












          • $begingroup$
            @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
            $endgroup$
            – Max
            Jan 26 at 13:19














          3












          3








          3





          $begingroup$

          Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.



          Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.



          With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.



          In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.



          From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.



          Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.



          Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.



          I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.






          share|cite|improve this answer









          $endgroup$



          Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.



          Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.



          With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.



          In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.



          From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.



          Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.



          Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.



          I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Jan 26 at 12:23









          MaxMax

          15.5k11143




          15.5k11143












          • $begingroup$
            In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
            $endgroup$
            – Berci
            Jan 26 at 12:30










          • $begingroup$
            @Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
            $endgroup$
            – Max
            Jan 26 at 12:53






          • 7




            $begingroup$
            This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:13






          • 5




            $begingroup$
            Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:17












          • $begingroup$
            @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
            $endgroup$
            – Max
            Jan 26 at 13:19


















          • $begingroup$
            In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
            $endgroup$
            – Berci
            Jan 26 at 12:30










          • $begingroup$
            @Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
            $endgroup$
            – Max
            Jan 26 at 12:53






          • 7




            $begingroup$
            This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:13






          • 5




            $begingroup$
            Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
            $endgroup$
            – Carl Mummert
            Jan 26 at 13:17












          • $begingroup$
            @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
            $endgroup$
            – Max
            Jan 26 at 13:19
















          $begingroup$
          In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
          $endgroup$
          – Berci
          Jan 26 at 12:30




          $begingroup$
          In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
          $endgroup$
          – Berci
          Jan 26 at 12:30












          $begingroup$
          @Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
          $endgroup$
          – Max
          Jan 26 at 12:53




          $begingroup$
          @Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
          $endgroup$
          – Max
          Jan 26 at 12:53




          7




          7




          $begingroup$
          This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
          $endgroup$
          – Carl Mummert
          Jan 26 at 13:13




          $begingroup$
          This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
          $endgroup$
          – Carl Mummert
          Jan 26 at 13:13




          5




          5




          $begingroup$
          Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
          $endgroup$
          – Carl Mummert
          Jan 26 at 13:17






          $begingroup$
          Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
          $endgroup$
          – Carl Mummert
          Jan 26 at 13:17














          $begingroup$
          @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
          $endgroup$
          – Max
          Jan 26 at 13:19




          $begingroup$
          @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
          $endgroup$
          – Max
          Jan 26 at 13:19


















          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%2f3088179%2ftwo-conflicting-versions-of-the-downward-l%25c3%25b6wenheim-skolem-theorem%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

          MongoDB - Not Authorized To Execute Command

          Npm cannot find a required file even through it is in the searched directory

          in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith