Elementary embeddings, elementary substructures,category of sets
$begingroup$
I would like to characterize elementary embeddings AND elementary substructures in the category of sets and functions, Set. Not only characterize, but also justify this characterization.
functions category-theory
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
$endgroup$
add a comment |
$begingroup$
I would like to characterize elementary embeddings AND elementary substructures in the category of sets and functions, Set. Not only characterize, but also justify this characterization.
functions category-theory
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
$endgroup$
2
$begingroup$
The elementary embeddings are all bijections between finite sets and all injections between infinite sets.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:06
$begingroup$
What about elementary substructures in Set?
$endgroup$
– user122424
Apr 4 '14 at 15:08
2
$begingroup$
You can easily work that out yourself once you know what the elementary embeddings are.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:19
$begingroup$
Are you sure you are interested in $bf{Set}$? Why not in $bf{Mod}_tau$ for some first order signature $tau$?
$endgroup$
– Berci
Apr 6 '14 at 15:53
add a comment |
$begingroup$
I would like to characterize elementary embeddings AND elementary substructures in the category of sets and functions, Set. Not only characterize, but also justify this characterization.
functions category-theory
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
$endgroup$
I would like to characterize elementary embeddings AND elementary substructures in the category of sets and functions, Set. Not only characterize, but also justify this characterization.
functions category-theory
functions category-theory
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
edited May 31 '18 at 1:34
Andrés E. Caicedo
65.7k8160250
65.7k8160250
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
asked Apr 4 '14 at 15:03
user122424user122424
1,1582717
1,1582717
2
$begingroup$
The elementary embeddings are all bijections between finite sets and all injections between infinite sets.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:06
$begingroup$
What about elementary substructures in Set?
$endgroup$
– user122424
Apr 4 '14 at 15:08
2
$begingroup$
You can easily work that out yourself once you know what the elementary embeddings are.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:19
$begingroup$
Are you sure you are interested in $bf{Set}$? Why not in $bf{Mod}_tau$ for some first order signature $tau$?
$endgroup$
– Berci
Apr 6 '14 at 15:53
add a comment |
2
$begingroup$
The elementary embeddings are all bijections between finite sets and all injections between infinite sets.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:06
$begingroup$
What about elementary substructures in Set?
$endgroup$
– user122424
Apr 4 '14 at 15:08
2
$begingroup$
You can easily work that out yourself once you know what the elementary embeddings are.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:19
$begingroup$
Are you sure you are interested in $bf{Set}$? Why not in $bf{Mod}_tau$ for some first order signature $tau$?
$endgroup$
– Berci
Apr 6 '14 at 15:53
2
2
$begingroup$
The elementary embeddings are all bijections between finite sets and all injections between infinite sets.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:06
$begingroup$
The elementary embeddings are all bijections between finite sets and all injections between infinite sets.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:06
$begingroup$
What about elementary substructures in Set?
$endgroup$
– user122424
Apr 4 '14 at 15:08
$begingroup$
What about elementary substructures in Set?
$endgroup$
– user122424
Apr 4 '14 at 15:08
2
2
$begingroup$
You can easily work that out yourself once you know what the elementary embeddings are.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:19
$begingroup$
You can easily work that out yourself once you know what the elementary embeddings are.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:19
$begingroup$
Are you sure you are interested in $bf{Set}$? Why not in $bf{Mod}_tau$ for some first order signature $tau$?
$endgroup$
– Berci
Apr 6 '14 at 15:53
$begingroup$
Are you sure you are interested in $bf{Set}$? Why not in $bf{Mod}_tau$ for some first order signature $tau$?
$endgroup$
– Berci
Apr 6 '14 at 15:53
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Since a set is a structure in the empty language - there's no additional structure besides the underlying carrier set itself - things are quite simple to describe.
Specifically, we have full quantifier elimination, and the quantifier-free formulas can basically only say finitely many facts about size. This analysis - which I've left a bit vague, since it's a good exercise - shows the following:
If $A,B$ are infinite sets, then the elementary embeddings from $A$ to $B$ are precisely the injections.
If $A,B$ are finite sets, then the elementary embeddings from $A$ to $B$ are precisely the bijections.
Since an elementary substructure is just a substructure for which the inclusion map is an elementary embedding, this also characterizes the elementary substructures: $A$ is an elementary substructure of $B$ iff $Asubseteq B$ and either $A=B$ or $A$ (and hence $B$ as well) is infinite.
Finally, note that we also get a characterization of elementary equivalence: $Aequiv B$ iff $A,B$ either have the same cardinality or are each infinite. In particular, two sets are elementarily equivalent iff there is an elementary embedding of one of them into the other (since cardinalities are comparable - note that this uses a weak form of the axiom of choice!).
So what we see in the "pure set situation" is a near-complete collapse of logical notions: elementary equivalence/embedding/substructure mean almost the bare minimum of what they have to mean. The situation is far more interesting with even a little bit of structure involved, and this situation should really be thought of as pathological.
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f739638%2felementary-embeddings-elementary-substructures-category-of-sets%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$
Since a set is a structure in the empty language - there's no additional structure besides the underlying carrier set itself - things are quite simple to describe.
Specifically, we have full quantifier elimination, and the quantifier-free formulas can basically only say finitely many facts about size. This analysis - which I've left a bit vague, since it's a good exercise - shows the following:
If $A,B$ are infinite sets, then the elementary embeddings from $A$ to $B$ are precisely the injections.
If $A,B$ are finite sets, then the elementary embeddings from $A$ to $B$ are precisely the bijections.
Since an elementary substructure is just a substructure for which the inclusion map is an elementary embedding, this also characterizes the elementary substructures: $A$ is an elementary substructure of $B$ iff $Asubseteq B$ and either $A=B$ or $A$ (and hence $B$ as well) is infinite.
Finally, note that we also get a characterization of elementary equivalence: $Aequiv B$ iff $A,B$ either have the same cardinality or are each infinite. In particular, two sets are elementarily equivalent iff there is an elementary embedding of one of them into the other (since cardinalities are comparable - note that this uses a weak form of the axiom of choice!).
So what we see in the "pure set situation" is a near-complete collapse of logical notions: elementary equivalence/embedding/substructure mean almost the bare minimum of what they have to mean. The situation is far more interesting with even a little bit of structure involved, and this situation should really be thought of as pathological.
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
$endgroup$
add a comment |
$begingroup$
Since a set is a structure in the empty language - there's no additional structure besides the underlying carrier set itself - things are quite simple to describe.
Specifically, we have full quantifier elimination, and the quantifier-free formulas can basically only say finitely many facts about size. This analysis - which I've left a bit vague, since it's a good exercise - shows the following:
If $A,B$ are infinite sets, then the elementary embeddings from $A$ to $B$ are precisely the injections.
If $A,B$ are finite sets, then the elementary embeddings from $A$ to $B$ are precisely the bijections.
Since an elementary substructure is just a substructure for which the inclusion map is an elementary embedding, this also characterizes the elementary substructures: $A$ is an elementary substructure of $B$ iff $Asubseteq B$ and either $A=B$ or $A$ (and hence $B$ as well) is infinite.
Finally, note that we also get a characterization of elementary equivalence: $Aequiv B$ iff $A,B$ either have the same cardinality or are each infinite. In particular, two sets are elementarily equivalent iff there is an elementary embedding of one of them into the other (since cardinalities are comparable - note that this uses a weak form of the axiom of choice!).
So what we see in the "pure set situation" is a near-complete collapse of logical notions: elementary equivalence/embedding/substructure mean almost the bare minimum of what they have to mean. The situation is far more interesting with even a little bit of structure involved, and this situation should really be thought of as pathological.
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
$endgroup$
add a comment |
$begingroup$
Since a set is a structure in the empty language - there's no additional structure besides the underlying carrier set itself - things are quite simple to describe.
Specifically, we have full quantifier elimination, and the quantifier-free formulas can basically only say finitely many facts about size. This analysis - which I've left a bit vague, since it's a good exercise - shows the following:
If $A,B$ are infinite sets, then the elementary embeddings from $A$ to $B$ are precisely the injections.
If $A,B$ are finite sets, then the elementary embeddings from $A$ to $B$ are precisely the bijections.
Since an elementary substructure is just a substructure for which the inclusion map is an elementary embedding, this also characterizes the elementary substructures: $A$ is an elementary substructure of $B$ iff $Asubseteq B$ and either $A=B$ or $A$ (and hence $B$ as well) is infinite.
Finally, note that we also get a characterization of elementary equivalence: $Aequiv B$ iff $A,B$ either have the same cardinality or are each infinite. In particular, two sets are elementarily equivalent iff there is an elementary embedding of one of them into the other (since cardinalities are comparable - note that this uses a weak form of the axiom of choice!).
So what we see in the "pure set situation" is a near-complete collapse of logical notions: elementary equivalence/embedding/substructure mean almost the bare minimum of what they have to mean. The situation is far more interesting with even a little bit of structure involved, and this situation should really be thought of as pathological.
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
$endgroup$
Since a set is a structure in the empty language - there's no additional structure besides the underlying carrier set itself - things are quite simple to describe.
Specifically, we have full quantifier elimination, and the quantifier-free formulas can basically only say finitely many facts about size. This analysis - which I've left a bit vague, since it's a good exercise - shows the following:
If $A,B$ are infinite sets, then the elementary embeddings from $A$ to $B$ are precisely the injections.
If $A,B$ are finite sets, then the elementary embeddings from $A$ to $B$ are precisely the bijections.
Since an elementary substructure is just a substructure for which the inclusion map is an elementary embedding, this also characterizes the elementary substructures: $A$ is an elementary substructure of $B$ iff $Asubseteq B$ and either $A=B$ or $A$ (and hence $B$ as well) is infinite.
Finally, note that we also get a characterization of elementary equivalence: $Aequiv B$ iff $A,B$ either have the same cardinality or are each infinite. In particular, two sets are elementarily equivalent iff there is an elementary embedding of one of them into the other (since cardinalities are comparable - note that this uses a weak form of the axiom of choice!).
So what we see in the "pure set situation" is a near-complete collapse of logical notions: elementary equivalence/embedding/substructure mean almost the bare minimum of what they have to mean. The situation is far more interesting with even a little bit of structure involved, and this situation should really be thought of as pathological.
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
answered Dec 16 '18 at 19:34
Noah SchweberNoah Schweber
127k10151290
127k10151290
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%2f739638%2felementary-embeddings-elementary-substructures-category-of-sets%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
2
$begingroup$
The elementary embeddings are all bijections between finite sets and all injections between infinite sets.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:06
$begingroup$
What about elementary substructures in Set?
$endgroup$
– user122424
Apr 4 '14 at 15:08
2
$begingroup$
You can easily work that out yourself once you know what the elementary embeddings are.
$endgroup$
– Zhen Lin
Apr 4 '14 at 15:19
$begingroup$
Are you sure you are interested in $bf{Set}$? Why not in $bf{Mod}_tau$ for some first order signature $tau$?
$endgroup$
– Berci
Apr 6 '14 at 15:53