Statement true because not provable The 2019 Stack Overflow Developer Survey Results Are InModel Theoretical Interpretation of the Incompleteness of Number TheoryIs the negation of the Gödel sentence always unprovable too?Understanding the syntactical completenessExamples of statements which are true but not provableclarify the term “arithmetics” when talking about Gödel's incompleteness theoremsTrue but unprovable?Why can PA + $neg G_PA$ be consistent?Understanding the definition of completeness of formal theorys(and Godel's famous theorem)What's wrong with this “proof” that Gödel's first incompleteness theorem is wrong?Gödel diagonalization and formulas not holding for themselvesFOL and Gödel's Incompleteness Theorem 1
Is there any way to tell whether the shot is going to hit you or not?
Did Section 31 appear in Star Trek: The Next Generation?
Why isn't airport relocation done gradually?
Worn-tile Scrabble
Is bread bad for ducks?
How to save as into a customized destination on macOS?
Right tool to dig six foot holes?
What does ひと匙 mean in this manga and has it been used colloquially?
Where to refill my bottle in India?
Why is my custom API endpoint not working?
"as much details as you can remember"
Why do UK politicians seemingly ignore opinion polls on Brexit?
Shouldn't "much" here be used instead of "more"?
What is the formula behind each level spell slot progression that I can use in a spreadsheet?
Why is the maximum length of OpenWrt’s root password 8 characters?
Identify This Plant (Flower)
Geography at the pixel level
Resizing object distorts it (Illustrator CC 2018)
What is the most effective way of iterating a std::vector and why?
What did it mean to "align" a radio?
Who coined the term "madman theory"?
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
How to notate time signature switching consistently every measure
How to manage monthly salary
Statement true because not provable
The 2019 Stack Overflow Developer Survey Results Are InModel Theoretical Interpretation of the Incompleteness of Number TheoryIs the negation of the Gödel sentence always unprovable too?Understanding the syntactical completenessExamples of statements which are true but not provableclarify the term “arithmetics” when talking about Gödel's incompleteness theoremsTrue but unprovable?Why can PA + $neg G_PA$ be consistent?Understanding the definition of completeness of formal theorys(and Godel's famous theorem)What's wrong with this “proof” that Gödel's first incompleteness theorem is wrong?Gödel diagonalization and formulas not holding for themselvesFOL and Gödel's Incompleteness Theorem 1
$begingroup$
It is my understanding that Gödel's second incompleteness theorem says roughly that
there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).
If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?
Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?
Is this reasoning correct?
logic incompleteness
$endgroup$
add a comment |
$begingroup$
It is my understanding that Gödel's second incompleteness theorem says roughly that
there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).
If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?
Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?
Is this reasoning correct?
logic incompleteness
$endgroup$
$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago
add a comment |
$begingroup$
It is my understanding that Gödel's second incompleteness theorem says roughly that
there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).
If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?
Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?
Is this reasoning correct?
logic incompleteness
$endgroup$
It is my understanding that Gödel's second incompleteness theorem says roughly that
there exists a sentence $varphi$ such that neither $varphi$ nor $negvarphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $mathbbN$).
If $varphi$ is a formula in the style : "for all integers $n$, then $psi(n)$".
For me, if $varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $negpsi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?
Therefore, it someone manage to prove that it not provable, does it mean that $varphi$ must be true?
Is this reasoning correct?
logic incompleteness
logic incompleteness
asked 7 hours ago
Thomas LesgourguesThomas Lesgourgues
1,340220
1,340220
$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago
add a comment |
$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago
$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago
$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.
However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.
$endgroup$
$begingroup$
Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
$endgroup$
– spaceisdarkgreen
1 hour ago
add a comment |
$begingroup$
You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.
Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.
$endgroup$
add a comment |
$begingroup$
First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$
So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.
Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...
$endgroup$
$begingroup$
Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
$endgroup$
– Bram28
4 hours ago
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%2f3182541%2fstatement-true-because-not-provable%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.
However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.
$endgroup$
$begingroup$
Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
$endgroup$
– spaceisdarkgreen
1 hour ago
add a comment |
$begingroup$
No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.
However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.
$endgroup$
$begingroup$
Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
$endgroup$
– spaceisdarkgreen
1 hour ago
add a comment |
$begingroup$
No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.
However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.
$endgroup$
No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $negpsi(n_f)$ itself may be another statement that is true but not provable in PA.
However, if for every $n$, you know that either $psi(n)$ or $negpsi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $psi$ is quantifier-free, because then $psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.
answered 6 hours ago
TedTed
22.1k13361
22.1k13361
$begingroup$
Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
$endgroup$
– spaceisdarkgreen
1 hour ago
add a comment |
$begingroup$
Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $zeta(x)=0$.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/…
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
$endgroup$
– spaceisdarkgreen
1 hour ago
$begingroup$
@Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.)
$endgroup$
– spaceisdarkgreen
1 hour ago
add a comment |
$begingroup$
You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.
Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.
$endgroup$
add a comment |
$begingroup$
You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.
Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.
$endgroup$
add a comment |
$begingroup$
You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.
Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.
$endgroup$
You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.
Consider groups for example. If we take the theory of group then we should not be able to prove $(forall x)(forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.
answered 6 hours ago
Floris ClaassensFloris Claassens
1,47429
1,47429
add a comment |
add a comment |
$begingroup$
First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$
So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.
Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...
$endgroup$
$begingroup$
Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$
So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.
Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...
$endgroup$
$begingroup$
Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$
So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.
Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...
$endgroup$
First of all, if I can prove that PA cannot prove $varphi$, that does not mean that $varphi$ is true ... for if $varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$
So, I think what you are trying to say is: If I can prove that PA cannot prove either $varphi$ or $neg varphi$, then that must mean that $varphi$ is true.
Second, your argument for this works when $varphi$ is of the form $forall x psi(x)$ where $psi(x)$ is quantifier-free, for if it is false, then $neg psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $neg varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $varphi$ ...
edited 7 mins ago
answered 5 hours ago
Bram28Bram28
64.3k44793
64.3k44793
$begingroup$
Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
$endgroup$
– Bram28
4 hours ago
$begingroup$
Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
Hi, I agree I need to restrict myself to quantifier free $psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample.
$endgroup$
– Thomas Lesgourgues
5 hours ago
$begingroup$
@ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
$endgroup$
– Bram28
4 hours ago
$begingroup$
@ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager.
$endgroup$
– Bram28
4 hours ago
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%2f3182541%2fstatement-true-because-not-provable%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
$begingroup$
I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false".
$endgroup$
– DanielV
1 hour ago