Why doesn't Gödel's incompleteness theorem apply to false statements?












9












$begingroup$


I've read and heard in lectures that




A way to prove that the Riemann hypothesis is true is to show that its negation is not provable.




The argument (informally) usually goes like




If a statement is false, then there must exist a counterexample showing its falsity.




Hence, to prove any statement is false, one must have a constructive proof.



Question: Why doesn't Godel's incompleteness theorem apply to false statements? That is, how do we know that all false statements are provably so?










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    This question seems to be based on an incorrect assumption. We have nonconstructive proofs of falsity all the time. For example "There exists a bijection between the reals and the natural" has a rather famously nonconstructive proof.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Do you have a reference for this "proof" ?
    $endgroup$
    – DanielV
    2 days ago






  • 1




    $begingroup$
    Sorry I should have said “Has a famous proof of it’s falsity”.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Cantor's proof is constructive. It explicitly builds the real number that's not in the bijection using pieces from the previous rows in the hypothetical bijection.
    $endgroup$
    – Tomislav Ostojich
    2 days ago








  • 2




    $begingroup$
    See also math.stackexchange.com/questions/2305177/…
    $endgroup$
    – Asaf Karagila
    2 days ago
















9












$begingroup$


I've read and heard in lectures that




A way to prove that the Riemann hypothesis is true is to show that its negation is not provable.




The argument (informally) usually goes like




If a statement is false, then there must exist a counterexample showing its falsity.




Hence, to prove any statement is false, one must have a constructive proof.



Question: Why doesn't Godel's incompleteness theorem apply to false statements? That is, how do we know that all false statements are provably so?










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    This question seems to be based on an incorrect assumption. We have nonconstructive proofs of falsity all the time. For example "There exists a bijection between the reals and the natural" has a rather famously nonconstructive proof.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Do you have a reference for this "proof" ?
    $endgroup$
    – DanielV
    2 days ago






  • 1




    $begingroup$
    Sorry I should have said “Has a famous proof of it’s falsity”.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Cantor's proof is constructive. It explicitly builds the real number that's not in the bijection using pieces from the previous rows in the hypothetical bijection.
    $endgroup$
    – Tomislav Ostojich
    2 days ago








  • 2




    $begingroup$
    See also math.stackexchange.com/questions/2305177/…
    $endgroup$
    – Asaf Karagila
    2 days ago














9












9








9


7



$begingroup$


I've read and heard in lectures that




A way to prove that the Riemann hypothesis is true is to show that its negation is not provable.




The argument (informally) usually goes like




If a statement is false, then there must exist a counterexample showing its falsity.




Hence, to prove any statement is false, one must have a constructive proof.



Question: Why doesn't Godel's incompleteness theorem apply to false statements? That is, how do we know that all false statements are provably so?










share|cite|improve this question











$endgroup$




I've read and heard in lectures that




A way to prove that the Riemann hypothesis is true is to show that its negation is not provable.




The argument (informally) usually goes like




If a statement is false, then there must exist a counterexample showing its falsity.




Hence, to prove any statement is false, one must have a constructive proof.



Question: Why doesn't Godel's incompleteness theorem apply to false statements? That is, how do we know that all false statements are provably so?







logic incompleteness






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited yesterday









Jens Renders

2,0211225




2,0211225










asked 2 days ago









InertialObserverInertialObserver

440312




440312








  • 2




    $begingroup$
    This question seems to be based on an incorrect assumption. We have nonconstructive proofs of falsity all the time. For example "There exists a bijection between the reals and the natural" has a rather famously nonconstructive proof.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Do you have a reference for this "proof" ?
    $endgroup$
    – DanielV
    2 days ago






  • 1




    $begingroup$
    Sorry I should have said “Has a famous proof of it’s falsity”.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Cantor's proof is constructive. It explicitly builds the real number that's not in the bijection using pieces from the previous rows in the hypothetical bijection.
    $endgroup$
    – Tomislav Ostojich
    2 days ago








  • 2




    $begingroup$
    See also math.stackexchange.com/questions/2305177/…
    $endgroup$
    – Asaf Karagila
    2 days ago














  • 2




    $begingroup$
    This question seems to be based on an incorrect assumption. We have nonconstructive proofs of falsity all the time. For example "There exists a bijection between the reals and the natural" has a rather famously nonconstructive proof.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Do you have a reference for this "proof" ?
    $endgroup$
    – DanielV
    2 days ago






  • 1




    $begingroup$
    Sorry I should have said “Has a famous proof of it’s falsity”.
    $endgroup$
    – Q the Platypus
    2 days ago






  • 1




    $begingroup$
    @QthePlatypus Cantor's proof is constructive. It explicitly builds the real number that's not in the bijection using pieces from the previous rows in the hypothetical bijection.
    $endgroup$
    – Tomislav Ostojich
    2 days ago








  • 2




    $begingroup$
    See also math.stackexchange.com/questions/2305177/…
    $endgroup$
    – Asaf Karagila
    2 days ago








2




2




$begingroup$
This question seems to be based on an incorrect assumption. We have nonconstructive proofs of falsity all the time. For example "There exists a bijection between the reals and the natural" has a rather famously nonconstructive proof.
$endgroup$
– Q the Platypus
2 days ago




$begingroup$
This question seems to be based on an incorrect assumption. We have nonconstructive proofs of falsity all the time. For example "There exists a bijection between the reals and the natural" has a rather famously nonconstructive proof.
$endgroup$
– Q the Platypus
2 days ago




1




1




$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
2 days ago




$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
2 days ago




1




1




$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
2 days ago




$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
2 days ago




1




1




$begingroup$
@QthePlatypus Cantor's proof is constructive. It explicitly builds the real number that's not in the bijection using pieces from the previous rows in the hypothetical bijection.
$endgroup$
– Tomislav Ostojich
2 days ago






$begingroup$
@QthePlatypus Cantor's proof is constructive. It explicitly builds the real number that's not in the bijection using pieces from the previous rows in the hypothetical bijection.
$endgroup$
– Tomislav Ostojich
2 days ago






2




2




$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila
2 days ago




$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila
2 days ago










3 Answers
3






active

oldest

votes


















24












$begingroup$


That is, how do we know that all false statements are provably so?




This is simply wrong. There are both true and false statements that cannot be proven. What is true is that any sufficiently nice foundational system (i.e. one that has a proof verifier program and can reason about finite program runs) is $Σ_1$-complete, meaning that it proves every true $Σ_1$-sentence. Here, a $Σ_1$-sentence is an arithmetical sentence (i.e. quantifies only over $mathbb{N}$) that is equivalent to $∃k∈mathbb{N} ( Q(k) )$ for some arithmetical property $Q$ that uses only bounded quantifiers. For example, "There is an even number that is not the sum of two primes." can be expressed as a $Σ_1$-sentence. The "$Σ_1$" stands for "$1$ unbounded existential". Similarly a $Π_1$-sentence is an arithmetical sentence equivalent to one with only $1$ unbounded universal quantifier in Skolem normal form.



In general, if you have a $Π_1$-sentence $C ≡ ∀k∈mathbb{N} ( Q(k) )$, then $¬C$ is a $Σ_1$-sentence. Thus if $C$ is false, $¬C$ is true and hence provable in any sufficiently nice foundational system by $Σ_1$-completeness. This does not apply to all false sentences!



It turns out that non-trivially RH (Riemann Hypothesis) is equivalent to a $Π_1$-sentence, and hence by the above we know that if it is false then even PA (Peano Arithmetic) can disprove it. Also, I should add that no expert believes that it would be any easier to prove unprovability of RH over PA than to directly disprove RH, even if it is false in the first place.



Godel's incompleteness theorem has completely nothing to do with $Σ_1$-completeness. In fact, the generalized incompleteness theorem shows that any sufficiently nice foundational system (regardless of what underlying logic it uses) necessarily is either $Π_1$-incomplete or proves $0=1$. That is, if it is arithmetically consistent (i.e. does not prove $0=1$) then it also does not prove some true $Π_1$-sentence. Moreover, we can find such a sentence uniformly and explicitly (as described in the linked post).






share|cite|improve this answer









$endgroup$









  • 3




    $begingroup$
    Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?"
    $endgroup$
    – MartianInvader
    2 days ago










  • $begingroup$
    @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it.
    $endgroup$
    – user21820
    yesterday










  • $begingroup$
    Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality.
    $endgroup$
    – user21820
    yesterday





















9












$begingroup$

This argument doesn't show that all false statements are provably so. (That's impossible for trivial reasons: if $P$ is a true statement that's not provable, then $lnot P$ is a false statement that's not provable.) The argument shows that the Riemann hypothesis, if false, is provably so, because there would be a specific number $s$ (in the critical strip but not on the critical line) at which $zeta(s)=0$, and so there would exist a proof (show that that specific number is a zero of $zeta$).






share|cite|improve this answer









$endgroup$









  • 7




    $begingroup$
    Note that your final claim is not obvious--even if some number is a zero of $zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove.
    $endgroup$
    – Eric Wofsey
    2 days ago










  • $begingroup$
    @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
    $endgroup$
    – Greg Martin
    2 days ago










  • $begingroup$
    "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean?
    $endgroup$
    – Arthur
    2 days ago










  • $begingroup$
    @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system.
    $endgroup$
    – user21820
    2 days ago






  • 1




    $begingroup$
    @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational.
    $endgroup$
    – ruakh
    yesterday





















5












$begingroup$

Because if you were lucky enough to guess the counterexample, you could just check it. Note that this only works for problems where it's easy to check whether a given value is in fact a counterexample. To take a non-mathematical example, you have no hope of proving you've found a counterexample to "all people are mortal" because you'd have to verify some individual is immortal, meaning you'd have to verify nothing at all can kill them, which isn't possible.






share|cite|improve this answer









$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3153739%2fwhy-doesnt-g%25c3%25b6dels-incompleteness-theorem-apply-to-false-statements%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









    24












    $begingroup$


    That is, how do we know that all false statements are provably so?




    This is simply wrong. There are both true and false statements that cannot be proven. What is true is that any sufficiently nice foundational system (i.e. one that has a proof verifier program and can reason about finite program runs) is $Σ_1$-complete, meaning that it proves every true $Σ_1$-sentence. Here, a $Σ_1$-sentence is an arithmetical sentence (i.e. quantifies only over $mathbb{N}$) that is equivalent to $∃k∈mathbb{N} ( Q(k) )$ for some arithmetical property $Q$ that uses only bounded quantifiers. For example, "There is an even number that is not the sum of two primes." can be expressed as a $Σ_1$-sentence. The "$Σ_1$" stands for "$1$ unbounded existential". Similarly a $Π_1$-sentence is an arithmetical sentence equivalent to one with only $1$ unbounded universal quantifier in Skolem normal form.



    In general, if you have a $Π_1$-sentence $C ≡ ∀k∈mathbb{N} ( Q(k) )$, then $¬C$ is a $Σ_1$-sentence. Thus if $C$ is false, $¬C$ is true and hence provable in any sufficiently nice foundational system by $Σ_1$-completeness. This does not apply to all false sentences!



    It turns out that non-trivially RH (Riemann Hypothesis) is equivalent to a $Π_1$-sentence, and hence by the above we know that if it is false then even PA (Peano Arithmetic) can disprove it. Also, I should add that no expert believes that it would be any easier to prove unprovability of RH over PA than to directly disprove RH, even if it is false in the first place.



    Godel's incompleteness theorem has completely nothing to do with $Σ_1$-completeness. In fact, the generalized incompleteness theorem shows that any sufficiently nice foundational system (regardless of what underlying logic it uses) necessarily is either $Π_1$-incomplete or proves $0=1$. That is, if it is arithmetically consistent (i.e. does not prove $0=1$) then it also does not prove some true $Π_1$-sentence. Moreover, we can find such a sentence uniformly and explicitly (as described in the linked post).






    share|cite|improve this answer









    $endgroup$









    • 3




      $begingroup$
      Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?"
      $endgroup$
      – MartianInvader
      2 days ago










    • $begingroup$
      @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it.
      $endgroup$
      – user21820
      yesterday










    • $begingroup$
      Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality.
      $endgroup$
      – user21820
      yesterday


















    24












    $begingroup$


    That is, how do we know that all false statements are provably so?




    This is simply wrong. There are both true and false statements that cannot be proven. What is true is that any sufficiently nice foundational system (i.e. one that has a proof verifier program and can reason about finite program runs) is $Σ_1$-complete, meaning that it proves every true $Σ_1$-sentence. Here, a $Σ_1$-sentence is an arithmetical sentence (i.e. quantifies only over $mathbb{N}$) that is equivalent to $∃k∈mathbb{N} ( Q(k) )$ for some arithmetical property $Q$ that uses only bounded quantifiers. For example, "There is an even number that is not the sum of two primes." can be expressed as a $Σ_1$-sentence. The "$Σ_1$" stands for "$1$ unbounded existential". Similarly a $Π_1$-sentence is an arithmetical sentence equivalent to one with only $1$ unbounded universal quantifier in Skolem normal form.



    In general, if you have a $Π_1$-sentence $C ≡ ∀k∈mathbb{N} ( Q(k) )$, then $¬C$ is a $Σ_1$-sentence. Thus if $C$ is false, $¬C$ is true and hence provable in any sufficiently nice foundational system by $Σ_1$-completeness. This does not apply to all false sentences!



    It turns out that non-trivially RH (Riemann Hypothesis) is equivalent to a $Π_1$-sentence, and hence by the above we know that if it is false then even PA (Peano Arithmetic) can disprove it. Also, I should add that no expert believes that it would be any easier to prove unprovability of RH over PA than to directly disprove RH, even if it is false in the first place.



    Godel's incompleteness theorem has completely nothing to do with $Σ_1$-completeness. In fact, the generalized incompleteness theorem shows that any sufficiently nice foundational system (regardless of what underlying logic it uses) necessarily is either $Π_1$-incomplete or proves $0=1$. That is, if it is arithmetically consistent (i.e. does not prove $0=1$) then it also does not prove some true $Π_1$-sentence. Moreover, we can find such a sentence uniformly and explicitly (as described in the linked post).






    share|cite|improve this answer









    $endgroup$









    • 3




      $begingroup$
      Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?"
      $endgroup$
      – MartianInvader
      2 days ago










    • $begingroup$
      @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it.
      $endgroup$
      – user21820
      yesterday










    • $begingroup$
      Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality.
      $endgroup$
      – user21820
      yesterday
















    24












    24








    24





    $begingroup$


    That is, how do we know that all false statements are provably so?




    This is simply wrong. There are both true and false statements that cannot be proven. What is true is that any sufficiently nice foundational system (i.e. one that has a proof verifier program and can reason about finite program runs) is $Σ_1$-complete, meaning that it proves every true $Σ_1$-sentence. Here, a $Σ_1$-sentence is an arithmetical sentence (i.e. quantifies only over $mathbb{N}$) that is equivalent to $∃k∈mathbb{N} ( Q(k) )$ for some arithmetical property $Q$ that uses only bounded quantifiers. For example, "There is an even number that is not the sum of two primes." can be expressed as a $Σ_1$-sentence. The "$Σ_1$" stands for "$1$ unbounded existential". Similarly a $Π_1$-sentence is an arithmetical sentence equivalent to one with only $1$ unbounded universal quantifier in Skolem normal form.



    In general, if you have a $Π_1$-sentence $C ≡ ∀k∈mathbb{N} ( Q(k) )$, then $¬C$ is a $Σ_1$-sentence. Thus if $C$ is false, $¬C$ is true and hence provable in any sufficiently nice foundational system by $Σ_1$-completeness. This does not apply to all false sentences!



    It turns out that non-trivially RH (Riemann Hypothesis) is equivalent to a $Π_1$-sentence, and hence by the above we know that if it is false then even PA (Peano Arithmetic) can disprove it. Also, I should add that no expert believes that it would be any easier to prove unprovability of RH over PA than to directly disprove RH, even if it is false in the first place.



    Godel's incompleteness theorem has completely nothing to do with $Σ_1$-completeness. In fact, the generalized incompleteness theorem shows that any sufficiently nice foundational system (regardless of what underlying logic it uses) necessarily is either $Π_1$-incomplete or proves $0=1$. That is, if it is arithmetically consistent (i.e. does not prove $0=1$) then it also does not prove some true $Π_1$-sentence. Moreover, we can find such a sentence uniformly and explicitly (as described in the linked post).






    share|cite|improve this answer









    $endgroup$




    That is, how do we know that all false statements are provably so?




    This is simply wrong. There are both true and false statements that cannot be proven. What is true is that any sufficiently nice foundational system (i.e. one that has a proof verifier program and can reason about finite program runs) is $Σ_1$-complete, meaning that it proves every true $Σ_1$-sentence. Here, a $Σ_1$-sentence is an arithmetical sentence (i.e. quantifies only over $mathbb{N}$) that is equivalent to $∃k∈mathbb{N} ( Q(k) )$ for some arithmetical property $Q$ that uses only bounded quantifiers. For example, "There is an even number that is not the sum of two primes." can be expressed as a $Σ_1$-sentence. The "$Σ_1$" stands for "$1$ unbounded existential". Similarly a $Π_1$-sentence is an arithmetical sentence equivalent to one with only $1$ unbounded universal quantifier in Skolem normal form.



    In general, if you have a $Π_1$-sentence $C ≡ ∀k∈mathbb{N} ( Q(k) )$, then $¬C$ is a $Σ_1$-sentence. Thus if $C$ is false, $¬C$ is true and hence provable in any sufficiently nice foundational system by $Σ_1$-completeness. This does not apply to all false sentences!



    It turns out that non-trivially RH (Riemann Hypothesis) is equivalent to a $Π_1$-sentence, and hence by the above we know that if it is false then even PA (Peano Arithmetic) can disprove it. Also, I should add that no expert believes that it would be any easier to prove unprovability of RH over PA than to directly disprove RH, even if it is false in the first place.



    Godel's incompleteness theorem has completely nothing to do with $Σ_1$-completeness. In fact, the generalized incompleteness theorem shows that any sufficiently nice foundational system (regardless of what underlying logic it uses) necessarily is either $Π_1$-incomplete or proves $0=1$. That is, if it is arithmetically consistent (i.e. does not prove $0=1$) then it also does not prove some true $Π_1$-sentence. Moreover, we can find such a sentence uniformly and explicitly (as described in the linked post).







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 2 days ago









    user21820user21820

    39.7k543157




    39.7k543157








    • 3




      $begingroup$
      Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?"
      $endgroup$
      – MartianInvader
      2 days ago










    • $begingroup$
      @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it.
      $endgroup$
      – user21820
      yesterday










    • $begingroup$
      Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality.
      $endgroup$
      – user21820
      yesterday
















    • 3




      $begingroup$
      Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?"
      $endgroup$
      – MartianInvader
      2 days ago










    • $begingroup$
      @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it.
      $endgroup$
      – user21820
      yesterday










    • $begingroup$
      Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality.
      $endgroup$
      – user21820
      yesterday










    3




    3




    $begingroup$
    Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?"
    $endgroup$
    – MartianInvader
    2 days ago




    $begingroup$
    Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?"
    $endgroup$
    – MartianInvader
    2 days ago












    $begingroup$
    @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it.
    $endgroup$
    – user21820
    yesterday




    $begingroup$
    @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it.
    $endgroup$
    – user21820
    yesterday












    $begingroup$
    Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality.
    $endgroup$
    – user21820
    yesterday






    $begingroup$
    Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality.
    $endgroup$
    – user21820
    yesterday













    9












    $begingroup$

    This argument doesn't show that all false statements are provably so. (That's impossible for trivial reasons: if $P$ is a true statement that's not provable, then $lnot P$ is a false statement that's not provable.) The argument shows that the Riemann hypothesis, if false, is provably so, because there would be a specific number $s$ (in the critical strip but not on the critical line) at which $zeta(s)=0$, and so there would exist a proof (show that that specific number is a zero of $zeta$).






    share|cite|improve this answer









    $endgroup$









    • 7




      $begingroup$
      Note that your final claim is not obvious--even if some number is a zero of $zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove.
      $endgroup$
      – Eric Wofsey
      2 days ago










    • $begingroup$
      @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
      $endgroup$
      – Greg Martin
      2 days ago










    • $begingroup$
      "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean?
      $endgroup$
      – Arthur
      2 days ago










    • $begingroup$
      @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system.
      $endgroup$
      – user21820
      2 days ago






    • 1




      $begingroup$
      @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational.
      $endgroup$
      – ruakh
      yesterday


















    9












    $begingroup$

    This argument doesn't show that all false statements are provably so. (That's impossible for trivial reasons: if $P$ is a true statement that's not provable, then $lnot P$ is a false statement that's not provable.) The argument shows that the Riemann hypothesis, if false, is provably so, because there would be a specific number $s$ (in the critical strip but not on the critical line) at which $zeta(s)=0$, and so there would exist a proof (show that that specific number is a zero of $zeta$).






    share|cite|improve this answer









    $endgroup$









    • 7




      $begingroup$
      Note that your final claim is not obvious--even if some number is a zero of $zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove.
      $endgroup$
      – Eric Wofsey
      2 days ago










    • $begingroup$
      @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
      $endgroup$
      – Greg Martin
      2 days ago










    • $begingroup$
      "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean?
      $endgroup$
      – Arthur
      2 days ago










    • $begingroup$
      @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system.
      $endgroup$
      – user21820
      2 days ago






    • 1




      $begingroup$
      @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational.
      $endgroup$
      – ruakh
      yesterday
















    9












    9








    9





    $begingroup$

    This argument doesn't show that all false statements are provably so. (That's impossible for trivial reasons: if $P$ is a true statement that's not provable, then $lnot P$ is a false statement that's not provable.) The argument shows that the Riemann hypothesis, if false, is provably so, because there would be a specific number $s$ (in the critical strip but not on the critical line) at which $zeta(s)=0$, and so there would exist a proof (show that that specific number is a zero of $zeta$).






    share|cite|improve this answer









    $endgroup$



    This argument doesn't show that all false statements are provably so. (That's impossible for trivial reasons: if $P$ is a true statement that's not provable, then $lnot P$ is a false statement that's not provable.) The argument shows that the Riemann hypothesis, if false, is provably so, because there would be a specific number $s$ (in the critical strip but not on the critical line) at which $zeta(s)=0$, and so there would exist a proof (show that that specific number is a zero of $zeta$).







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 2 days ago









    Greg MartinGreg Martin

    36.5k23565




    36.5k23565








    • 7




      $begingroup$
      Note that your final claim is not obvious--even if some number is a zero of $zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove.
      $endgroup$
      – Eric Wofsey
      2 days ago










    • $begingroup$
      @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
      $endgroup$
      – Greg Martin
      2 days ago










    • $begingroup$
      "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean?
      $endgroup$
      – Arthur
      2 days ago










    • $begingroup$
      @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system.
      $endgroup$
      – user21820
      2 days ago






    • 1




      $begingroup$
      @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational.
      $endgroup$
      – ruakh
      yesterday
















    • 7




      $begingroup$
      Note that your final claim is not obvious--even if some number is a zero of $zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove.
      $endgroup$
      – Eric Wofsey
      2 days ago










    • $begingroup$
      @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
      $endgroup$
      – Greg Martin
      2 days ago










    • $begingroup$
      "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean?
      $endgroup$
      – Arthur
      2 days ago










    • $begingroup$
      @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system.
      $endgroup$
      – user21820
      2 days ago






    • 1




      $begingroup$
      @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational.
      $endgroup$
      – ruakh
      yesterday










    7




    7




    $begingroup$
    Note that your final claim is not obvious--even if some number is a zero of $zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove.
    $endgroup$
    – Eric Wofsey
    2 days ago




    $begingroup$
    Note that your final claim is not obvious--even if some number is a zero of $zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove.
    $endgroup$
    – Eric Wofsey
    2 days ago












    $begingroup$
    @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
    $endgroup$
    – Greg Martin
    2 days ago




    $begingroup$
    @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
    $endgroup$
    – Greg Martin
    2 days ago












    $begingroup$
    "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean?
    $endgroup$
    – Arthur
    2 days ago




    $begingroup$
    "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean?
    $endgroup$
    – Arthur
    2 days ago












    $begingroup$
    @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system.
    $endgroup$
    – user21820
    2 days ago




    $begingroup$
    @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system.
    $endgroup$
    – user21820
    2 days ago




    1




    1




    $begingroup$
    @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational.
    $endgroup$
    – ruakh
    yesterday






    $begingroup$
    @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational.
    $endgroup$
    – ruakh
    yesterday













    5












    $begingroup$

    Because if you were lucky enough to guess the counterexample, you could just check it. Note that this only works for problems where it's easy to check whether a given value is in fact a counterexample. To take a non-mathematical example, you have no hope of proving you've found a counterexample to "all people are mortal" because you'd have to verify some individual is immortal, meaning you'd have to verify nothing at all can kill them, which isn't possible.






    share|cite|improve this answer









    $endgroup$


















      5












      $begingroup$

      Because if you were lucky enough to guess the counterexample, you could just check it. Note that this only works for problems where it's easy to check whether a given value is in fact a counterexample. To take a non-mathematical example, you have no hope of proving you've found a counterexample to "all people are mortal" because you'd have to verify some individual is immortal, meaning you'd have to verify nothing at all can kill them, which isn't possible.






      share|cite|improve this answer









      $endgroup$
















        5












        5








        5





        $begingroup$

        Because if you were lucky enough to guess the counterexample, you could just check it. Note that this only works for problems where it's easy to check whether a given value is in fact a counterexample. To take a non-mathematical example, you have no hope of proving you've found a counterexample to "all people are mortal" because you'd have to verify some individual is immortal, meaning you'd have to verify nothing at all can kill them, which isn't possible.






        share|cite|improve this answer









        $endgroup$



        Because if you were lucky enough to guess the counterexample, you could just check it. Note that this only works for problems where it's easy to check whether a given value is in fact a counterexample. To take a non-mathematical example, you have no hope of proving you've found a counterexample to "all people are mortal" because you'd have to verify some individual is immortal, meaning you'd have to verify nothing at all can kill them, which isn't possible.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 2 days ago









        J.G.J.G.

        31.1k23149




        31.1k23149






























            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%2f3153739%2fwhy-doesnt-g%25c3%25b6dels-incompleteness-theorem-apply-to-false-statements%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

            Plaza Victoria

            Puebla de Zaragoza

            Musa