Undecidable statement that doesn't involve infinity
$begingroup$
All statements independent of ZFC I'm aware of involve infinity.
Do we know any statement independent of ZFC of the form $forall n in mathbb{N}: P(n)$ where $P(n)$ is disprovable if false? (In other words, an independent statement that could be disprovable by a counterexample).
If not, can we show that such a statement must exist? Can there be a consistent logical system in which such a statement cannot exist?
logic set-theory incompleteness
asked Dec 10 '18 at 1:47
StefanStefan
1906
$endgroup$
add a comment |
$begingroup$
All statements independent of ZFC I'm aware of involve infinity.
Do we know any statement independent of ZFC of the form $forall n in mathbb{N}: P(n)$ where $P(n)$ is disprovable if false? (In other words, an independent statement that could be disprovable by a counterexample).
If not, can we show that such a statement must exist? Can there be a consistent logical system in which such a statement cannot exist?
logic set-theory incompleteness
asked Dec 10 '18 at 1:47
StefanStefan
1906
$endgroup$
3
$begingroup$
This is a famous solved problem. The statement "ZFC is consistent" is expressible in ZFC and unprovable in ZFC if the statement is true - that is the conclusion of Godel's incompleteness theorem. The statement is easy to disprove if false - just present the formal proof of any contradiction from the ZFC axioms.
$endgroup$
– Carl Mummert
Dec 10 '18 at 1:56
2
$begingroup$
And the statement "ZFC is consistent" IS a statement of the desired form: "For all natural numbers $n$, $n$ is not the code of a ZFC proof of the formula 0 = 1"
$endgroup$
– Ned
Dec 10 '18 at 2:33
1
$begingroup$
"Can there be a consistent logical system in which such a statement cannot exist?" Godel's theorem (which always produces undecidable statements of the very simple sort you describe) does hold for a very general class of sufficiently strong formal systems. However, there are systems that are complete, even some quite natural ones. For example, Presberger arithmetic, and the theory of real closed fields.
$endgroup$
– spaceisdarkgreen
Dec 10 '18 at 3:57
add a comment |
$begingroup$
All statements independent of ZFC I'm aware of involve infinity.
Do we know any statement independent of ZFC of the form $forall n in mathbb{N}: P(n)$ where $P(n)$ is disprovable if false? (In other words, an independent statement that could be disprovable by a counterexample).
If not, can we show that such a statement must exist? Can there be a consistent logical system in which such a statement cannot exist?
logic set-theory incompleteness
asked Dec 10 '18 at 1:47
StefanStefan
1906
$endgroup$
All statements independent of ZFC I'm aware of involve infinity.
Do we know any statement independent of ZFC of the form $forall n in mathbb{N}: P(n)$ where $P(n)$ is disprovable if false? (In other words, an independent statement that could be disprovable by a counterexample).
If not, can we show that such a statement must exist? Can there be a consistent logical system in which such a statement cannot exist?
logic set-theory incompleteness
logic set-theory incompleteness
asked Dec 10 '18 at 1:47
StefanStefan
1906
asked Dec 10 '18 at 1:47
StefanStefan
1906
asked Dec 10 '18 at 1:47
StefanStefan
1906
asked Dec 10 '18 at 1:47
StefanStefan
1906
asked Dec 10 '18 at 1:47
StefanStefan
1906
1906
3
$begingroup$
This is a famous solved problem. The statement "ZFC is consistent" is expressible in ZFC and unprovable in ZFC if the statement is true - that is the conclusion of Godel's incompleteness theorem. The statement is easy to disprove if false - just present the formal proof of any contradiction from the ZFC axioms.
$endgroup$
– Carl Mummert
Dec 10 '18 at 1:56
2
$begingroup$
And the statement "ZFC is consistent" IS a statement of the desired form: "For all natural numbers $n$, $n$ is not the code of a ZFC proof of the formula 0 = 1"
$endgroup$
– Ned
Dec 10 '18 at 2:33
1
$begingroup$
"Can there be a consistent logical system in which such a statement cannot exist?" Godel's theorem (which always produces undecidable statements of the very simple sort you describe) does hold for a very general class of sufficiently strong formal systems. However, there are systems that are complete, even some quite natural ones. For example, Presberger arithmetic, and the theory of real closed fields.
$endgroup$
– spaceisdarkgreen
Dec 10 '18 at 3:57
add a comment |
3
$begingroup$
This is a famous solved problem. The statement "ZFC is consistent" is expressible in ZFC and unprovable in ZFC if the statement is true - that is the conclusion of Godel's incompleteness theorem. The statement is easy to disprove if false - just present the formal proof of any contradiction from the ZFC axioms.
$endgroup$
– Carl Mummert
Dec 10 '18 at 1:56
2
$begingroup$
And the statement "ZFC is consistent" IS a statement of the desired form: "For all natural numbers $n$, $n$ is not the code of a ZFC proof of the formula 0 = 1"
$endgroup$
– Ned
Dec 10 '18 at 2:33
1
$begingroup$
"Can there be a consistent logical system in which such a statement cannot exist?" Godel's theorem (which always produces undecidable statements of the very simple sort you describe) does hold for a very general class of sufficiently strong formal systems. However, there are systems that are complete, even some quite natural ones. For example, Presberger arithmetic, and the theory of real closed fields.
$endgroup$
– spaceisdarkgreen
Dec 10 '18 at 3:57
3
3
$begingroup$
This is a famous solved problem. The statement "ZFC is consistent" is expressible in ZFC and unprovable in ZFC if the statement is true - that is the conclusion of Godel's incompleteness theorem. The statement is easy to disprove if false - just present the formal proof of any contradiction from the ZFC axioms.
$endgroup$
– Carl Mummert
Dec 10 '18 at 1:56
$begingroup$
This is a famous solved problem. The statement "ZFC is consistent" is expressible in ZFC and unprovable in ZFC if the statement is true - that is the conclusion of Godel's incompleteness theorem. The statement is easy to disprove if false - just present the formal proof of any contradiction from the ZFC axioms.
$endgroup$
– Carl Mummert
Dec 10 '18 at 1:56
2
2
$begingroup$
And the statement "ZFC is consistent" IS a statement of the desired form: "For all natural numbers $n$, $n$ is not the code of a ZFC proof of the formula 0 = 1"
$endgroup$
– Ned
Dec 10 '18 at 2:33
$begingroup$
And the statement "ZFC is consistent" IS a statement of the desired form: "For all natural numbers $n$, $n$ is not the code of a ZFC proof of the formula 0 = 1"
$endgroup$
– Ned
Dec 10 '18 at 2:33
1
1
$begingroup$
"Can there be a consistent logical system in which such a statement cannot exist?" Godel's theorem (which always produces undecidable statements of the very simple sort you describe) does hold for a very general class of sufficiently strong formal systems. However, there are systems that are complete, even some quite natural ones. For example, Presberger arithmetic, and the theory of real closed fields.
$endgroup$
– spaceisdarkgreen
Dec 10 '18 at 3:57
$begingroup$
"Can there be a consistent logical system in which such a statement cannot exist?" Godel's theorem (which always produces undecidable statements of the very simple sort you describe) does hold for a very general class of sufficiently strong formal systems. However, there are systems that are complete, even some quite natural ones. For example, Presberger arithmetic, and the theory of real closed fields.
$endgroup$
– spaceisdarkgreen
Dec 10 '18 at 3:57
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As mentioned in the comments, "ZFC is consistent" is itself such a statement (once properly expressed in the language of set theory). We can do even better, though: the MRDP theorem (or rather, its proof) shows that (assuming ZFC is consistent) there is a Diophantine equation $P$ with no solutions, which ZFC cannot prove has no solutions. This is about as concrete as it gets!
So no, incompleteness manifests at even the most concrete levels of mathematical propositions.
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033315%2fundecidable-statement-that-doesnt-involve-infinity%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$
As mentioned in the comments, "ZFC is consistent" is itself such a statement (once properly expressed in the language of set theory). We can do even better, though: the MRDP theorem (or rather, its proof) shows that (assuming ZFC is consistent) there is a Diophantine equation $P$ with no solutions, which ZFC cannot prove has no solutions. This is about as concrete as it gets!
So no, incompleteness manifests at even the most concrete levels of mathematical propositions.
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
$begingroup$
As mentioned in the comments, "ZFC is consistent" is itself such a statement (once properly expressed in the language of set theory). We can do even better, though: the MRDP theorem (or rather, its proof) shows that (assuming ZFC is consistent) there is a Diophantine equation $P$ with no solutions, which ZFC cannot prove has no solutions. This is about as concrete as it gets!
So no, incompleteness manifests at even the most concrete levels of mathematical propositions.
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
$begingroup$
As mentioned in the comments, "ZFC is consistent" is itself such a statement (once properly expressed in the language of set theory). We can do even better, though: the MRDP theorem (or rather, its proof) shows that (assuming ZFC is consistent) there is a Diophantine equation $P$ with no solutions, which ZFC cannot prove has no solutions. This is about as concrete as it gets!
So no, incompleteness manifests at even the most concrete levels of mathematical propositions.
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
$endgroup$
As mentioned in the comments, "ZFC is consistent" is itself such a statement (once properly expressed in the language of set theory). We can do even better, though: the MRDP theorem (or rather, its proof) shows that (assuming ZFC is consistent) there is a Diophantine equation $P$ with no solutions, which ZFC cannot prove has no solutions. This is about as concrete as it gets!
So no, incompleteness manifests at even the most concrete levels of mathematical propositions.
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
answered Dec 10 '18 at 3:31
Noah SchweberNoah Schweber
125k10150287
125k10150287
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%2f3033315%2fundecidable-statement-that-doesnt-involve-infinity%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
3
$begingroup$
This is a famous solved problem. The statement "ZFC is consistent" is expressible in ZFC and unprovable in ZFC if the statement is true - that is the conclusion of Godel's incompleteness theorem. The statement is easy to disprove if false - just present the formal proof of any contradiction from the ZFC axioms.
$endgroup$
– Carl Mummert
Dec 10 '18 at 1:56
2
$begingroup$
And the statement "ZFC is consistent" IS a statement of the desired form: "For all natural numbers $n$, $n$ is not the code of a ZFC proof of the formula 0 = 1"
$endgroup$
– Ned
Dec 10 '18 at 2:33
1
$begingroup$
"Can there be a consistent logical system in which such a statement cannot exist?" Godel's theorem (which always produces undecidable statements of the very simple sort you describe) does hold for a very general class of sufficiently strong formal systems. However, there are systems that are complete, even some quite natural ones. For example, Presberger arithmetic, and the theory of real closed fields.
$endgroup$
– spaceisdarkgreen
Dec 10 '18 at 3:57