If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.












1












$begingroup$


This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:



Let $Sigma$ a set of sentences and $phi$ a sentence.



If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.



The proof by contradiction reads:



"If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."



How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?



From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?










share|cite|improve this question









$endgroup$

















    1












    $begingroup$


    This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:



    Let $Sigma$ a set of sentences and $phi$ a sentence.



    If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.



    The proof by contradiction reads:



    "If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."



    How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?



    From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?










    share|cite|improve this question









    $endgroup$















      1












      1








      1


      1



      $begingroup$


      This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:



      Let $Sigma$ a set of sentences and $phi$ a sentence.



      If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.



      The proof by contradiction reads:



      "If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."



      How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?



      From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?










      share|cite|improve this question









      $endgroup$




      This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:



      Let $Sigma$ a set of sentences and $phi$ a sentence.



      If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.



      The proof by contradiction reads:



      "If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."



      How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?



      From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?







      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










      asked Dec 8 '18 at 20:07









      MikeMike

      709415




      709415






















          3 Answers
          3






          active

          oldest

          votes


















          3












          $begingroup$

          First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.



          What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)





          This is in fact the crux of the problem!



          Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).





          All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"



          Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).






          share|cite|improve this answer









          $endgroup$





















            3












            $begingroup$

            My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:



            If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
              $endgroup$
              – Noah Schweber
              Dec 8 '18 at 20:28










            • $begingroup$
              @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
              $endgroup$
              – Mike
              Dec 8 '18 at 20:31










            • $begingroup$
              @Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
              $endgroup$
              – Noah Schweber
              Dec 8 '18 at 20:32












            • $begingroup$
              @NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
              $endgroup$
              – Mike
              Dec 8 '18 at 20:36












            • $begingroup$
              @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
              $endgroup$
              – Henning Makholm
              Dec 8 '18 at 20:51



















            1












            $begingroup$

            Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$






            share|cite|improve this answer









            $endgroup$









            • 1




              $begingroup$
              So does Doets assume that $Sigma$ has a model?
              $endgroup$
              – Mike
              Dec 8 '18 at 20:32










            • $begingroup$
              If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
              $endgroup$
              – Holo
              Dec 8 '18 at 20:35












            • $begingroup$
              @Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
              $endgroup$
              – Noah Schweber
              Dec 8 '18 at 20:38










            • $begingroup$
              @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
              $endgroup$
              – Holo
              Dec 8 '18 at 20:50










            • $begingroup$
              @Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
              $endgroup$
              – Noah Schweber
              Dec 8 '18 at 20:51













            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%2f3031577%2fif-sigma-models-phi-then-for-some-finite-delta-subset-sigma-delta%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









            3












            $begingroup$

            First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.



            What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)





            This is in fact the crux of the problem!



            Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).





            All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"



            Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).






            share|cite|improve this answer









            $endgroup$


















              3












              $begingroup$

              First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.



              What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)





              This is in fact the crux of the problem!



              Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).





              All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"



              Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).






              share|cite|improve this answer









              $endgroup$
















                3












                3








                3





                $begingroup$

                First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.



                What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)





                This is in fact the crux of the problem!



                Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).





                All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"



                Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).






                share|cite|improve this answer









                $endgroup$



                First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.



                What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)





                This is in fact the crux of the problem!



                Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).





                All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"



                Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Dec 8 '18 at 20:45









                Noah SchweberNoah Schweber

                123k10150286




                123k10150286























                    3












                    $begingroup$

                    My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:



                    If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:28










                    • $begingroup$
                      @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:31










                    • $begingroup$
                      @Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:32












                    • $begingroup$
                      @NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:36












                    • $begingroup$
                      @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
                      $endgroup$
                      – Henning Makholm
                      Dec 8 '18 at 20:51
















                    3












                    $begingroup$

                    My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:



                    If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:28










                    • $begingroup$
                      @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:31










                    • $begingroup$
                      @Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:32












                    • $begingroup$
                      @NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:36












                    • $begingroup$
                      @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
                      $endgroup$
                      – Henning Makholm
                      Dec 8 '18 at 20:51














                    3












                    3








                    3





                    $begingroup$

                    My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:



                    If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).






                    share|cite|improve this answer









                    $endgroup$



                    My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:



                    If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Dec 8 '18 at 20:14









                    Henning MakholmHenning Makholm

                    240k17305541




                    240k17305541












                    • $begingroup$
                      To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:28










                    • $begingroup$
                      @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:31










                    • $begingroup$
                      @Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:32












                    • $begingroup$
                      @NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:36












                    • $begingroup$
                      @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
                      $endgroup$
                      – Henning Makholm
                      Dec 8 '18 at 20:51


















                    • $begingroup$
                      To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:28










                    • $begingroup$
                      @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:31










                    • $begingroup$
                      @Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:32












                    • $begingroup$
                      @NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:36












                    • $begingroup$
                      @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
                      $endgroup$
                      – Henning Makholm
                      Dec 8 '18 at 20:51
















                    $begingroup$
                    To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:28




                    $begingroup$
                    To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:28












                    $begingroup$
                    @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
                    $endgroup$
                    – Mike
                    Dec 8 '18 at 20:31




                    $begingroup$
                    @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
                    $endgroup$
                    – Mike
                    Dec 8 '18 at 20:31












                    $begingroup$
                    @Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:32






                    $begingroup$
                    @Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:32














                    $begingroup$
                    @NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
                    $endgroup$
                    – Mike
                    Dec 8 '18 at 20:36






                    $begingroup$
                    @NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
                    $endgroup$
                    – Mike
                    Dec 8 '18 at 20:36














                    $begingroup$
                    @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
                    $endgroup$
                    – Henning Makholm
                    Dec 8 '18 at 20:51




                    $begingroup$
                    @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
                    $endgroup$
                    – Henning Makholm
                    Dec 8 '18 at 20:51











                    1












                    $begingroup$

                    Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$






                    share|cite|improve this answer









                    $endgroup$









                    • 1




                      $begingroup$
                      So does Doets assume that $Sigma$ has a model?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:32










                    • $begingroup$
                      If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:35












                    • $begingroup$
                      @Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:38










                    • $begingroup$
                      @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:50










                    • $begingroup$
                      @Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:51


















                    1












                    $begingroup$

                    Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$






                    share|cite|improve this answer









                    $endgroup$









                    • 1




                      $begingroup$
                      So does Doets assume that $Sigma$ has a model?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:32










                    • $begingroup$
                      If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:35












                    • $begingroup$
                      @Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:38










                    • $begingroup$
                      @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:50










                    • $begingroup$
                      @Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:51
















                    1












                    1








                    1





                    $begingroup$

                    Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$






                    share|cite|improve this answer









                    $endgroup$



                    Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Dec 8 '18 at 20:17









                    HoloHolo

                    5,73121031




                    5,73121031








                    • 1




                      $begingroup$
                      So does Doets assume that $Sigma$ has a model?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:32










                    • $begingroup$
                      If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:35












                    • $begingroup$
                      @Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:38










                    • $begingroup$
                      @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:50










                    • $begingroup$
                      @Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:51
















                    • 1




                      $begingroup$
                      So does Doets assume that $Sigma$ has a model?
                      $endgroup$
                      – Mike
                      Dec 8 '18 at 20:32










                    • $begingroup$
                      If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:35












                    • $begingroup$
                      @Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:38










                    • $begingroup$
                      @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
                      $endgroup$
                      – Holo
                      Dec 8 '18 at 20:50










                    • $begingroup$
                      @Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
                      $endgroup$
                      – Noah Schweber
                      Dec 8 '18 at 20:51










                    1




                    1




                    $begingroup$
                    So does Doets assume that $Sigma$ has a model?
                    $endgroup$
                    – Mike
                    Dec 8 '18 at 20:32




                    $begingroup$
                    So does Doets assume that $Sigma$ has a model?
                    $endgroup$
                    – Mike
                    Dec 8 '18 at 20:32












                    $begingroup$
                    If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
                    $endgroup$
                    – Holo
                    Dec 8 '18 at 20:35






                    $begingroup$
                    If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
                    $endgroup$
                    – Holo
                    Dec 8 '18 at 20:35














                    $begingroup$
                    @Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:38




                    $begingroup$
                    @Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:38












                    $begingroup$
                    @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
                    $endgroup$
                    – Holo
                    Dec 8 '18 at 20:50




                    $begingroup$
                    @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
                    $endgroup$
                    – Holo
                    Dec 8 '18 at 20:50












                    $begingroup$
                    @Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:51






                    $begingroup$
                    @Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
                    $endgroup$
                    – Noah Schweber
                    Dec 8 '18 at 20:51




















                    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%2f3031577%2fif-sigma-models-phi-then-for-some-finite-delta-subset-sigma-delta%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

                    Aardman Animations

                    Are they similar matrix

                    “minimization” problem in Euclidean space related to orthonormal basis