A (quantifier-free) is true in standard model of PA ==> PA |- A ??
$begingroup$
Is the following statement correct ?
A is a formula in PA without a quantifier and
A is true for the standard model of arithmetic, i.e. the model
|N = (N,+,×,0,1,<)
This means: |N |= A
==>
A is proofable in PA. This means:
PA |- A
Example:
|N |= (x+y)^2 =x^2 + 2xy + y^2
===>
PA |- (x+y)^2 =x^2 + 2xy + y^2
If this statement is wrong, please give me a counterexample
cu
cx
peano-axioms
$endgroup$
add a comment |
$begingroup$
Is the following statement correct ?
A is a formula in PA without a quantifier and
A is true for the standard model of arithmetic, i.e. the model
|N = (N,+,×,0,1,<)
This means: |N |= A
==>
A is proofable in PA. This means:
PA |- A
Example:
|N |= (x+y)^2 =x^2 + 2xy + y^2
===>
PA |- (x+y)^2 =x^2 + 2xy + y^2
If this statement is wrong, please give me a counterexample
cu
cx
peano-axioms
$endgroup$
add a comment |
$begingroup$
Is the following statement correct ?
A is a formula in PA without a quantifier and
A is true for the standard model of arithmetic, i.e. the model
|N = (N,+,×,0,1,<)
This means: |N |= A
==>
A is proofable in PA. This means:
PA |- A
Example:
|N |= (x+y)^2 =x^2 + 2xy + y^2
===>
PA |- (x+y)^2 =x^2 + 2xy + y^2
If this statement is wrong, please give me a counterexample
cu
cx
peano-axioms
$endgroup$
Is the following statement correct ?
A is a formula in PA without a quantifier and
A is true for the standard model of arithmetic, i.e. the model
|N = (N,+,×,0,1,<)
This means: |N |= A
==>
A is proofable in PA. This means:
PA |- A
Example:
|N |= (x+y)^2 =x^2 + 2xy + y^2
===>
PA |- (x+y)^2 =x^2 + 2xy + y^2
If this statement is wrong, please give me a counterexample
cu
cx
peano-axioms
peano-axioms
asked Jan 29 at 15:27
user508589user508589
12
12
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$
Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.
What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.
Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.
So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.
$endgroup$
$begingroup$
Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
$endgroup$
– user508589
Jan 29 at 21:29
$begingroup$
@user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
$endgroup$
– Noah Schweber
Jan 29 at 22:35
add a comment |
$begingroup$
$$
text{You gave a counterexample: true in N but not PA-provable.} \
text{But there are so many examples with: true in N and PA-provable: } \
text{I define: } \
text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
bar 0 ; and ; bar 1 text{ are the constants from PA} \
oplus and circ text{ are the functions in PA} \
text{when z is element from I_N, I define:} \
bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
text{I proofed the following statement "S1"} \
text{When n is element from I_N then we have:} \
PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
text{I assume, that there are "many" of "similar" statements like S1.} \
text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
$$
cu
cx
$endgroup$
add a comment |
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%2f3092309%2fa-quantifier-free-is-true-in-standard-model-of-pa-pa-a%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$
Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.
What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.
Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.
So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.
$endgroup$
$begingroup$
Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
$endgroup$
– user508589
Jan 29 at 21:29
$begingroup$
@user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
$endgroup$
– Noah Schweber
Jan 29 at 22:35
add a comment |
$begingroup$
EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$
Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.
What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.
Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.
So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.
$endgroup$
$begingroup$
Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
$endgroup$
– user508589
Jan 29 at 21:29
$begingroup$
@user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
$endgroup$
– Noah Schweber
Jan 29 at 22:35
add a comment |
$begingroup$
EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$
Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.
What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.
Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.
So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.
$endgroup$
EDIT: It looks like I misread your question. There is an important difference between quantifier-free sentences, which is what my original answer (now below the fold) addressed, and quantifier-free formulas. Namely, when you speak of PA proving a formula with free variables (or of a structure satisfying such a formula), you're really asking about PA proving (or a structure satisfying) the universal closure of a quantifier-free formula: e.g. $$PAvdash (x+y)^2=x^2+2x+y^2$$ is really shorthand for $$PAvdashforall x,y((x+y)^2=x^2+2x+y^2).$$
Such statements are no longer provable in PA in general. For example, it's essentially a consequence of the MRDP theorem that there is a Diophantine equation $t_1(x_1,..,x_n)=t_2(x_1,...,x_n)$ which has no solutions but which PA can't prove has no solutions; then the quantifier-free formula $$neg(t_1(x_1,...,x_n)=t_2(x_1,...,x_n))$$ is true in $mathbb{N}$ but not PA-provable.
What if we don't work with implicit universal quantifiers - that is, we restrict attention to sentences (= formulas with no free variables)? This was the original - incorrect - way I interpreted your question.
Here we get a positive result: PA proves every true $Sigma_1$ sentence (that is, every sentence of the form $exists x_1...exists x_nvarphi(x_1,...,x_n)$, where $varphi$ uses only bounded quantifiers). This fact ("$Sigma_1$-completeness") about PA does not depend on PA being consistent - it is provable in PA itself, or indeed much less. The proof is tedious but not hard. Under the further assumption that PA is $Sigma_1$-sound, this implies that the true $Sigma_1$-sentences are exactly those which PA proves.
So this exactly delineates PA's power in terms of the coarse arithmetic hierarchy: PA proves exactly the correct $Sigma_1$ sentences (under a reasonable assumption on PA), but there are correct $Pi_1$ sentences which PA doesn't prove.
edited Jan 29 at 22:56
answered Jan 29 at 16:02
Noah SchweberNoah Schweber
128k10151294
128k10151294
$begingroup$
Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
$endgroup$
– user508589
Jan 29 at 21:29
$begingroup$
@user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
$endgroup$
– Noah Schweber
Jan 29 at 22:35
add a comment |
$begingroup$
Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
$endgroup$
– user508589
Jan 29 at 21:29
$begingroup$
@user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
$endgroup$
– Noah Schweber
Jan 29 at 22:35
$begingroup$
Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
$endgroup$
– user508589
Jan 29 at 21:29
$begingroup$
Thank you for your feedback. I tried to proof my statement, but I could not do it. My idee: every term represent as a polynom. Please can you give me a link to the proof of my statement. cu cx
$endgroup$
– user508589
Jan 29 at 21:29
$begingroup$
@user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
$endgroup$
– Noah Schweber
Jan 29 at 22:35
$begingroup$
@user508589 Looking at your question again, I misread it (the issue being "formula" versus "sentence" and the implicit universal quantifier when we talk about proving/satisfying the former). I've edited.
$endgroup$
– Noah Schweber
Jan 29 at 22:35
add a comment |
$begingroup$
$$
text{You gave a counterexample: true in N but not PA-provable.} \
text{But there are so many examples with: true in N and PA-provable: } \
text{I define: } \
text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
bar 0 ; and ; bar 1 text{ are the constants from PA} \
oplus and circ text{ are the functions in PA} \
text{when z is element from I_N, I define:} \
bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
text{I proofed the following statement "S1"} \
text{When n is element from I_N then we have:} \
PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
text{I assume, that there are "many" of "similar" statements like S1.} \
text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
$$
cu
cx
$endgroup$
add a comment |
$begingroup$
$$
text{You gave a counterexample: true in N but not PA-provable.} \
text{But there are so many examples with: true in N and PA-provable: } \
text{I define: } \
text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
bar 0 ; and ; bar 1 text{ are the constants from PA} \
oplus and circ text{ are the functions in PA} \
text{when z is element from I_N, I define:} \
bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
text{I proofed the following statement "S1"} \
text{When n is element from I_N then we have:} \
PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
text{I assume, that there are "many" of "similar" statements like S1.} \
text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
$$
cu
cx
$endgroup$
add a comment |
$begingroup$
$$
text{You gave a counterexample: true in N but not PA-provable.} \
text{But there are so many examples with: true in N and PA-provable: } \
text{I define: } \
text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
bar 0 ; and ; bar 1 text{ are the constants from PA} \
oplus and circ text{ are the functions in PA} \
text{when z is element from I_N, I define:} \
bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
text{I proofed the following statement "S1"} \
text{When n is element from I_N then we have:} \
PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
text{I assume, that there are "many" of "similar" statements like S1.} \
text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
$$
cu
cx
$endgroup$
$$
text{You gave a counterexample: true in N but not PA-provable.} \
text{But there are so many examples with: true in N and PA-provable: } \
text{I define: } \
text{I_N} = {0,1,2, ...} text{ is the set of intuitive natural numbers} \
bar 0 ; and ; bar 1 text{ are the constants from PA} \
oplus and circ text{ are the functions in PA} \
text{when z is element from I_N, I define:} \
bar z := bar 1 oplus ... oplus + bar 1 quad text{n-times} \
text{I proofed the following statement "S1"} \
text{When n is element from I_N then we have:} \
PA vdash forall x forall y ; (bar z = x oplus y quad .rightarrow. quad
bigvee_{i=0}^z (x=bar i land y=overline{z-i}) \
text{I assume, that there are "many" of "similar" statements like S1.} \
text{Is it possible to formulate a statement "S", so that "S1" follows from "S" ?} \
$$
cu
cx
edited Feb 4 at 9:09
answered Feb 3 at 9:42
user508589user508589
12
12
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%2f3092309%2fa-quantifier-free-is-true-in-standard-model-of-pa-pa-a%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