Why doesn't Gödel's incompleteness theorem apply to false statements?Decidability of the Riemann Hypothesis vs. the Goldbach ConjectureComputability viewpoint of Godel/Rosser's incompleteness theoremModel Theoretical Interpretation of the Incompleteness of Number TheoryExplanation of proof of Gödel's Second Incompleteness TheoremA qualitative, yet precise statement of Godel's incompleteness theorem?Gödel's Incompleteness Theorem — meta-reasoning “loophole”?Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?Godel's incompletness theorem - proving a statement is falseWhy do we find Gödel's Incompleteness Theorem surprising?Definition of Algorithms in Gödel's incompleteness theoremsIs the negation of all unprovable truths all unprovable falsehoods?Why does incompleteness not imply consistency?What was the exact form of Gödel's original Second Incompleteness Theorem?
How can I write humor as character trait?
Is aluminum electrical wire used on aircraft?
Why is the "ls" command showing permissions of files in a FAT32 partition?
Quoting Keynes in a lecture
How can "mimic phobia" be cured or prevented?
What should you do if you miss a job interview (deliberately)?
Are Captain Marvel's powers affected by Thanos' actions in Infinity War
Multiplicative persistence
Biological Blimps: Propulsion
Does Doodling or Improvising on the Piano Have Any Benefits?
Mimic lecturing on blackboard, facing audience
Can disgust be a key component of horror?
On a tidally locked planet, would time be quantized?
Can a Canadian Travel to the USA twice, less than 180 days each time?
How do you respond to a colleague from another team when they're wrongly expecting that you'll help them?
Lowest total scrabble score
Terse Method to Swap Lowest for Highest?
How does the math work for Perception checks?
Why should universal income be universal?
Moving brute-force search to FPGA
Why can Carol Danvers change her suit colours in the first place?
Keeping a ball lost forever
What does "Scientists rise up against statistical significance" mean? (Comment in Nature)
It grows, but water kills it
Why doesn't Gödel's incompleteness theorem apply to false statements?
Decidability of the Riemann Hypothesis vs. the Goldbach ConjectureComputability viewpoint of Godel/Rosser's incompleteness theoremModel Theoretical Interpretation of the Incompleteness of Number TheoryExplanation of proof of Gödel's Second Incompleteness TheoremA qualitative, yet precise statement of Godel's incompleteness theorem?Gödel's Incompleteness Theorem — meta-reasoning “loophole”?Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?Godel's incompletness theorem - proving a statement is falseWhy do we find Gödel's Incompleteness Theorem surprising?Definition of Algorithms in Gödel's incompleteness theoremsIs the negation of all unprovable truths all unprovable falsehoods?Why does incompleteness not imply consistency?What was the exact form of Gödel's original Second Incompleteness Theorem?
$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?
logic incompleteness
edited 2 days ago
Jens Renders
2,0211225
asked Mar 19 at 6:52
InertialObserverInertialObserver
440312
$endgroup$
|
show 1 more comment
$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?
logic incompleteness
edited 2 days ago
Jens Renders
2,0211225
asked Mar 19 at 6:52
InertialObserverInertialObserver
440312
$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
Mar 19 at 6:59
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
Mar 19 at 7:12
1
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
Mar 19 at 7:25
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
Mar 19 at 7:35
2
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
Mar 19 at 8:31
|
show 1 more comment
$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?
logic incompleteness
edited 2 days ago
Jens Renders
2,0211225
asked Mar 19 at 6:52
InertialObserverInertialObserver
440312
$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
logic incompleteness
edited 2 days ago
Jens Renders
2,0211225
asked Mar 19 at 6:52
InertialObserverInertialObserver
440312
edited 2 days ago
Jens Renders
2,0211225
asked Mar 19 at 6:52
InertialObserverInertialObserver
440312
edited 2 days ago
Jens Renders
2,0211225
edited 2 days ago
Jens Renders
2,0211225
edited 2 days ago
Jens Renders
2,0211225
2,0211225
asked Mar 19 at 6:52
InertialObserverInertialObserver
440312
asked Mar 19 at 6:52
InertialObserverInertialObserver
440312
asked Mar 19 at 6:52
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
Mar 19 at 6:59
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
Mar 19 at 7:12
1
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
Mar 19 at 7:25
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
Mar 19 at 7:35
2
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
Mar 19 at 8:31
|
show 1 more comment
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
Mar 19 at 6:59
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
Mar 19 at 7:12
1
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
Mar 19 at 7:25
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
Mar 19 at 7:35
2
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
Mar 19 at 8:31
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
Mar 19 at 6:59
$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
Mar 19 at 6:59
1
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
Mar 19 at 7:12
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
Mar 19 at 7:12
1
1
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
Mar 19 at 7:25
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
Mar 19 at 7:25
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
Mar 19 at 7:35
$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
Mar 19 at 7:35
2
2
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
Mar 19 at 8:31
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
Mar 19 at 8:31
|
show 1 more comment
3 Answers
3
active
oldest
votes
$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 $mathbbN$) that is equivalent to $∃k∈mathbbN ( 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∈mathbbN ( 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).
answered Mar 19 at 8:20
user21820user21820
39.7k543157
$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
Mar 19 at 20:31
$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
Mar 20 at 4:59
$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
Mar 20 at 5:14
add a comment |
$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$).
answered Mar 19 at 6:58
Greg MartinGreg Martin
36.5k23565
$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
Mar 19 at 7:11
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
Mar 19 at 7:16
$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
Mar 19 at 12:22
$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
Mar 19 at 13:00
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
Mar 20 at 4:19
|
show 1 more comment
$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.
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
$endgroup$
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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 $mathbbN$) that is equivalent to $∃k∈mathbbN ( 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∈mathbbN ( 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).
answered Mar 19 at 8:20
user21820user21820
39.7k543157
$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
Mar 19 at 20:31
$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
Mar 20 at 4:59
$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
Mar 20 at 5:14
add a comment |
$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 $mathbbN$) that is equivalent to $∃k∈mathbbN ( 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∈mathbbN ( 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).
answered Mar 19 at 8:20
user21820user21820
39.7k543157
$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
Mar 19 at 20:31
$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
Mar 20 at 4:59
$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
Mar 20 at 5:14
add a comment |
$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 $mathbbN$) that is equivalent to $∃k∈mathbbN ( 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∈mathbbN ( 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).
answered Mar 19 at 8:20
user21820user21820
39.7k543157
$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 $mathbbN$) that is equivalent to $∃k∈mathbbN ( 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∈mathbbN ( 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).
answered Mar 19 at 8:20
user21820user21820
39.7k543157
answered Mar 19 at 8:20
user21820user21820
39.7k543157
answered Mar 19 at 8:20
user21820user21820
39.7k543157
answered Mar 19 at 8:20
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
Mar 19 at 20:31
$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
Mar 20 at 4:59
$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
Mar 20 at 5:14
add a comment |
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
Mar 19 at 20:31
$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
Mar 20 at 4:59
$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
Mar 20 at 5:14
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
Mar 19 at 20:31
$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
Mar 19 at 20:31
$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
Mar 20 at 4:59
$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
Mar 20 at 4:59
$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
Mar 20 at 5:14
$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
Mar 20 at 5:14
add a comment |
$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$).
answered Mar 19 at 6:58
Greg MartinGreg Martin
36.5k23565
$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
Mar 19 at 7:11
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
Mar 19 at 7:16
$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
Mar 19 at 12:22
$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
Mar 19 at 13:00
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
Mar 20 at 4:19
|
show 1 more comment
$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$).
answered Mar 19 at 6:58
Greg MartinGreg Martin
36.5k23565
$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
Mar 19 at 7:11
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
Mar 19 at 7:16
$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
Mar 19 at 12:22
$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
Mar 19 at 13:00
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
Mar 20 at 4:19
|
show 1 more comment
$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$).
answered Mar 19 at 6:58
Greg MartinGreg Martin
36.5k23565
$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$).
answered Mar 19 at 6:58
Greg MartinGreg Martin
36.5k23565
answered Mar 19 at 6:58
Greg MartinGreg Martin
36.5k23565
answered Mar 19 at 6:58
Greg MartinGreg Martin
36.5k23565
answered Mar 19 at 6:58
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
Mar 19 at 7:11
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
Mar 19 at 7:16
$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
Mar 19 at 12:22
$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
Mar 19 at 13:00
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
Mar 20 at 4:19
|
show 1 more comment
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
Mar 19 at 7:11
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
Mar 19 at 7:16
$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
Mar 19 at 12:22
$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
Mar 19 at 13:00
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
Mar 20 at 4:19
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
Mar 19 at 7:11
$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
Mar 19 at 7:11
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
Mar 19 at 7:16
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
Mar 19 at 7:16
$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
Mar 19 at 12:22
$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
Mar 19 at 12:22
$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
Mar 19 at 13:00
$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
Mar 19 at 13:00
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
Mar 20 at 4:19
$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
Mar 20 at 4:19
|
show 1 more comment
$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.
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
$endgroup$
add a comment |
$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.
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
$endgroup$
add a comment |
$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.
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
$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.
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
answered Mar 19 at 7:00
J.G.J.G.
31.4k23149
31.4k23149
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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
Mar 19 at 6:59
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
Mar 19 at 7:12
1
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
Mar 19 at 7:25
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
Mar 19 at 7:35
2
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
Mar 19 at 8:31