A (quantifier-free) is true in standard model of PA ==> PA |- A ??












0












$begingroup$


Is the following statement correct ?



A is a formula in PA without a quantifier and
A is true for the standard model of arithmetic, i.e. the model
|N = (N,+,×,0,1,<)
This means: |N |= A



==>



A is proofable in PA. This means:
PA |- A



Example:
|N |= (x+y)^2 =x^2 + 2xy + y^2
===>
PA |- (x+y)^2 =x^2 + 2xy + y^2



If this statement is wrong, please give me a counterexample



cu
cx










share|cite|improve this question









$endgroup$

















    0












    $begingroup$


    Is the following statement correct ?



    A is a formula in PA without a quantifier and
    A is true for the standard model of arithmetic, i.e. the model
    |N = (N,+,×,0,1,<)
    This means: |N |= A



    ==>



    A is proofable in PA. This means:
    PA |- A



    Example:
    |N |= (x+y)^2 =x^2 + 2xy + y^2
    ===>
    PA |- (x+y)^2 =x^2 + 2xy + y^2



    If this statement is wrong, please give me a counterexample



    cu
    cx










    share|cite|improve this question









    $endgroup$















      0












      0








      0





      $begingroup$


      Is the following statement correct ?



      A is a formula in PA without a quantifier and
      A is true for the standard model of arithmetic, i.e. the model
      |N = (N,+,×,0,1,<)
      This means: |N |= A



      ==>



      A is proofable in PA. This means:
      PA |- A



      Example:
      |N |= (x+y)^2 =x^2 + 2xy + y^2
      ===>
      PA |- (x+y)^2 =x^2 + 2xy + y^2



      If this statement is wrong, please give me a counterexample



      cu
      cx










      share|cite|improve this question









      $endgroup$




      Is the following statement correct ?



      A is a formula in PA without a quantifier and
      A is true for the standard model of arithmetic, i.e. the model
      |N = (N,+,×,0,1,<)
      This means: |N |= A



      ==>



      A is proofable in PA. This means:
      PA |- A



      Example:
      |N |= (x+y)^2 =x^2 + 2xy + y^2
      ===>
      PA |- (x+y)^2 =x^2 + 2xy + y^2



      If this statement is wrong, please give me a counterexample



      cu
      cx







      peano-axioms






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Jan 29 at 15:27









      user508589user508589

      12




      12






















          2 Answers
          2






          active

          oldest

          votes


















          1












          $begingroup$

          EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$



          Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.





          What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.



          Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.



          So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
            $endgroup$
            – user508589
            Jan 29 at 21:29












          • $begingroup$
            @user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
            $endgroup$
            – Noah Schweber
            Jan 29 at 22:35



















          -1












          $begingroup$

          $$
          text{You gave a counterexample: true in N but not PA-provable.} \
          text{But there are so many examples with: true in N and PA-provable: } \
          text{I define: } \
          text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
          bar 0 ; and ; bar 1 text{ are the constants from PA} \
          oplus and circ text{ are the functions in PA} \
          text{when z is element from I_N, I define:} \
          bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
          text{I proofed the following statement "S1"} \
          text{When n is element from I_N then we have:} \
          PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
          bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
          text{I assume, that there are "many" of "similar" statements like S1.} \
          text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
          $$



          cu
          cx






          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%2f3092309%2fa-quantifier-free-is-true-in-standard-model-of-pa-pa-a%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









            1












            $begingroup$

            EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$



            Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.





            What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.



            Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.



            So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
              $endgroup$
              – user508589
              Jan 29 at 21:29












            • $begingroup$
              @user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
              $endgroup$
              – Noah Schweber
              Jan 29 at 22:35
















            1












            $begingroup$

            EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$



            Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.





            What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.



            Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.



            So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
              $endgroup$
              – user508589
              Jan 29 at 21:29












            • $begingroup$
              @user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
              $endgroup$
              – Noah Schweber
              Jan 29 at 22:35














            1












            1








            1





            $begingroup$

            EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$



            Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.





            What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.



            Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.



            So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.






            share|cite|improve this answer











            $endgroup$



            EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$



            Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.





            What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.



            Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.



            So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Jan 29 at 22:56

























            answered Jan 29 at 16:02









            Noah SchweberNoah Schweber

            128k10151294




            128k10151294












            • $begingroup$
              Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
              $endgroup$
              – user508589
              Jan 29 at 21:29












            • $begingroup$
              @user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
              $endgroup$
              – Noah Schweber
              Jan 29 at 22:35


















            • $begingroup$
              Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
              $endgroup$
              – user508589
              Jan 29 at 21:29












            • $begingroup$
              @user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
              $endgroup$
              – Noah Schweber
              Jan 29 at 22:35
















            $begingroup$
            Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
            $endgroup$
            – user508589
            Jan 29 at 21:29






            $begingroup$
            Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
            $endgroup$
            – user508589
            Jan 29 at 21:29














            $begingroup$
            @user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
            $endgroup$
            – Noah Schweber
            Jan 29 at 22:35




            $begingroup$
            @user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
            $endgroup$
            – Noah Schweber
            Jan 29 at 22:35











            -1












            $begingroup$

            $$
            text{You gave a counterexample: true in N but not PA-provable.} \
            text{But there are so many examples with: true in N and PA-provable: } \
            text{I define: } \
            text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
            bar 0 ; and ; bar 1 text{ are the constants from PA} \
            oplus and circ text{ are the functions in PA} \
            text{when z is element from I_N, I define:} \
            bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
            text{I proofed the following statement "S1"} \
            text{When n is element from I_N then we have:} \
            PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
            bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
            text{I assume, that there are "many" of "similar" statements like S1.} \
            text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
            $$



            cu
            cx






            share|cite|improve this answer











            $endgroup$


















              -1












              $begingroup$

              $$
              text{You gave a counterexample: true in N but not PA-provable.} \
              text{But there are so many examples with: true in N and PA-provable: } \
              text{I define: } \
              text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
              bar 0 ; and ; bar 1 text{ are the constants from PA} \
              oplus and circ text{ are the functions in PA} \
              text{when z is element from I_N, I define:} \
              bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
              text{I proofed the following statement "S1"} \
              text{When n is element from I_N then we have:} \
              PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
              bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
              text{I assume, that there are "many" of "similar" statements like S1.} \
              text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
              $$



              cu
              cx






              share|cite|improve this answer











              $endgroup$
















                -1












                -1








                -1





                $begingroup$

                $$
                text{You gave a counterexample: true in N but not PA-provable.} \
                text{But there are so many examples with: true in N and PA-provable: } \
                text{I define: } \
                text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
                bar 0 ; and ; bar 1 text{ are the constants from PA} \
                oplus and circ text{ are the functions in PA} \
                text{when z is element from I_N, I define:} \
                bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
                text{I proofed the following statement "S1"} \
                text{When n is element from I_N then we have:} \
                PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
                bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
                text{I assume, that there are "many" of "similar" statements like S1.} \
                text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
                $$



                cu
                cx






                share|cite|improve this answer











                $endgroup$



                $$
                text{You gave a counterexample: true in N but not PA-provable.} \
                text{But there are so many examples with: true in N and PA-provable: } \
                text{I define: } \
                text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
                bar 0 ; and ; bar 1 text{ are the constants from PA} \
                oplus and circ text{ are the functions in PA} \
                text{when z is element from I_N, I define:} \
                bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
                text{I proofed the following statement "S1"} \
                text{When n is element from I_N then we have:} \
                PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
                bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
                text{I assume, that there are "many" of "similar" statements like S1.} \
                text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
                $$



                cu
                cx







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Feb 4 at 9:09

























                answered Feb 3 at 9:42









                user508589user508589

                12




                12






























                    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%2f3092309%2fa-quantifier-free-is-true-in-standard-model-of-pa-pa-a%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