Is Peano arithmetic complete for quantifier free formulas and strict arithmetical formulas?
$begingroup$
By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.
By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.
Is PA complete for quantifier free arithmetical sentences?
Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
Is PA complete for strict arithmetical sentences?
Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
peano-axioms
$endgroup$
add a comment |
$begingroup$
By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.
By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.
Is PA complete for quantifier free arithmetical sentences?
Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
Is PA complete for strict arithmetical sentences?
Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
peano-axioms
$endgroup$
add a comment |
$begingroup$
By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.
By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.
Is PA complete for quantifier free arithmetical sentences?
Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
Is PA complete for strict arithmetical sentences?
Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
peano-axioms
$endgroup$
By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.
By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.
Is PA complete for quantifier free arithmetical sentences?
Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
Is PA complete for strict arithmetical sentences?
Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA vdash P) oplus (PA vdash neg P)$?
peano-axioms
peano-axioms
asked Dec 7 '18 at 9:34
ZuhairZuhair
248111
248111
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.
As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.
(A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)
If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.
$endgroup$
$begingroup$
This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
$endgroup$
– Andreas Blass
Dec 7 '18 at 14:57
$begingroup$
@AndreasBlass That also needs subtraction I think.
$endgroup$
– Noah Schweber
Dec 7 '18 at 15:00
$begingroup$
There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:06
$begingroup$
To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:08
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%2f3029696%2fis-peano-arithmetic-complete-for-quantifier-free-formulas-and-strict-arithmetica%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.
As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.
(A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)
If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.
$endgroup$
$begingroup$
This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
$endgroup$
– Andreas Blass
Dec 7 '18 at 14:57
$begingroup$
@AndreasBlass That also needs subtraction I think.
$endgroup$
– Noah Schweber
Dec 7 '18 at 15:00
$begingroup$
There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:06
$begingroup$
To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:08
add a comment |
$begingroup$
First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.
As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.
(A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)
If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.
$endgroup$
$begingroup$
This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
$endgroup$
– Andreas Blass
Dec 7 '18 at 14:57
$begingroup$
@AndreasBlass That also needs subtraction I think.
$endgroup$
– Noah Schweber
Dec 7 '18 at 15:00
$begingroup$
There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:06
$begingroup$
To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:08
add a comment |
$begingroup$
First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.
As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.
(A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)
If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.
$endgroup$
First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.
As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $Pi_1$ queries in this way.
(A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)iff forall x_1,...,x_n(neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)
If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.
edited Dec 7 '18 at 15:05
answered Dec 7 '18 at 13:31
Noah SchweberNoah Schweber
122k10149284
122k10149284
$begingroup$
This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
$endgroup$
– Andreas Blass
Dec 7 '18 at 14:57
$begingroup$
@AndreasBlass That also needs subtraction I think.
$endgroup$
– Noah Schweber
Dec 7 '18 at 15:00
$begingroup$
There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:06
$begingroup$
To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:08
add a comment |
$begingroup$
This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
$endgroup$
– Andreas Blass
Dec 7 '18 at 14:57
$begingroup$
@AndreasBlass That also needs subtraction I think.
$endgroup$
– Noah Schweber
Dec 7 '18 at 15:00
$begingroup$
There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:06
$begingroup$
To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:08
$begingroup$
This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
$endgroup$
– Andreas Blass
Dec 7 '18 at 14:57
$begingroup$
This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $pneq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left.
$endgroup$
– Andreas Blass
Dec 7 '18 at 14:57
$begingroup$
@AndreasBlass That also needs subtraction I think.
$endgroup$
– Noah Schweber
Dec 7 '18 at 15:00
$begingroup$
@AndreasBlass That also needs subtraction I think.
$endgroup$
– Noah Schweber
Dec 7 '18 at 15:00
$begingroup$
There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:06
$begingroup$
There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $pneq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.)
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:06
$begingroup$
To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:08
$begingroup$
To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true.
$endgroup$
– Andreas Blass
Dec 7 '18 at 15:08
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%2f3029696%2fis-peano-arithmetic-complete-for-quantifier-free-formulas-and-strict-arithmetica%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