Is it possible to prove consistency of an axiomatic system without providing a model?
1
$begingroup$
Providing concrete models is more-or-less impossible, since we are not sure about many things in real world. On the other side, abstract models are usually insufficient for proving consistency, since the consistency of the other axiomatic system (which we have constructed the model in) needs to be proved first and the problem arises again!
Another method is to count all theorems of the system and make sure that they do not contradict.
So I have two questions:
- Can an axiomatic system be proposed whose theorems can be counted completely? Do you know an example?
- Is there another method to prove absolute consistency of an axiomatic system without providing a model? If no, why not? And if yes, may you please provide an example?
proof-theory
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
$endgroup$
add a comment |
1
$begingroup$
Providing concrete models is more-or-less impossible, since we are not sure about many things in real world. On the other side, abstract models are usually insufficient for proving consistency, since the consistency of the other axiomatic system (which we have constructed the model in) needs to be proved first and the problem arises again!
Another method is to count all theorems of the system and make sure that they do not contradict.
So I have two questions:
- Can an axiomatic system be proposed whose theorems can be counted completely? Do you know an example?
- Is there another method to prove absolute consistency of an axiomatic system without providing a model? If no, why not? And if yes, may you please provide an example?
proof-theory
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
$endgroup$
$begingroup$
Yes; see Gentzen's consistency proof and see Proof theory.
$endgroup$
– Mauro ALLEGRANZA
Dec 6 '18 at 9:45
$begingroup$
Thanks @MauroALLEGRANZA, but Gentzen's proof does not yet prove absolute consistency. Yes? And what about the first question? Can all theorems of a theory be counted to ensure its consistency?
$endgroup$
– Hamid Haghshenas
Dec 8 '18 at 14:58
$begingroup$
@HamidHaghshenas Nothing proves absolute consistency: even with a model "in hand," we need some ambient framework to verify that the structure is, in fact, a model (and to prove the soundness theorem, for that matter!). As to the first question, you're just asking about decidable theories, and there are lots of those - e.g. Presburger arithmetic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 18:56
$begingroup$
@NoahSchweber Helpful, thanks. In a decidable theory, if the algorithm tells us that a proposition is provable but its negation is not, can it be said that we have a proof of consistency of the theory?
$endgroup$
– Hamid Haghshenas
Dec 10 '18 at 6:14
$begingroup$
@HamidHaghshenas Only if we also have a proof that the algorithm behaves correctly. But if so, yes.
$endgroup$
– Noah Schweber
Dec 10 '18 at 14:53
add a comment |
1
1
1
$begingroup$
Providing concrete models is more-or-less impossible, since we are not sure about many things in real world. On the other side, abstract models are usually insufficient for proving consistency, since the consistency of the other axiomatic system (which we have constructed the model in) needs to be proved first and the problem arises again!
Another method is to count all theorems of the system and make sure that they do not contradict.
So I have two questions:
- Can an axiomatic system be proposed whose theorems can be counted completely? Do you know an example?
- Is there another method to prove absolute consistency of an axiomatic system without providing a model? If no, why not? And if yes, may you please provide an example?
proof-theory
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
$endgroup$
Providing concrete models is more-or-less impossible, since we are not sure about many things in real world. On the other side, abstract models are usually insufficient for proving consistency, since the consistency of the other axiomatic system (which we have constructed the model in) needs to be proved first and the problem arises again!
Another method is to count all theorems of the system and make sure that they do not contradict.
So I have two questions:
- Can an axiomatic system be proposed whose theorems can be counted completely? Do you know an example?
- Is there another method to prove absolute consistency of an axiomatic system without providing a model? If no, why not? And if yes, may you please provide an example?
proof-theory
proof-theory
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
asked Dec 6 '18 at 9:40
Hamid HaghshenasHamid Haghshenas
62
62
$begingroup$
Yes; see Gentzen's consistency proof and see Proof theory.
$endgroup$
– Mauro ALLEGRANZA
Dec 6 '18 at 9:45
$begingroup$
Thanks @MauroALLEGRANZA, but Gentzen's proof does not yet prove absolute consistency. Yes? And what about the first question? Can all theorems of a theory be counted to ensure its consistency?
$endgroup$
– Hamid Haghshenas
Dec 8 '18 at 14:58
$begingroup$
@HamidHaghshenas Nothing proves absolute consistency: even with a model "in hand," we need some ambient framework to verify that the structure is, in fact, a model (and to prove the soundness theorem, for that matter!). As to the first question, you're just asking about decidable theories, and there are lots of those - e.g. Presburger arithmetic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 18:56
$begingroup$
@NoahSchweber Helpful, thanks. In a decidable theory, if the algorithm tells us that a proposition is provable but its negation is not, can it be said that we have a proof of consistency of the theory?
$endgroup$
– Hamid Haghshenas
Dec 10 '18 at 6:14
$begingroup$
@HamidHaghshenas Only if we also have a proof that the algorithm behaves correctly. But if so, yes.
$endgroup$
– Noah Schweber
Dec 10 '18 at 14:53
add a comment |
$begingroup$
Yes; see Gentzen's consistency proof and see Proof theory.
$endgroup$
– Mauro ALLEGRANZA
Dec 6 '18 at 9:45
$begingroup$
Thanks @MauroALLEGRANZA, but Gentzen's proof does not yet prove absolute consistency. Yes? And what about the first question? Can all theorems of a theory be counted to ensure its consistency?
$endgroup$
– Hamid Haghshenas
Dec 8 '18 at 14:58
$begingroup$
@HamidHaghshenas Nothing proves absolute consistency: even with a model "in hand," we need some ambient framework to verify that the structure is, in fact, a model (and to prove the soundness theorem, for that matter!). As to the first question, you're just asking about decidable theories, and there are lots of those - e.g. Presburger arithmetic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 18:56
$begingroup$
@NoahSchweber Helpful, thanks. In a decidable theory, if the algorithm tells us that a proposition is provable but its negation is not, can it be said that we have a proof of consistency of the theory?
$endgroup$
– Hamid Haghshenas
Dec 10 '18 at 6:14
$begingroup$
@HamidHaghshenas Only if we also have a proof that the algorithm behaves correctly. But if so, yes.
$endgroup$
– Noah Schweber
Dec 10 '18 at 14:53
$begingroup$
Yes; see Gentzen's consistency proof and see Proof theory.
$endgroup$
– Mauro ALLEGRANZA
Dec 6 '18 at 9:45
$begingroup$
Yes; see Gentzen's consistency proof and see Proof theory.
$endgroup$
– Mauro ALLEGRANZA
Dec 6 '18 at 9:45
$begingroup$
Thanks @MauroALLEGRANZA, but Gentzen's proof does not yet prove absolute consistency. Yes? And what about the first question? Can all theorems of a theory be counted to ensure its consistency?
$endgroup$
– Hamid Haghshenas
Dec 8 '18 at 14:58
$begingroup$
Thanks @MauroALLEGRANZA, but Gentzen's proof does not yet prove absolute consistency. Yes? And what about the first question? Can all theorems of a theory be counted to ensure its consistency?
$endgroup$
– Hamid Haghshenas
Dec 8 '18 at 14:58
$begingroup$
@HamidHaghshenas Nothing proves absolute consistency: even with a model "in hand," we need some ambient framework to verify that the structure is, in fact, a model (and to prove the soundness theorem, for that matter!). As to the first question, you're just asking about decidable theories, and there are lots of those - e.g. Presburger arithmetic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 18:56
$begingroup$
@HamidHaghshenas Nothing proves absolute consistency: even with a model "in hand," we need some ambient framework to verify that the structure is, in fact, a model (and to prove the soundness theorem, for that matter!). As to the first question, you're just asking about decidable theories, and there are lots of those - e.g. Presburger arithmetic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 18:56
$begingroup$
@NoahSchweber Helpful, thanks. In a decidable theory, if the algorithm tells us that a proposition is provable but its negation is not, can it be said that we have a proof of consistency of the theory?
$endgroup$
– Hamid Haghshenas
Dec 10 '18 at 6:14
$begingroup$
@NoahSchweber Helpful, thanks. In a decidable theory, if the algorithm tells us that a proposition is provable but its negation is not, can it be said that we have a proof of consistency of the theory?
$endgroup$
– Hamid Haghshenas
Dec 10 '18 at 6:14
$begingroup$
@HamidHaghshenas Only if we also have a proof that the algorithm behaves correctly. But if so, yes.
$endgroup$
– Noah Schweber
Dec 10 '18 at 14:53
$begingroup$
@HamidHaghshenas Only if we also have a proof that the algorithm behaves correctly. But if so, yes.
$endgroup$
– Noah Schweber
Dec 10 '18 at 14:53
add a comment |
0
active
oldest
votes
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
});
}
});
draft saved
draft discarded
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%2f3028275%2fis-it-possible-to-prove-consistency-of-an-axiomatic-system-without-providing-a-m%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3028275%2fis-it-possible-to-prove-consistency-of-an-axiomatic-system-without-providing-a-m%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$
Yes; see Gentzen's consistency proof and see Proof theory.
$endgroup$
– Mauro ALLEGRANZA
Dec 6 '18 at 9:45
$begingroup$
Thanks @MauroALLEGRANZA, but Gentzen's proof does not yet prove absolute consistency. Yes? And what about the first question? Can all theorems of a theory be counted to ensure its consistency?
$endgroup$
– Hamid Haghshenas
Dec 8 '18 at 14:58
$begingroup$
@HamidHaghshenas Nothing proves absolute consistency: even with a model "in hand," we need some ambient framework to verify that the structure is, in fact, a model (and to prove the soundness theorem, for that matter!). As to the first question, you're just asking about decidable theories, and there are lots of those - e.g. Presburger arithmetic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 18:56
$begingroup$
@NoahSchweber Helpful, thanks. In a decidable theory, if the algorithm tells us that a proposition is provable but its negation is not, can it be said that we have a proof of consistency of the theory?
$endgroup$
– Hamid Haghshenas
Dec 10 '18 at 6:14
$begingroup$
@HamidHaghshenas Only if we also have a proof that the algorithm behaves correctly. But if so, yes.
$endgroup$
– Noah Schweber
Dec 10 '18 at 14:53