Statement true because not provable The 2019 Stack Overflow Developer Survey Results Are InModel Theoretical Interpretation of the Incompleteness of Number TheoryIs the negation of the Gödel sentence always unprovable too?Understanding the syntactical completenessExamples of statements which are true but not provableclarify the term “arithmetics” when talking about Gödel's incompleteness theoremsTrue but unprovable?Why can PA + $neg G_PA$ be consistent?Understanding the definition of completeness of formal theorys(and Godel's famous theorem)What's wrong with this “proof” that Gödel's first incompleteness theorem is wrong?Gödel diagonalization and formulas not holding for themselvesFOL and Gödel's Incompleteness Theorem 1

Is there any way to tell whether the shot is going to hit you or not?

Did Section 31 appear in Star Trek: The Next Generation?

Why isn't airport relocation done gradually?

Worn-tile Scrabble

Is bread bad for ducks?

How to save as into a customized destination on macOS?

Right tool to dig six foot holes?

What does ひと匙 mean in this manga and has it been used colloquially?

Where to refill my bottle in India?

Why is my custom API endpoint not working?

"as much details as you can remember"

Why do UK politicians seemingly ignore opinion polls on Brexit?

Shouldn't "much" here be used instead of "more"?

What is the formula behind each level spell slot progression that I can use in a spreadsheet?

Why is the maximum length of OpenWrt’s root password 8 characters?

Identify This Plant (Flower)

Geography at the pixel level

Resizing object distorts it (Illustrator CC 2018)

What is the most effective way of iterating a std::vector and why?

What did it mean to "align" a radio?

Who coined the term "madman theory"?

Why isn't the circumferential light around the M87 black hole's event horizon symmetric?

How to notate time signature switching consistently every measure

How to manage monthly salary



Statement true because not provable



The 2019 Stack Overflow Developer Survey Results Are InModel Theoretical Interpretation of the Incompleteness of Number TheoryIs the negation of the Gödel sentence always unprovable too?Understanding the syntactical completenessExamples of statements which are true but not provableclarify the term “arithmetics” when talking about Gödel's incompleteness theoremsTrue but unprovable?Why can PA + $neg G_PA$ be consistent?Understanding the definition of completeness of formal theorys(and Godel's famous theorem)What's wrong with this “proof” that Gödel's first incompleteness theorem is wrong?Gödel diagonalization and formulas not holding for themselvesFOL and Gödel's Incompleteness Theorem 1










3












$begingroup$


It is my understanding that Gödel's second incompleteness theorem says roughly that




there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).




If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?



Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?



Is this reasoning correct?










share|cite|improve this question









$endgroup$











  • $begingroup$
    I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
    $endgroup$
    – DanielV
    1 hour ago















3












$begingroup$


It is my understanding that Gödel's second incompleteness theorem says roughly that




there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).




If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?



Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?



Is this reasoning correct?










share|cite|improve this question









$endgroup$











  • $begingroup$
    I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
    $endgroup$
    – DanielV
    1 hour ago













3












3








3





$begingroup$


It is my understanding that Gödel's second incompleteness theorem says roughly that




there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).




If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?



Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?



Is this reasoning correct?










share|cite|improve this question









$endgroup$




It is my understanding that Gödel's second incompleteness theorem says roughly that




there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).




If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?



Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?



Is this reasoning correct?







logic incompleteness






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 7 hours ago









Thomas LesgourguesThomas Lesgourgues

1,340220




1,340220











  • $begingroup$
    I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
    $endgroup$
    – DanielV
    1 hour ago
















  • $begingroup$
    I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
    $endgroup$
    – DanielV
    1 hour ago















$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago




$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago










3 Answers
3






active

oldest

votes


















7












$begingroup$

No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.



However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.






share|cite|improve this answer









$endgroup$












  • $begingroup$
    Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
    $endgroup$
    – Thomas Lesgourgues
    5 hours ago










  • $begingroup$
    @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
    $endgroup$
    – spaceisdarkgreen
    1 hour ago










  • $begingroup$
    @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
    $endgroup$
    – spaceisdarkgreen
    1 hour ago


















3












$begingroup$

You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.



Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.






share|cite|improve this answer









$endgroup$




















    2












    $begingroup$

    First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$



    So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.



    Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
      $endgroup$
      – Thomas Lesgourgues
      5 hours ago











    • $begingroup$
      @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
      $endgroup$
      – Bram28
      4 hours ago











    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%2f3182541%2fstatement-true-because-not-provable%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









    7












    $begingroup$

    No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.



    However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.






    share|cite|improve this answer









    $endgroup$












    • $begingroup$
      Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
      $endgroup$
      – Thomas Lesgourgues
      5 hours ago










    • $begingroup$
      @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
      $endgroup$
      – spaceisdarkgreen
      1 hour ago










    • $begingroup$
      @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
      $endgroup$
      – spaceisdarkgreen
      1 hour ago















    7












    $begingroup$

    No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.



    However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.






    share|cite|improve this answer









    $endgroup$












    • $begingroup$
      Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
      $endgroup$
      – Thomas Lesgourgues
      5 hours ago










    • $begingroup$
      @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
      $endgroup$
      – spaceisdarkgreen
      1 hour ago










    • $begingroup$
      @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
      $endgroup$
      – spaceisdarkgreen
      1 hour ago













    7












    7








    7





    $begingroup$

    No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.



    However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.






    share|cite|improve this answer









    $endgroup$



    No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.



    However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 6 hours ago









    TedTed

    22.1k13361




    22.1k13361











    • $begingroup$
      Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
      $endgroup$
      – Thomas Lesgourgues
      5 hours ago










    • $begingroup$
      @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
      $endgroup$
      – spaceisdarkgreen
      1 hour ago










    • $begingroup$
      @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
      $endgroup$
      – spaceisdarkgreen
      1 hour ago
















    • $begingroup$
      Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
      $endgroup$
      – Thomas Lesgourgues
      5 hours ago










    • $begingroup$
      @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
      $endgroup$
      – spaceisdarkgreen
      1 hour ago










    • $begingroup$
      @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
      $endgroup$
      – spaceisdarkgreen
      1 hour ago















    $begingroup$
    Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
    $endgroup$
    – Thomas Lesgourgues
    5 hours ago




    $begingroup$
    Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
    $endgroup$
    – Thomas Lesgourgues
    5 hours ago












    $begingroup$
    @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
    $endgroup$
    – spaceisdarkgreen
    1 hour ago




    $begingroup$
    @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
    $endgroup$
    – spaceisdarkgreen
    1 hour ago












    $begingroup$
    @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
    $endgroup$
    – spaceisdarkgreen
    1 hour ago




    $begingroup$
    @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
    $endgroup$
    – spaceisdarkgreen
    1 hour ago











    3












    $begingroup$

    You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.



    Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.






    share|cite|improve this answer









    $endgroup$

















      3












      $begingroup$

      You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.



      Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.






      share|cite|improve this answer









      $endgroup$















        3












        3








        3





        $begingroup$

        You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.



        Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.






        share|cite|improve this answer









        $endgroup$



        You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.



        Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 6 hours ago









        Floris ClaassensFloris Claassens

        1,47429




        1,47429





















            2












            $begingroup$

            First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$



            So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.



            Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...






            share|cite|improve this answer











            $endgroup$












            • $begingroup$
              Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
              $endgroup$
              – Thomas Lesgourgues
              5 hours ago











            • $begingroup$
              @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
              $endgroup$
              – Bram28
              4 hours ago















            2












            $begingroup$

            First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$



            So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.



            Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...






            share|cite|improve this answer











            $endgroup$












            • $begingroup$
              Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
              $endgroup$
              – Thomas Lesgourgues
              5 hours ago











            • $begingroup$
              @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
              $endgroup$
              – Bram28
              4 hours ago













            2












            2








            2





            $begingroup$

            First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$



            So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.



            Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...






            share|cite|improve this answer











            $endgroup$



            First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$



            So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.



            Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited 7 mins ago

























            answered 5 hours ago









            Bram28Bram28

            64.3k44793




            64.3k44793











            • $begingroup$
              Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
              $endgroup$
              – Thomas Lesgourgues
              5 hours ago











            • $begingroup$
              @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
              $endgroup$
              – Bram28
              4 hours ago
















            • $begingroup$
              Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
              $endgroup$
              – Thomas Lesgourgues
              5 hours ago











            • $begingroup$
              @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
              $endgroup$
              – Bram28
              4 hours ago















            $begingroup$
            Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
            $endgroup$
            – Thomas Lesgourgues
            5 hours ago





            $begingroup$
            Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
            $endgroup$
            – Thomas Lesgourgues
            5 hours ago













            $begingroup$
            @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
            $endgroup$
            – Bram28
            4 hours ago




            $begingroup$
            @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
            $endgroup$
            – Bram28
            4 hours ago

















            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%2f3182541%2fstatement-true-because-not-provable%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

            Are there any AGPL-style licences that require source code modifications to be public? Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Force derivative works to be publicAre there any GPL like licenses for Apple App Store?Do you violate the GPL if you provide source code that cannot be compiled?GPL - is it distribution to use libraries in an appliance loaned to customers?Distributing App for free which uses GPL'ed codeModifications of server software under GPL, with web/CLI interfaceDoes using an AGPLv3-licensed library prevent me from dual-licensing my own source code?Can I publish only select code under GPLv3 from a private project?Is there published precedent regarding the scope of covered work that uses AGPL software?If MIT licensed code links to GPL licensed code what should be the license of the resulting binary program?If I use a public API endpoint that has its source code licensed under AGPL in my app, do I need to disclose my source?

            2013 GY136 Descoberta | Órbita | Referências Menu de navegação«List Of Centaurs and Scattered-Disk Objects»«List of Known Trans-Neptunian Objects»

            Button changing it's text & action. Good or terrible? The 2019 Stack Overflow Developer Survey Results Are Inchanging text on user mouseoverShould certain functions be “hard to find” for powerusers to discover?Custom liking function - do I need user login?Using different checkbox style for different checkbox behaviorBest Practices: Save and Exit in Software UIInteraction with remote validated formMore efficient UI to progress the user through a complicated process?Designing a popup notice for a gameShould bulk-editing functions be hidden until a table row is selected, or is there a better solution?Is it bad practice to disable (replace) the context menu?