Difference between consistency and satisfiabilityClarifications on proof of compactness theoremRelationship between consistency, strong completeness and soundnessQuestion about the proof of consistency iff satisfiability of a theoryFinding Satisfiability, Unsatisfiability and Valid well formed formulaDifference between validity and satisfiability?Logic and consistencyProof of SatisfiabilityUnclear why (first order) satisfiability undecidable and not semi-decidable.Undecidability of first-order satisfiability problem?What is the difference between syntactic and semantic completeness?Satisfiability and validity in first-order logicWhat is the difference between validity and satisfiability?
Hygienic footwear for prehensile feet?
I made a mistake ordering ground coffee - will Expresso ground coffee work for a French Press?
Sucuri detects malware on wordpress but I can't find the malicious code
The term for the person/group a political party aligns themselves with to appear concerned about the general public
Is /home directory in root partition mapped to /home partition
Relativistic resistance transformation
Is this cancel button needed?
Is American Express widely accepted in France?
Pros and cons of writing a book review?
Restoring order in a deck of playing cards (II)
What does War Machine's "Canopy! Canopy!" line mean in "Avengers: Endgame"?
Why is Colorado so different politically from nearby states?
How to detach yourself from a character you're going to kill?
Can a magnetic field of a large body be stronger than its gravity?
Benefits of employing devices that support vlan trunking
What if you don't bring your credit card or debit for incidentals?
Why are grass strips more dangerous than tarmac?
Unorthodox way of solving Einstein field equations
Applicants clearly not having the skills they advertise
Credit card offering 0.5 miles for every cent rounded up. Too good to be true?
How is it possible for Mordenkainen to be alive during the Curse of Strahd adventure?
If a problem only occurs randomly once in every N times on average, how many tests do I have to perform to be certain that it's now fixed?
PhD student with mental health issues and bad performance
What is the best option to connect old computer to modern TV
Difference between consistency and satisfiability
Clarifications on proof of compactness theoremRelationship between consistency, strong completeness and soundnessQuestion about the proof of consistency iff satisfiability of a theoryFinding Satisfiability, Unsatisfiability and Valid well formed formulaDifference between validity and satisfiability?Logic and consistencyProof of SatisfiabilityUnclear why (first order) satisfiability undecidable and not semi-decidable.Undecidability of first-order satisfiability problem?What is the difference between syntactic and semantic completeness?Satisfiability and validity in first-order logicWhat is the difference between validity and satisfiability?
$begingroup$
If a set of formula is consistent, there exist a model in which every formula is true. This is only if the set is satisfiable.
But satisfiability is the fact that it can be true so what is the difference between the 2 notions ?
logic
$endgroup$
add a comment |
$begingroup$
If a set of formula is consistent, there exist a model in which every formula is true. This is only if the set is satisfiable.
But satisfiability is the fact that it can be true so what is the difference between the 2 notions ?
logic
$endgroup$
$begingroup$
Great question!
$endgroup$
– Pat Devlin
May 17 at 14:25
add a comment |
$begingroup$
If a set of formula is consistent, there exist a model in which every formula is true. This is only if the set is satisfiable.
But satisfiability is the fact that it can be true so what is the difference between the 2 notions ?
logic
$endgroup$
If a set of formula is consistent, there exist a model in which every formula is true. This is only if the set is satisfiable.
But satisfiability is the fact that it can be true so what is the difference between the 2 notions ?
logic
logic
asked May 17 at 13:14
Emma Vande WouwerEmma Vande Wouwer
332
332
$begingroup$
Great question!
$endgroup$
– Pat Devlin
May 17 at 14:25
add a comment |
$begingroup$
Great question!
$endgroup$
– Pat Devlin
May 17 at 14:25
$begingroup$
Great question!
$endgroup$
– Pat Devlin
May 17 at 14:25
$begingroup$
Great question!
$endgroup$
– Pat Devlin
May 17 at 14:25
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Consistency is a syntactic property. It means that there is no proof of contradiction from your axioms.
Satisfiability is a semantic property. It means that there is a model of the axioms.
In first-order logic (as well as propositional logic) the two notions are equivalent because the logic is sound and complete. Meaning a satisfiable theory is consistent, and a consistent theory is satisfiable.
Other logics, however, are not so lucky to have both of these properties and the two notions separate. In fact, if we do not assume the axiom of choice, then it is consistent that there is a theory which is consistent but not satisfiable.
$endgroup$
$begingroup$
Regarding the last point, I always feel like such issues are artifacts of allowing uncountable theories in the first place. What do you think?
$endgroup$
– user21820
May 17 at 16:44
$begingroup$
Well, it's true. If the language is countable, then choice is not necessary. But then you can argue that this requires $sf WKL_0$ over weaker theories, which are also considered "reasonable". So it's not just uncountability.
$endgroup$
– Asaf Karagila♦
May 17 at 16:45
$begingroup$
I don't find a similar issue with WKL because in some sense the notion that every arithmetic sentence has a boolean truth-value already presupposes that arithmetical properties are well-defined, and so ACA0 is well-justified once we assume PA is meaningful. What I find strange is that when we allow (in ZFC) a theory to have an uncountable language, we lose control over the theory if we lack a well-ordering of it, and a priori it's not clear that the axiom of choice is meaningful if we have full power-sets, yet it is reasonable if the intended universe is countable...
$endgroup$
– user21820
May 17 at 16:53
$begingroup$
Well, that's because uncountable things are unwieldy, which is why we need the axiom of choice to bring order to the universe of sets. If my memory serves me right, Shelah has a version of the completeness theorem in ZF and you need to require something like linear orders and that the cardinality of the language equals to its finite subsets, or finite sequences, or something like that. And then you can prove completeness without additional assumptions. This really shows you that the counterexamples I mention are very particular.
$endgroup$
– Asaf Karagila♦
May 17 at 16:58
$begingroup$
Oh I read that the completeness theorem is equivalent to BPIT, but I'd be curious if you can pull up a reference for what you just said.
$endgroup$
– user21820
May 17 at 17:02
|
show 1 more comment
$begingroup$
Consistency is defined syntactically :
a set $Gamma$ of formulas is inconsistent iff we can derive (in the proof system) a contradiction from it : $Gamma vdash bot$.
In this way, we prove that :
a set $Gamma$ is consistent iff it is satisfiable.
See also the post : Relationship between consistency, strong completeness and soundness.
$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%2f3229498%2fdifference-between-consistency-and-satisfiability%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$
Consistency is a syntactic property. It means that there is no proof of contradiction from your axioms.
Satisfiability is a semantic property. It means that there is a model of the axioms.
In first-order logic (as well as propositional logic) the two notions are equivalent because the logic is sound and complete. Meaning a satisfiable theory is consistent, and a consistent theory is satisfiable.
Other logics, however, are not so lucky to have both of these properties and the two notions separate. In fact, if we do not assume the axiom of choice, then it is consistent that there is a theory which is consistent but not satisfiable.
$endgroup$
$begingroup$
Regarding the last point, I always feel like such issues are artifacts of allowing uncountable theories in the first place. What do you think?
$endgroup$
– user21820
May 17 at 16:44
$begingroup$
Well, it's true. If the language is countable, then choice is not necessary. But then you can argue that this requires $sf WKL_0$ over weaker theories, which are also considered "reasonable". So it's not just uncountability.
$endgroup$
– Asaf Karagila♦
May 17 at 16:45
$begingroup$
I don't find a similar issue with WKL because in some sense the notion that every arithmetic sentence has a boolean truth-value already presupposes that arithmetical properties are well-defined, and so ACA0 is well-justified once we assume PA is meaningful. What I find strange is that when we allow (in ZFC) a theory to have an uncountable language, we lose control over the theory if we lack a well-ordering of it, and a priori it's not clear that the axiom of choice is meaningful if we have full power-sets, yet it is reasonable if the intended universe is countable...
$endgroup$
– user21820
May 17 at 16:53
$begingroup$
Well, that's because uncountable things are unwieldy, which is why we need the axiom of choice to bring order to the universe of sets. If my memory serves me right, Shelah has a version of the completeness theorem in ZF and you need to require something like linear orders and that the cardinality of the language equals to its finite subsets, or finite sequences, or something like that. And then you can prove completeness without additional assumptions. This really shows you that the counterexamples I mention are very particular.
$endgroup$
– Asaf Karagila♦
May 17 at 16:58
$begingroup$
Oh I read that the completeness theorem is equivalent to BPIT, but I'd be curious if you can pull up a reference for what you just said.
$endgroup$
– user21820
May 17 at 17:02
|
show 1 more comment
$begingroup$
Consistency is a syntactic property. It means that there is no proof of contradiction from your axioms.
Satisfiability is a semantic property. It means that there is a model of the axioms.
In first-order logic (as well as propositional logic) the two notions are equivalent because the logic is sound and complete. Meaning a satisfiable theory is consistent, and a consistent theory is satisfiable.
Other logics, however, are not so lucky to have both of these properties and the two notions separate. In fact, if we do not assume the axiom of choice, then it is consistent that there is a theory which is consistent but not satisfiable.
$endgroup$
$begingroup$
Regarding the last point, I always feel like such issues are artifacts of allowing uncountable theories in the first place. What do you think?
$endgroup$
– user21820
May 17 at 16:44
$begingroup$
Well, it's true. If the language is countable, then choice is not necessary. But then you can argue that this requires $sf WKL_0$ over weaker theories, which are also considered "reasonable". So it's not just uncountability.
$endgroup$
– Asaf Karagila♦
May 17 at 16:45
$begingroup$
I don't find a similar issue with WKL because in some sense the notion that every arithmetic sentence has a boolean truth-value already presupposes that arithmetical properties are well-defined, and so ACA0 is well-justified once we assume PA is meaningful. What I find strange is that when we allow (in ZFC) a theory to have an uncountable language, we lose control over the theory if we lack a well-ordering of it, and a priori it's not clear that the axiom of choice is meaningful if we have full power-sets, yet it is reasonable if the intended universe is countable...
$endgroup$
– user21820
May 17 at 16:53
$begingroup$
Well, that's because uncountable things are unwieldy, which is why we need the axiom of choice to bring order to the universe of sets. If my memory serves me right, Shelah has a version of the completeness theorem in ZF and you need to require something like linear orders and that the cardinality of the language equals to its finite subsets, or finite sequences, or something like that. And then you can prove completeness without additional assumptions. This really shows you that the counterexamples I mention are very particular.
$endgroup$
– Asaf Karagila♦
May 17 at 16:58
$begingroup$
Oh I read that the completeness theorem is equivalent to BPIT, but I'd be curious if you can pull up a reference for what you just said.
$endgroup$
– user21820
May 17 at 17:02
|
show 1 more comment
$begingroup$
Consistency is a syntactic property. It means that there is no proof of contradiction from your axioms.
Satisfiability is a semantic property. It means that there is a model of the axioms.
In first-order logic (as well as propositional logic) the two notions are equivalent because the logic is sound and complete. Meaning a satisfiable theory is consistent, and a consistent theory is satisfiable.
Other logics, however, are not so lucky to have both of these properties and the two notions separate. In fact, if we do not assume the axiom of choice, then it is consistent that there is a theory which is consistent but not satisfiable.
$endgroup$
Consistency is a syntactic property. It means that there is no proof of contradiction from your axioms.
Satisfiability is a semantic property. It means that there is a model of the axioms.
In first-order logic (as well as propositional logic) the two notions are equivalent because the logic is sound and complete. Meaning a satisfiable theory is consistent, and a consistent theory is satisfiable.
Other logics, however, are not so lucky to have both of these properties and the two notions separate. In fact, if we do not assume the axiom of choice, then it is consistent that there is a theory which is consistent but not satisfiable.
answered May 17 at 13:24
Asaf Karagila♦Asaf Karagila
311k33445777
311k33445777
$begingroup$
Regarding the last point, I always feel like such issues are artifacts of allowing uncountable theories in the first place. What do you think?
$endgroup$
– user21820
May 17 at 16:44
$begingroup$
Well, it's true. If the language is countable, then choice is not necessary. But then you can argue that this requires $sf WKL_0$ over weaker theories, which are also considered "reasonable". So it's not just uncountability.
$endgroup$
– Asaf Karagila♦
May 17 at 16:45
$begingroup$
I don't find a similar issue with WKL because in some sense the notion that every arithmetic sentence has a boolean truth-value already presupposes that arithmetical properties are well-defined, and so ACA0 is well-justified once we assume PA is meaningful. What I find strange is that when we allow (in ZFC) a theory to have an uncountable language, we lose control over the theory if we lack a well-ordering of it, and a priori it's not clear that the axiom of choice is meaningful if we have full power-sets, yet it is reasonable if the intended universe is countable...
$endgroup$
– user21820
May 17 at 16:53
$begingroup$
Well, that's because uncountable things are unwieldy, which is why we need the axiom of choice to bring order to the universe of sets. If my memory serves me right, Shelah has a version of the completeness theorem in ZF and you need to require something like linear orders and that the cardinality of the language equals to its finite subsets, or finite sequences, or something like that. And then you can prove completeness without additional assumptions. This really shows you that the counterexamples I mention are very particular.
$endgroup$
– Asaf Karagila♦
May 17 at 16:58
$begingroup$
Oh I read that the completeness theorem is equivalent to BPIT, but I'd be curious if you can pull up a reference for what you just said.
$endgroup$
– user21820
May 17 at 17:02
|
show 1 more comment
$begingroup$
Regarding the last point, I always feel like such issues are artifacts of allowing uncountable theories in the first place. What do you think?
$endgroup$
– user21820
May 17 at 16:44
$begingroup$
Well, it's true. If the language is countable, then choice is not necessary. But then you can argue that this requires $sf WKL_0$ over weaker theories, which are also considered "reasonable". So it's not just uncountability.
$endgroup$
– Asaf Karagila♦
May 17 at 16:45
$begingroup$
I don't find a similar issue with WKL because in some sense the notion that every arithmetic sentence has a boolean truth-value already presupposes that arithmetical properties are well-defined, and so ACA0 is well-justified once we assume PA is meaningful. What I find strange is that when we allow (in ZFC) a theory to have an uncountable language, we lose control over the theory if we lack a well-ordering of it, and a priori it's not clear that the axiom of choice is meaningful if we have full power-sets, yet it is reasonable if the intended universe is countable...
$endgroup$
– user21820
May 17 at 16:53
$begingroup$
Well, that's because uncountable things are unwieldy, which is why we need the axiom of choice to bring order to the universe of sets. If my memory serves me right, Shelah has a version of the completeness theorem in ZF and you need to require something like linear orders and that the cardinality of the language equals to its finite subsets, or finite sequences, or something like that. And then you can prove completeness without additional assumptions. This really shows you that the counterexamples I mention are very particular.
$endgroup$
– Asaf Karagila♦
May 17 at 16:58
$begingroup$
Oh I read that the completeness theorem is equivalent to BPIT, but I'd be curious if you can pull up a reference for what you just said.
$endgroup$
– user21820
May 17 at 17:02
$begingroup$
Regarding the last point, I always feel like such issues are artifacts of allowing uncountable theories in the first place. What do you think?
$endgroup$
– user21820
May 17 at 16:44
$begingroup$
Regarding the last point, I always feel like such issues are artifacts of allowing uncountable theories in the first place. What do you think?
$endgroup$
– user21820
May 17 at 16:44
$begingroup$
Well, it's true. If the language is countable, then choice is not necessary. But then you can argue that this requires $sf WKL_0$ over weaker theories, which are also considered "reasonable". So it's not just uncountability.
$endgroup$
– Asaf Karagila♦
May 17 at 16:45
$begingroup$
Well, it's true. If the language is countable, then choice is not necessary. But then you can argue that this requires $sf WKL_0$ over weaker theories, which are also considered "reasonable". So it's not just uncountability.
$endgroup$
– Asaf Karagila♦
May 17 at 16:45
$begingroup$
I don't find a similar issue with WKL because in some sense the notion that every arithmetic sentence has a boolean truth-value already presupposes that arithmetical properties are well-defined, and so ACA0 is well-justified once we assume PA is meaningful. What I find strange is that when we allow (in ZFC) a theory to have an uncountable language, we lose control over the theory if we lack a well-ordering of it, and a priori it's not clear that the axiom of choice is meaningful if we have full power-sets, yet it is reasonable if the intended universe is countable...
$endgroup$
– user21820
May 17 at 16:53
$begingroup$
I don't find a similar issue with WKL because in some sense the notion that every arithmetic sentence has a boolean truth-value already presupposes that arithmetical properties are well-defined, and so ACA0 is well-justified once we assume PA is meaningful. What I find strange is that when we allow (in ZFC) a theory to have an uncountable language, we lose control over the theory if we lack a well-ordering of it, and a priori it's not clear that the axiom of choice is meaningful if we have full power-sets, yet it is reasonable if the intended universe is countable...
$endgroup$
– user21820
May 17 at 16:53
$begingroup$
Well, that's because uncountable things are unwieldy, which is why we need the axiom of choice to bring order to the universe of sets. If my memory serves me right, Shelah has a version of the completeness theorem in ZF and you need to require something like linear orders and that the cardinality of the language equals to its finite subsets, or finite sequences, or something like that. And then you can prove completeness without additional assumptions. This really shows you that the counterexamples I mention are very particular.
$endgroup$
– Asaf Karagila♦
May 17 at 16:58
$begingroup$
Well, that's because uncountable things are unwieldy, which is why we need the axiom of choice to bring order to the universe of sets. If my memory serves me right, Shelah has a version of the completeness theorem in ZF and you need to require something like linear orders and that the cardinality of the language equals to its finite subsets, or finite sequences, or something like that. And then you can prove completeness without additional assumptions. This really shows you that the counterexamples I mention are very particular.
$endgroup$
– Asaf Karagila♦
May 17 at 16:58
$begingroup$
Oh I read that the completeness theorem is equivalent to BPIT, but I'd be curious if you can pull up a reference for what you just said.
$endgroup$
– user21820
May 17 at 17:02
$begingroup$
Oh I read that the completeness theorem is equivalent to BPIT, but I'd be curious if you can pull up a reference for what you just said.
$endgroup$
– user21820
May 17 at 17:02
|
show 1 more comment
$begingroup$
Consistency is defined syntactically :
a set $Gamma$ of formulas is inconsistent iff we can derive (in the proof system) a contradiction from it : $Gamma vdash bot$.
In this way, we prove that :
a set $Gamma$ is consistent iff it is satisfiable.
See also the post : Relationship between consistency, strong completeness and soundness.
$endgroup$
add a comment |
$begingroup$
Consistency is defined syntactically :
a set $Gamma$ of formulas is inconsistent iff we can derive (in the proof system) a contradiction from it : $Gamma vdash bot$.
In this way, we prove that :
a set $Gamma$ is consistent iff it is satisfiable.
See also the post : Relationship between consistency, strong completeness and soundness.
$endgroup$
add a comment |
$begingroup$
Consistency is defined syntactically :
a set $Gamma$ of formulas is inconsistent iff we can derive (in the proof system) a contradiction from it : $Gamma vdash bot$.
In this way, we prove that :
a set $Gamma$ is consistent iff it is satisfiable.
See also the post : Relationship between consistency, strong completeness and soundness.
$endgroup$
Consistency is defined syntactically :
a set $Gamma$ of formulas is inconsistent iff we can derive (in the proof system) a contradiction from it : $Gamma vdash bot$.
In this way, we prove that :
a set $Gamma$ is consistent iff it is satisfiable.
See also the post : Relationship between consistency, strong completeness and soundness.
edited May 18 at 10:08
answered May 17 at 13:24
Mauro ALLEGRANZAMauro ALLEGRANZA
69.1k449118
69.1k449118
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%2f3229498%2fdifference-between-consistency-and-satisfiability%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$
Great question!
$endgroup$
– Pat Devlin
May 17 at 14:25