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 theoremA naive inquiry of Godel's incompleteness--or why does mathematics need proofs of unprovability?Explanation 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 it possible to construct a formal system such that all interesting statements from ZFC can be proven within the system?Why does incompleteness not imply consistency?
What is the tangent at a sharp point on a curve?
Why didn’t Eve recognize the little cockroach as a living organism?
Can creatures abilities target that creature itself?
Would a primitive species be able to learn English from reading books alone?
Calculate Pi using Monte Carlo
categorizing a variable turns it from insignificant to significant
Asserting that Atheism and Theism are both faith based positions
Is there any common country to visit for persons holding UK and Schengen visas?
Relations between homogeneous polynomials
What is it called when someone votes for an option that's not their first choice?
Capacitor electron flow
Travelling in US for more than 90 days
Hashing password to increase entropy
Connection Between Knot Theory and Number Theory
Why do Radio Buttons not fill the entire outer circle?
Friend wants my recommendation but I don't want to give it to him
Why didn't Voldemort know what Grindelwald looked like?
PTIJ: Which Dr. Seuss books should one obtain?
What should be the ideal length of sentences in a blog post for ease of reading?
Reasons for having MCU pin-states default to pull-up/down out of reset
Extract substring according to regexp with sed or grep
Strange behavior in TikZ draw command
How would a solely written language work mechanically
How do you justify more code being written by following clean code practices?
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 theoremA naive inquiry of Godel's incompleteness--or why does mathematics need proofs of unprovability?Explanation 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 it possible to construct a formal system such that all interesting statements from ZFC can be proven within the system?Why does incompleteness not imply consistency?
$begingroup$
I've read and heard in lectures that
A way to prove that the Riemann hypothesis is true is to show that it's 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
$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 it's 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
$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
17 hours ago
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
17 hours ago
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
17 hours ago
1
$begingroup$
It is not the full story to say that a proof is non constructive, because a non constructive proof can be converted to a constructive proof just by adding assumptions. Whether a theorem is constructively established is based on whether or not you classify the assumptions as constructive, for those assumptions that would be present in a constructively organized proof. And whether an assumption is constructive is a whole other philosophical (and computational) matter.
$endgroup$
– DanielV
17 hours ago
1
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
16 hours ago
|
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 it's 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
$endgroup$
I've read and heard in lectures that
A way to prove that the Riemann hypothesis is true is to show that it's 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
asked 17 hours ago
InertialObserverInertialObserver
420211
420211
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
17 hours ago
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
17 hours ago
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
17 hours ago
1
$begingroup$
It is not the full story to say that a proof is non constructive, because a non constructive proof can be converted to a constructive proof just by adding assumptions. Whether a theorem is constructively established is based on whether or not you classify the assumptions as constructive, for those assumptions that would be present in a constructively organized proof. And whether an assumption is constructive is a whole other philosophical (and computational) matter.
$endgroup$
– DanielV
17 hours ago
1
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
16 hours ago
|
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
17 hours ago
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
17 hours ago
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
17 hours ago
1
$begingroup$
It is not the full story to say that a proof is non constructive, because a non constructive proof can be converted to a constructive proof just by adding assumptions. Whether a theorem is constructively established is based on whether or not you classify the assumptions as constructive, for those assumptions that would be present in a constructively organized proof. And whether an assumption is constructive is a whole other philosophical (and computational) matter.
$endgroup$
– DanielV
17 hours ago
1
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
16 hours 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
17 hours 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
17 hours ago
1
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
17 hours ago
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
17 hours ago
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
17 hours ago
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
17 hours ago
1
1
$begingroup$
It is not the full story to say that a proof is non constructive, because a non constructive proof can be converted to a constructive proof just by adding assumptions. Whether a theorem is constructively established is based on whether or not you classify the assumptions as constructive, for those assumptions that would be present in a constructively organized proof. And whether an assumption is constructive is a whole other philosophical (and computational) matter.
$endgroup$
– DanielV
17 hours ago
$begingroup$
It is not the full story to say that a proof is non constructive, because a non constructive proof can be converted to a constructive proof just by adding assumptions. Whether a theorem is constructively established is based on whether or not you classify the assumptions as constructive, for those assumptions that would be present in a constructively organized proof. And whether an assumption is constructive is a whole other philosophical (and computational) matter.
$endgroup$
– DanielV
17 hours ago
1
1
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
16 hours ago
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
16 hours ago
|
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).
$endgroup$
1
$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
4 hours ago
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$).
$endgroup$
6
$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
17 hours ago
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
17 hours 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
12 hours 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
11 hours ago
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.
$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).
$endgroup$
1
$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
4 hours ago
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).
$endgroup$
1
$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
4 hours ago
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).
$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 16 hours ago
user21820user21820
39.6k543156
39.6k543156
1
$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
4 hours ago
add a comment |
1
$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
4 hours ago
1
1
$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
4 hours 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
4 hours ago
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$).
$endgroup$
6
$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
17 hours ago
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
17 hours 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
12 hours 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
11 hours ago
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$).
$endgroup$
6
$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
17 hours ago
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
17 hours 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
12 hours 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
11 hours ago
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$).
$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 17 hours ago
Greg MartinGreg Martin
36.4k23565
36.4k23565
6
$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
17 hours ago
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
17 hours 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
12 hours 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
11 hours ago
add a comment |
6
$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
17 hours ago
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
17 hours 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
12 hours 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
11 hours ago
6
6
$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
17 hours 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
17 hours ago
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
17 hours ago
$begingroup$
@EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought.
$endgroup$
– Greg Martin
17 hours 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
12 hours 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
12 hours 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
11 hours 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
11 hours ago
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.
$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.
$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.
$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 17 hours ago
J.G.J.G.
30.8k23149
30.8k23149
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
17 hours ago
1
$begingroup$
@QthePlatypus Do you have a reference for this "proof" ?
$endgroup$
– DanielV
17 hours ago
$begingroup$
Sorry I should have said “Has a famous proof of it’s falsity”.
$endgroup$
– Q the Platypus
17 hours ago
1
$begingroup$
It is not the full story to say that a proof is non constructive, because a non constructive proof can be converted to a constructive proof just by adding assumptions. Whether a theorem is constructively established is based on whether or not you classify the assumptions as constructive, for those assumptions that would be present in a constructively organized proof. And whether an assumption is constructive is a whole other philosophical (and computational) matter.
$endgroup$
– DanielV
17 hours ago
1
$begingroup$
See also math.stackexchange.com/questions/2305177/…
$endgroup$
– Asaf Karagila♦
16 hours ago