Statement true because not provable Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Model 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
Take 2! Is this homebrew Lady of Pain warlock patron balanced?
Generate an RGB colour grid
Denied boarding although I have proper visa and documentation. To whom should I make a complaint?
What is the font for "b" letter?
Time to Settle Down!
Can the Great Weapon Master feat's "Power Attack" apply to attacks from the Spiritual Weapon spell?
Amount of permutations on an NxNxN Rubik's Cube
How could we fake a moon landing now?
Is CEO the "profession" with the most psychopaths?
Localisation of Category
Multiple OR (||) Conditions in If Statement
Is it fair for a professor to grade us on the possession of past papers?
Effects on objects due to a brief relocation of massive amounts of mass
Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?
How were pictures turned from film to a big picture in a picture frame before digital scanning?
Did Deadpool rescue all of the X-Force?
How does light 'choose' between wave and particle behaviour?
Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?
Why wasn't DOSKEY integrated with COMMAND.COM?
Illegal assignment from sObject to Id
How to write the following sign?
Should I use a zero-interest credit card for a large one-time purchase?
Why does the remaining Rebel fleet at the end of Rogue One seem dramatically larger than the one in A New Hope?
Is there any word for a place full of confusion?
Statement true because not provable
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Model 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
asked Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
$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
asked Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
$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
Apr 10 at 21:18
$begingroup$
Someone call it a Goldbach-like sentence and we have that "A $Pi_1$ sentence $varphi$ is true iff $lnot varphi$ is not provable from $mathsf Q$".
$endgroup$
– Mauro ALLEGRANZA
Apr 11 at 6:30
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
asked Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
$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 Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
asked Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
asked Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
asked Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
asked Apr 10 at 15:26
Thomas LesgourguesThomas Lesgourgues
1,401220
1,401220
$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
Apr 10 at 21:18
$begingroup$
Someone call it a Goldbach-like sentence and we have that "A $Pi_1$ sentence $varphi$ is true iff $lnot varphi$ is not provable from $mathsf Q$".
$endgroup$
– Mauro ALLEGRANZA
Apr 11 at 6:30
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
Apr 10 at 21:18
$begingroup$
Someone call it a Goldbach-like sentence and we have that "A $Pi_1$ sentence $varphi$ is true iff $lnot varphi$ is not provable from $mathsf Q$".
$endgroup$
– Mauro ALLEGRANZA
Apr 11 at 6:30
$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
Apr 10 at 21:18
$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
Apr 10 at 21:18
$begingroup$
Someone call it a Goldbach-like sentence and we have that "A $Pi_1$ sentence $varphi$ is true iff $lnot varphi$ is not provable from $mathsf Q$".
$endgroup$
– Mauro ALLEGRANZA
Apr 11 at 6:30
$begingroup$
Someone call it a Goldbach-like sentence and we have that "A $Pi_1$ sentence $varphi$ is true iff $lnot varphi$ is not provable from $mathsf Q$".
$endgroup$
– Mauro ALLEGRANZA
Apr 11 at 6:30
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.
answered Apr 10 at 15:36
TedTed
22.2k13361
$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
Apr 10 at 17:22
$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
Apr 10 at 21:05
$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
Apr 10 at 21:14
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$ ...
So, the question is: what kinds of interesting statements are there that contain a single quantifier, and for which you can prove that PA cannot prove either it or its negation?
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
$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
Apr 10 at 17:34
$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
Apr 10 at 17:59
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.
answered Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
$endgroup$
add a comment |
Your Answer
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.
answered Apr 10 at 15:36
TedTed
22.2k13361
$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
Apr 10 at 17:22
$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
Apr 10 at 21:05
$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
Apr 10 at 21:14
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.
answered Apr 10 at 15:36
TedTed
22.2k13361
$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
Apr 10 at 17:22
$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
Apr 10 at 21:05
$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
Apr 10 at 21:14
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.
answered Apr 10 at 15:36
TedTed
22.2k13361
$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 Apr 10 at 15:36
TedTed
22.2k13361
answered Apr 10 at 15:36
TedTed
22.2k13361
answered Apr 10 at 15:36
TedTed
22.2k13361
answered Apr 10 at 15:36
TedTed
22.2k13361
22.2k13361
$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
Apr 10 at 17:22
$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
Apr 10 at 21:05
$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
Apr 10 at 21:14
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
Apr 10 at 17:22
$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
Apr 10 at 21:05
$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
Apr 10 at 21:14
$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
Apr 10 at 17:22
$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
Apr 10 at 17:22
$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
Apr 10 at 21:05
$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
Apr 10 at 21:05
$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
Apr 10 at 21:14
$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
Apr 10 at 21:14
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$ ...
So, the question is: what kinds of interesting statements are there that contain a single quantifier, and for which you can prove that PA cannot prove either it or its negation?
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
$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
Apr 10 at 17:34
$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
Apr 10 at 17:59
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$ ...
So, the question is: what kinds of interesting statements are there that contain a single quantifier, and for which you can prove that PA cannot prove either it or its negation?
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
$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
Apr 10 at 17:34
$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
Apr 10 at 17:59
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$ ...
So, the question is: what kinds of interesting statements are there that contain a single quantifier, and for which you can prove that PA cannot prove either it or its negation?
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
$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$ ...
So, the question is: what kinds of interesting statements are there that contain a single quantifier, and for which you can prove that PA cannot prove either it or its negation?
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
edited Apr 10 at 22:42
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
answered Apr 10 at 17:27
Bram28Bram28
64.7k44793
64.7k44793
$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
Apr 10 at 17:34
$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
Apr 10 at 17:59
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
Apr 10 at 17:34
$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
Apr 10 at 17:59
$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
Apr 10 at 17:34
$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
Apr 10 at 17:34
$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
Apr 10 at 17:59
$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
Apr 10 at 17:59
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.
answered Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
$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.
answered Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
$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.
answered Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
$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 Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
answered Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
answered Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
answered Apr 10 at 15:38
Floris ClaassensFloris Claassens
1,48029
1,48029
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%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
Apr 10 at 21:18
$begingroup$
Someone call it a Goldbach-like sentence and we have that "A $Pi_1$ sentence $varphi$ is true iff $lnot varphi$ is not provable from $mathsf Q$".
$endgroup$
– Mauro ALLEGRANZA
Apr 11 at 6:30