Is Peano arithmetic complete for quantifier free formulas and strict arithmetical formulas?












1












$begingroup$


By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.



By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.



Is PA complete for quantifier free arithmetical sentences?




Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?




Is PA complete for strict arithmetical sentences?




Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?











share|cite|improve this question









$endgroup$

















    1












    $begingroup$


    By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.



    By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.



    Is PA complete for quantifier free arithmetical sentences?




    Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?




    Is PA complete for strict arithmetical sentences?




    Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?











    share|cite|improve this question









    $endgroup$















      1












      1








      1





      $begingroup$


      By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.



      By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.



      Is PA complete for quantifier free arithmetical sentences?




      Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?




      Is PA complete for strict arithmetical sentences?




      Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?











      share|cite|improve this question









      $endgroup$




      By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.



      By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.



      Is PA complete for quantifier free arithmetical sentences?




      Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?




      Is PA complete for strict arithmetical sentences?




      Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?








      peano-axioms






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 7 '18 at 9:34









      ZuhairZuhair

      248111




      248111






















          1 Answer
          1






          active

          oldest

          votes


















          2












          $begingroup$

          First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.



          As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.



          (A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)



          If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 14:57












          • $begingroup$
            @AndreasBlass That also needs subtraction I think.
            $endgroup$
            – Noah Schweber
            Dec 7 '18 at 15:00










          • $begingroup$
            There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:06










          • $begingroup$
            To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:08











          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%2f3029696%2fis-peano-arithmetic-complete-for-quantifier-free-formulas-and-strict-arithmetica%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          2












          $begingroup$

          First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.



          As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.



          (A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)



          If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 14:57












          • $begingroup$
            @AndreasBlass That also needs subtraction I think.
            $endgroup$
            – Noah Schweber
            Dec 7 '18 at 15:00










          • $begingroup$
            There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:06










          • $begingroup$
            To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:08
















          2












          $begingroup$

          First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.



          As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.



          (A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)



          If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 14:57












          • $begingroup$
            @AndreasBlass That also needs subtraction I think.
            $endgroup$
            – Noah Schweber
            Dec 7 '18 at 15:00










          • $begingroup$
            There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:06










          • $begingroup$
            To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:08














          2












          2








          2





          $begingroup$

          First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.



          As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.



          (A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)



          If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.






          share|cite|improve this answer











          $endgroup$



          First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.



          As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.



          (A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)



          If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 7 '18 at 15:05

























          answered Dec 7 '18 at 13:31









          Noah SchweberNoah Schweber

          122k10149284




          122k10149284












          • $begingroup$
            This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 14:57












          • $begingroup$
            @AndreasBlass That also needs subtraction I think.
            $endgroup$
            – Noah Schweber
            Dec 7 '18 at 15:00










          • $begingroup$
            There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:06










          • $begingroup$
            To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:08


















          • $begingroup$
            This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 14:57












          • $begingroup$
            @AndreasBlass That also needs subtraction I think.
            $endgroup$
            – Noah Schweber
            Dec 7 '18 at 15:00










          • $begingroup$
            There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:06










          • $begingroup$
            To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
            $endgroup$
            – Andreas Blass
            Dec 7 '18 at 15:08
















          $begingroup$
          This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
          $endgroup$
          – Andreas Blass
          Dec 7 '18 at 14:57






          $begingroup$
          This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
          $endgroup$
          – Andreas Blass
          Dec 7 '18 at 14:57














          $begingroup$
          @AndreasBlass That also needs subtraction I think.
          $endgroup$
          – Noah Schweber
          Dec 7 '18 at 15:00




          $begingroup$
          @AndreasBlass That also needs subtraction I think.
          $endgroup$
          – Noah Schweber
          Dec 7 '18 at 15:00












          $begingroup$
          There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
          $endgroup$
          – Andreas Blass
          Dec 7 '18 at 15:06




          $begingroup$
          There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
          $endgroup$
          – Andreas Blass
          Dec 7 '18 at 15:06












          $begingroup$
          To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
          $endgroup$
          – Andreas Blass
          Dec 7 '18 at 15:08




          $begingroup$
          To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
          $endgroup$
          – Andreas Blass
          Dec 7 '18 at 15:08


















          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%2f3029696%2fis-peano-arithmetic-complete-for-quantifier-free-formulas-and-strict-arithmetica%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

          Berounka

          Sphinx de Gizeh

          Different font size/position of beamer's navigation symbols template's content depending on regular/plain...