Two conflicting (?) versions of the Downward Löwenheim-Skolem Theorem
$begingroup$
I found two definitions of the Downward Löwenheim-Skolem Theorem:
Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
infinite.
From Zach et al.
Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.
From Weiss et al.
What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".
Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?
Looking forward to the responses 😊.
logic first-order-logic model-theory
$endgroup$
add a comment |
$begingroup$
I found two definitions of the Downward Löwenheim-Skolem Theorem:
Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
infinite.
From Zach et al.
Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.
From Weiss et al.
What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".
Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?
Looking forward to the responses 😊.
logic first-order-logic model-theory
$endgroup$
add a comment |
$begingroup$
I found two definitions of the Downward Löwenheim-Skolem Theorem:
Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
infinite.
From Zach et al.
Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.
From Weiss et al.
What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".
Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?
Looking forward to the responses 😊.
logic first-order-logic model-theory
$endgroup$
I found two definitions of the Downward Löwenheim-Skolem Theorem:
Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably
infinite.
From Zach et al.
Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.
From Weiss et al.
What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".
Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?
Looking forward to the responses 😊.
logic first-order-logic model-theory
logic first-order-logic model-theory
edited Jan 26 at 13:39
Rafael Bankosegger
asked Jan 26 at 12:08
Rafael BankoseggerRafael Bankosegger
595
595
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.
Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.
With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.
In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.
From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.
Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.
Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.
I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.
$endgroup$
$begingroup$
In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
$endgroup$
– Berci
Jan 26 at 12:30
$begingroup$
@Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
$endgroup$
– Max
Jan 26 at 12:53
7
$begingroup$
This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
$endgroup$
– Carl Mummert
Jan 26 at 13:13
5
$begingroup$
Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
$endgroup$
– Carl Mummert
Jan 26 at 13:17
$begingroup$
@CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
$endgroup$
– Max
Jan 26 at 13:19
|
show 2 more comments
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%2f3088179%2ftwo-conflicting-versions-of-the-downward-l%25c3%25b6wenheim-skolem-theorem%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$
Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.
Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.
With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.
In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.
From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.
Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.
Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.
I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.
$endgroup$
$begingroup$
In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
$endgroup$
– Berci
Jan 26 at 12:30
$begingroup$
@Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
$endgroup$
– Max
Jan 26 at 12:53
7
$begingroup$
This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
$endgroup$
– Carl Mummert
Jan 26 at 13:13
5
$begingroup$
Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
$endgroup$
– Carl Mummert
Jan 26 at 13:17
$begingroup$
@CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
$endgroup$
– Max
Jan 26 at 13:19
|
show 2 more comments
$begingroup$
Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.
Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.
With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.
In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.
From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.
Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.
Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.
I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.
$endgroup$
$begingroup$
In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
$endgroup$
– Berci
Jan 26 at 12:30
$begingroup$
@Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
$endgroup$
– Max
Jan 26 at 12:53
7
$begingroup$
This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
$endgroup$
– Carl Mummert
Jan 26 at 13:13
5
$begingroup$
Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
$endgroup$
– Carl Mummert
Jan 26 at 13:17
$begingroup$
@CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
$endgroup$
– Max
Jan 26 at 13:19
|
show 2 more comments
$begingroup$
Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.
Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.
With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.
In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.
From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.
Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.
Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.
I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.
$endgroup$
Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.
Note that, as stated, version 2 is also false, $kappa$ needs to be assumed to be infinite for it to be true.
With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.
In this case the first version becomes true, and the second one becomes : if $B$ is an $mathscr{L}$-structure and $kappa$ an infinite cardinal, $kappaleq |B|$ then $B$ has an elementary substructure of size $kappa$.
From this we may deduce the first version by simply saying : if $Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $kappa = aleph_0$.
Since $B$ is a model of $Gamma$, any elementary substructure is also a model of $Gamma$, so we get a countable model and we are done.
Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.
I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.
answered Jan 26 at 12:23
MaxMax
15.5k11143
15.5k11143
$begingroup$
In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
$endgroup$
– Berci
Jan 26 at 12:30
$begingroup$
@Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
$endgroup$
– Max
Jan 26 at 12:53
7
$begingroup$
This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
$endgroup$
– Carl Mummert
Jan 26 at 13:13
5
$begingroup$
Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
$endgroup$
– Carl Mummert
Jan 26 at 13:17
$begingroup$
@CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
$endgroup$
– Max
Jan 26 at 13:19
|
show 2 more comments
$begingroup$
In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
$endgroup$
– Berci
Jan 26 at 12:30
$begingroup$
@Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
$endgroup$
– Max
Jan 26 at 12:53
7
$begingroup$
This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
$endgroup$
– Carl Mummert
Jan 26 at 13:13
5
$begingroup$
Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
$endgroup$
– Carl Mummert
Jan 26 at 13:17
$begingroup$
@CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
$endgroup$
– Max
Jan 26 at 13:19
$begingroup$
In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
$endgroup$
– Berci
Jan 26 at 12:30
$begingroup$
In def.2 $kappa$ is assumed to be $ge |mathcal L|$, so it must be infinite.
$endgroup$
– Berci
Jan 26 at 12:30
$begingroup$
@Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
$endgroup$
– Max
Jan 26 at 12:53
$begingroup$
@Berci : it depends on the definition of $|mathscr{L}|$; but if you say that $|mathscr{L}|$ must be infinite then yes
$endgroup$
– Max
Jan 26 at 12:53
7
7
$begingroup$
This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
$endgroup$
– Carl Mummert
Jan 26 at 13:13
$begingroup$
This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match.
$endgroup$
– Carl Mummert
Jan 26 at 13:13
5
5
$begingroup$
Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
$endgroup$
– Carl Mummert
Jan 26 at 13:17
$begingroup$
Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/…
$endgroup$
– Carl Mummert
Jan 26 at 13:17
$begingroup$
@CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
$endgroup$
– Max
Jan 26 at 13:19
$begingroup$
@CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles
$endgroup$
– Max
Jan 26 at 13:19
|
show 2 more comments
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%2f3088179%2ftwo-conflicting-versions-of-the-downward-l%25c3%25b6wenheim-skolem-theorem%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