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»

            Mortes em março de 2019 Referências Menu de navegação«Zhores Alferov, Nobel de Física bielorrusso, morre aos 88 anos - Ciência»«Fallece Rafael Torija, o bispo emérito de Ciudad Real»«Peter Hurford dies at 88»«Keith Flint, vocalista do The Prodigy, morre aos 49 anos»«Luke Perry, ator de 'Barrados no baile' e 'Riverdale', morre aos 52 anos»«Former Rangers and Scotland captain Eric Caldow dies, aged 84»«Morreu, aos 61 anos, a antiga lenda do wrestling King Kong Bundy»«Fallece el actor y director teatral Abraham Stavans»«In Memoriam Guillaume Faye»«Sidney Sheinberg, a Force Behind Universal and Spielberg, Is Dead at 84»«Carmine Persico, Colombo Crime Family Boss, Is Dead at 85»«Dirigent Michael Gielen gestorben»«Ciclista tricampeã mundial e prata na Rio 2016 é encontrada morta em casa aos 23 anos»«Pagan Community Notes: Raven Grimassi dies, Indianapolis pop-up event cancelled, Circle Sanctuary announces new podcast, and more!»«Hal Blaine, Wrecking Crew Drummer, Dies at 90»«Morre Coutinho, que editou dupla lendária com Pelé no Santos»«Cantor Demétrius, ídolo da Jovem Guarda, morre em SP»«Ex-presidente do Vasco, Eurico Miranda morre no Rio de Janeiro»«Bronze no Mundial de basquete de 1971, Laís Elena morre aos 76 anos»«Diretor de Corridas da F1, Charlie Whiting morre aos 66 anos às vésperas do GP da Austrália»«Morreu o cardeal Danneels, da Bélgica»«Morreu o cartoonista Augusto Cid»«Morreu a atriz Maria Isabel de Lizandra, de "Vale Tudo" e novelas da Tupi»«WS Merwin, prize-winning poet of nature, dies at 91»«Atriz Márcia Real morre em São Paulo aos 88 anos»«Mauritanie: décès de l'ancien président Mohamed Mahmoud ould Louly»«Morreu Dick Dale, o rei da surf guitar e de "Pulp Fiction"»«Falleció Víctor Genes»«João Carlos Marinho, autor de 'O Gênio do Crime', morre em SP»«Legendary Horror Director and SFX Artist John Carl Buechler Dies at 66»«Morre em Salvador a religiosa Makota Valdina»«مرگ بازیکن‌ سابق نساجی بر اثر سقوط سنگ در مازندران»«Domingos Oliveira morre no Rio»«Morre Airton Ravagniani, ex-São Paulo, Fla, Vasco, Grêmio e Sport - Notícias»«Morre o escritor Flavio Moreira da Costa»«Larry Cohen, Writer-Director of 'It's Alive' and 'Hell Up in Harlem,' Dies at 77»«Scott Walker, experimental singer-songwriter, dead at 76»«Joseph Pilato, Day of the Dead Star and Horror Favorite, Dies at 70»«Sheffield United set to pay tribute to legendary goalkeeper Ted Burgin who has died at 91»«Morre Rafael Henzel, sobrevivente de acidente aéreo da Chapecoense»«Morre Valery Bykovsky, um dos primeiros cosmonautas da União Soviética»«Agnès Varda, cineasta da Nouvelle Vague, morre aos 90 anos»«Agnès Varda, cineasta francesa, morre aos 90 anos»«Tania Mallet, James Bond Actress and Helen Mirren's Cousin, Dies at 77»e