If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.
$begingroup$
This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:
Let $Sigma$ a set of sentences and $phi$ a sentence.
If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.
The proof by contradiction reads:
"If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."
How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?
From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?
logic first-order-logic model-theory
$endgroup$
add a comment |
$begingroup$
This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:
Let $Sigma$ a set of sentences and $phi$ a sentence.
If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.
The proof by contradiction reads:
"If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."
How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?
From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?
logic first-order-logic model-theory
$endgroup$
add a comment |
$begingroup$
This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:
Let $Sigma$ a set of sentences and $phi$ a sentence.
If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.
The proof by contradiction reads:
"If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."
How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?
From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?
logic first-order-logic model-theory
$endgroup$
This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:
Let $Sigma$ a set of sentences and $phi$ a sentence.
If $Sigma models phi$, then for some finite $Delta subsetSigma$, $Delta models phi$.
The proof by contradiction reads:
"If $phi$ does not logically follow from some $Delta subset Sigma$, then the set $Sigma cup {neg phi}$ is finitely satisfiable and therefore, by compactness, satisfiable."
How do we know that $Sigma cup {neg phi}$ is finitely satisfiable?
From the fact that $phi$ does not logically follow from some $Delta$, we know that $neg phi$ follows from every $Delta subset Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?
logic first-order-logic model-theory
logic first-order-logic model-theory
asked Dec 8 '18 at 20:07
MikeMike
709415
709415
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.
What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)
This is in fact the crux of the problem!
Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).
All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"
Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).
$endgroup$
add a comment |
$begingroup$
My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:
If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).
$endgroup$
$begingroup$
To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:28
$begingroup$
@NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
$endgroup$
– Mike
Dec 8 '18 at 20:31
$begingroup$
@Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:32
$begingroup$
@NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
$endgroup$
– Mike
Dec 8 '18 at 20:36
$begingroup$
@NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
$endgroup$
– Henning Makholm
Dec 8 '18 at 20:51
|
show 5 more comments
$begingroup$
Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$
$endgroup$
1
$begingroup$
So does Doets assume that $Sigma$ has a model?
$endgroup$
– Mike
Dec 8 '18 at 20:32
$begingroup$
If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
$endgroup$
– Holo
Dec 8 '18 at 20:35
$begingroup$
@Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:38
$begingroup$
@NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
$endgroup$
– Holo
Dec 8 '18 at 20:50
$begingroup$
@Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:51
|
show 1 more 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%2f3031577%2fif-sigma-models-phi-then-for-some-finite-delta-subset-sigma-delta%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.
What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)
This is in fact the crux of the problem!
Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).
All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"
Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).
$endgroup$
add a comment |
$begingroup$
First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.
What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)
This is in fact the crux of the problem!
Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).
All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"
Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).
$endgroup$
add a comment |
$begingroup$
First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.
What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)
This is in fact the crux of the problem!
Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).
All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"
Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).
$endgroup$
First, a quick comment. Your statement "From the fact that $varphi$ does not logically follow from some $Delta$, we know that $negvarphi$ follows from every $Deltasubseteq Sigma$." is incorrect: when $A$ is a set of sentences, "$Anotmodels b$" is different from "$Amodelsneg b$." We could have $b$ be independent of $A$ - that is, $Anotmodels b$ and $Anotmodelsneg b$.
What is true is that since $varphi$ isn't entailed by any finite $DeltasubseteqSigma$, $negvarphi$ must be compatible with every finite $DeltasubseteqSigma$ in the sense that, for every $DeltasubseteqSigma$, the set $Deltacup{negvarphi}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)
This is in fact the crux of the problem!
Saying "$Sigmacup{negvarphi}$ is finitely satisfiable" just means "$Deltacup{negvarphi}$ is satisfiable for every finite $DeltasubseteqSigma$." But "$Deltacup{negvarphi}$ is satisfiable" just means "there is some model of $Deltacup{negvarphi}$," which is to say $$Deltanotmodelsvarphi$$ ("$Deltamodelsvarphi$" means exactly "every model of $Delta$ satisfies $varphi$," which can't be true if there is some model of $Deltacup{negvarphi}$).
All that is to say that the statement "$Sigmacup{negvarphi}$ is finitely satisfiable" is equivalent to "For every finite $DeltasubseteqSigma$, we have $Deltanotmodelsvarphi$." But this latter statement is precisely our hypothesis "$varphi$ does not logically follow from some [finite] $DeltasubseteqSigma$!"
Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($models$), not the syntactic sense ($vdash$).
answered Dec 8 '18 at 20:45
Noah SchweberNoah Schweber
123k10150286
123k10150286
add a comment |
add a comment |
$begingroup$
My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:
If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).
$endgroup$
$begingroup$
To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:28
$begingroup$
@NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
$endgroup$
– Mike
Dec 8 '18 at 20:31
$begingroup$
@Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:32
$begingroup$
@NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
$endgroup$
– Mike
Dec 8 '18 at 20:36
$begingroup$
@NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
$endgroup$
– Henning Makholm
Dec 8 '18 at 20:51
|
show 5 more comments
$begingroup$
My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:
If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).
$endgroup$
$begingroup$
To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:28
$begingroup$
@NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
$endgroup$
– Mike
Dec 8 '18 at 20:31
$begingroup$
@Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:32
$begingroup$
@NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
$endgroup$
– Mike
Dec 8 '18 at 20:36
$begingroup$
@NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
$endgroup$
– Henning Makholm
Dec 8 '18 at 20:51
|
show 5 more comments
$begingroup$
My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:
If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).
$endgroup$
My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:
If $SigmavDashphi$, then there is a proof of $Sigmavdashphi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $Sigma$. Therefore the same proof proves $Deltavdashphi$ for some finite $DeltasubseteqSigma$, and thus $DeltavDashphi$ (soundness).
answered Dec 8 '18 at 20:14
Henning MakholmHenning Makholm
240k17305541
240k17305541
$begingroup$
To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:28
$begingroup$
@NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
$endgroup$
– Mike
Dec 8 '18 at 20:31
$begingroup$
@Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:32
$begingroup$
@NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
$endgroup$
– Mike
Dec 8 '18 at 20:36
$begingroup$
@NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
$endgroup$
– Henning Makholm
Dec 8 '18 at 20:51
|
show 5 more comments
$begingroup$
To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:28
$begingroup$
@NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
$endgroup$
– Mike
Dec 8 '18 at 20:31
$begingroup$
@Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:32
$begingroup$
@NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
$endgroup$
– Mike
Dec 8 '18 at 20:36
$begingroup$
@NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
$endgroup$
– Henning Makholm
Dec 8 '18 at 20:51
$begingroup$
To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:28
$begingroup$
To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:28
$begingroup$
@NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
$endgroup$
– Mike
Dec 8 '18 at 20:31
$begingroup$
@NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now?
$endgroup$
– Mike
Dec 8 '18 at 20:31
$begingroup$
@Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:32
$begingroup$
@Craig You have things backwards. "$models$" is a purely semantic notion ($Sigmamodelsvarphi$ iff every model of $Sigma$ satisfies $varphi$); "$vdash$" is syntactic ($Sigmavdashvarphi$ iff there is a proof of $varphi$ from $Sigma$). Since the problem involves only "$models$," it is (a priori) purely semantic.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:32
$begingroup$
@NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
$endgroup$
– Mike
Dec 8 '18 at 20:36
$begingroup$
@NoahSchweber Ohhh, I thought that $models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks.
$endgroup$
– Mike
Dec 8 '18 at 20:36
$begingroup$
@NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
$endgroup$
– Henning Makholm
Dec 8 '18 at 20:51
$begingroup$
@NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ...
$endgroup$
– Henning Makholm
Dec 8 '18 at 20:51
|
show 5 more comments
$begingroup$
Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$
$endgroup$
1
$begingroup$
So does Doets assume that $Sigma$ has a model?
$endgroup$
– Mike
Dec 8 '18 at 20:32
$begingroup$
If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
$endgroup$
– Holo
Dec 8 '18 at 20:35
$begingroup$
@Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:38
$begingroup$
@NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
$endgroup$
– Holo
Dec 8 '18 at 20:50
$begingroup$
@Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:51
|
show 1 more comment
$begingroup$
Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$
$endgroup$
1
$begingroup$
So does Doets assume that $Sigma$ has a model?
$endgroup$
– Mike
Dec 8 '18 at 20:32
$begingroup$
If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
$endgroup$
– Holo
Dec 8 '18 at 20:35
$begingroup$
@Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:38
$begingroup$
@NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
$endgroup$
– Holo
Dec 8 '18 at 20:50
$begingroup$
@Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:51
|
show 1 more comment
$begingroup$
Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$
$endgroup$
Every $Delta$ finite have $DeltavDashlnotvarphi$, so every model of $Delta$ is a model of $Deltacup{lnotvarphi}$, and there is a model for every $Delta$, namely, the model of $Sigma$
answered Dec 8 '18 at 20:17
HoloHolo
5,73121031
5,73121031
1
$begingroup$
So does Doets assume that $Sigma$ has a model?
$endgroup$
– Mike
Dec 8 '18 at 20:32
$begingroup$
If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
$endgroup$
– Holo
Dec 8 '18 at 20:35
$begingroup$
@Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:38
$begingroup$
@NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
$endgroup$
– Holo
Dec 8 '18 at 20:50
$begingroup$
@Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:51
|
show 1 more comment
1
$begingroup$
So does Doets assume that $Sigma$ has a model?
$endgroup$
– Mike
Dec 8 '18 at 20:32
$begingroup$
If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
$endgroup$
– Holo
Dec 8 '18 at 20:35
$begingroup$
@Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:38
$begingroup$
@NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
$endgroup$
– Holo
Dec 8 '18 at 20:50
$begingroup$
@Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:51
1
1
$begingroup$
So does Doets assume that $Sigma$ has a model?
$endgroup$
– Mike
Dec 8 '18 at 20:32
$begingroup$
So does Doets assume that $Sigma$ has a model?
$endgroup$
– Mike
Dec 8 '18 at 20:32
$begingroup$
If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
$endgroup$
– Holo
Dec 8 '18 at 20:35
$begingroup$
If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction, take $Delta$ be all the elements of $Sigma$ that appear in that sequence and you got a finite subset of $Sigma$ that proves $varphi$
$endgroup$
– Holo
Dec 8 '18 at 20:35
$begingroup$
@Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:38
$begingroup$
@Holo "If there is no model to $Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:38
$begingroup$
@NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
$endgroup$
– Holo
Dec 8 '18 at 20:50
$begingroup$
@NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
$endgroup$
– Holo
Dec 8 '18 at 20:50
$begingroup$
@Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:51
$begingroup$
@Holo I disagree - $vdash$ isn't needed at all, this is just a direct application of the basic definition of $models$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 20:51
|
show 1 more 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%2f3031577%2fif-sigma-models-phi-then-for-some-finite-delta-subset-sigma-delta%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