Proof that there exist no finite axiomatic system with Compactness Theorem












4












$begingroup$


Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).



Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.



This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.



The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?










share|cite|improve this question











$endgroup$

















    4












    $begingroup$


    Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).



    Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.



    This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.



    The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?










    share|cite|improve this question











    $endgroup$















      4












      4








      4





      $begingroup$


      Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).



      Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.



      This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.



      The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?










      share|cite|improve this question











      $endgroup$




      Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).



      Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.



      This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.



      The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?







      logic first-order-logic predicate-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 21:06









      Taroccoesbrocco

      5,64271840




      5,64271840










      asked Aug 12 '14 at 11:46









      mercurialmercurial

      5862815




      5862815






















          2 Answers
          2






          active

          oldest

          votes


















          3












          $begingroup$

          There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
          $psi$ is the sentence
          $$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
          The sentence $lnot psi$ is then the sentence
          $$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
          This is a disjunction. No group property needs to fail.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Ah yea true that didn't occur to me! Thanks!
            $endgroup$
            – mercurial
            Aug 12 '14 at 12:25










          • $begingroup$
            You are welcome. It is natural to think that a group-theoretic axiom is being negated.
            $endgroup$
            – André Nicolas
            Aug 12 '14 at 13:13



















          2












          $begingroup$

          The following may be a more intuitive proof:



          Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.



          If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.






          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%2f895021%2fproof-that-there-exist-no-finite-axiomatic-system-with-compactness-theorem%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            3












            $begingroup$

            There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
            $psi$ is the sentence
            $$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
            The sentence $lnot psi$ is then the sentence
            $$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
            This is a disjunction. No group property needs to fail.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Ah yea true that didn't occur to me! Thanks!
              $endgroup$
              – mercurial
              Aug 12 '14 at 12:25










            • $begingroup$
              You are welcome. It is natural to think that a group-theoretic axiom is being negated.
              $endgroup$
              – André Nicolas
              Aug 12 '14 at 13:13
















            3












            $begingroup$

            There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
            $psi$ is the sentence
            $$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
            The sentence $lnot psi$ is then the sentence
            $$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
            This is a disjunction. No group property needs to fail.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Ah yea true that didn't occur to me! Thanks!
              $endgroup$
              – mercurial
              Aug 12 '14 at 12:25










            • $begingroup$
              You are welcome. It is natural to think that a group-theoretic axiom is being negated.
              $endgroup$
              – André Nicolas
              Aug 12 '14 at 13:13














            3












            3








            3





            $begingroup$

            There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
            $psi$ is the sentence
            $$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
            The sentence $lnot psi$ is then the sentence
            $$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
            This is a disjunction. No group property needs to fail.






            share|cite|improve this answer









            $endgroup$



            There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
            $psi$ is the sentence
            $$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
            The sentence $lnot psi$ is then the sentence
            $$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
            This is a disjunction. No group property needs to fail.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Aug 12 '14 at 12:02









            André NicolasAndré Nicolas

            454k36432819




            454k36432819












            • $begingroup$
              Ah yea true that didn't occur to me! Thanks!
              $endgroup$
              – mercurial
              Aug 12 '14 at 12:25










            • $begingroup$
              You are welcome. It is natural to think that a group-theoretic axiom is being negated.
              $endgroup$
              – André Nicolas
              Aug 12 '14 at 13:13


















            • $begingroup$
              Ah yea true that didn't occur to me! Thanks!
              $endgroup$
              – mercurial
              Aug 12 '14 at 12:25










            • $begingroup$
              You are welcome. It is natural to think that a group-theoretic axiom is being negated.
              $endgroup$
              – André Nicolas
              Aug 12 '14 at 13:13
















            $begingroup$
            Ah yea true that didn't occur to me! Thanks!
            $endgroup$
            – mercurial
            Aug 12 '14 at 12:25




            $begingroup$
            Ah yea true that didn't occur to me! Thanks!
            $endgroup$
            – mercurial
            Aug 12 '14 at 12:25












            $begingroup$
            You are welcome. It is natural to think that a group-theoretic axiom is being negated.
            $endgroup$
            – André Nicolas
            Aug 12 '14 at 13:13




            $begingroup$
            You are welcome. It is natural to think that a group-theoretic axiom is being negated.
            $endgroup$
            – André Nicolas
            Aug 12 '14 at 13:13











            2












            $begingroup$

            The following may be a more intuitive proof:



            Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.



            If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.






            share|cite|improve this answer











            $endgroup$


















              2












              $begingroup$

              The following may be a more intuitive proof:



              Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.



              If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.






              share|cite|improve this answer











              $endgroup$
















                2












                2








                2





                $begingroup$

                The following may be a more intuitive proof:



                Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.



                If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.






                share|cite|improve this answer











                $endgroup$



                The following may be a more intuitive proof:



                Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.



                If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Aug 12 '14 at 12:17

























                answered Aug 12 '14 at 12:08









                WilliamWilliam

                17.3k22256




                17.3k22256






























                    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%2f895021%2fproof-that-there-exist-no-finite-axiomatic-system-with-compactness-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

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

                    How to fix TextFormField cause rebuild widget in Flutter