What are the properties of countably infinite sets compared to sets of higher cardinality?
$begingroup$
When looking at mathematical definitions, there are quite a few cases where we limit certain properties to countably infinite sets (e.g. $sigma$-Algebras).
In some cases we set this limit as we'd lose our intuition of what would happen if we chose an even bigger infinity, in other cases there are hard facts at work.
Yet, the only property of countably infinite sets that comes to my mind is ... well, that they are countable, and the higher cardinalities are not.
I'm sure though that there are many more characteristic properties of countably infinite sets that get lost when moving up to higher cardinalities - so what are they?
elementary-set-theory cardinals
asked Dec 3 '18 at 19:22
SudixSudix
8781316
$endgroup$
add a comment |
$begingroup$
When looking at mathematical definitions, there are quite a few cases where we limit certain properties to countably infinite sets (e.g. $sigma$-Algebras).
In some cases we set this limit as we'd lose our intuition of what would happen if we chose an even bigger infinity, in other cases there are hard facts at work.
Yet, the only property of countably infinite sets that comes to my mind is ... well, that they are countable, and the higher cardinalities are not.
I'm sure though that there are many more characteristic properties of countably infinite sets that get lost when moving up to higher cardinalities - so what are they?
elementary-set-theory cardinals
asked Dec 3 '18 at 19:22
SudixSudix
8781316
$endgroup$
add a comment |
$begingroup$
When looking at mathematical definitions, there are quite a few cases where we limit certain properties to countably infinite sets (e.g. $sigma$-Algebras).
In some cases we set this limit as we'd lose our intuition of what would happen if we chose an even bigger infinity, in other cases there are hard facts at work.
Yet, the only property of countably infinite sets that comes to my mind is ... well, that they are countable, and the higher cardinalities are not.
I'm sure though that there are many more characteristic properties of countably infinite sets that get lost when moving up to higher cardinalities - so what are they?
elementary-set-theory cardinals
asked Dec 3 '18 at 19:22
SudixSudix
8781316
$endgroup$
When looking at mathematical definitions, there are quite a few cases where we limit certain properties to countably infinite sets (e.g. $sigma$-Algebras).
In some cases we set this limit as we'd lose our intuition of what would happen if we chose an even bigger infinity, in other cases there are hard facts at work.
Yet, the only property of countably infinite sets that comes to my mind is ... well, that they are countable, and the higher cardinalities are not.
I'm sure though that there are many more characteristic properties of countably infinite sets that get lost when moving up to higher cardinalities - so what are they?
elementary-set-theory cardinals
elementary-set-theory cardinals
asked Dec 3 '18 at 19:22
SudixSudix
8781316
asked Dec 3 '18 at 19:22
SudixSudix
8781316
asked Dec 3 '18 at 19:22
SudixSudix
8781316
asked Dec 3 '18 at 19:22
SudixSudix
8781316
asked Dec 3 '18 at 19:22
SudixSudix
8781316
8781316
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are a lot of combinatorial properties you lose. For example:
$mathbb{N}$ satisfies infinite Ramsey's theorem for pairs: if $c:[mathbb{N}]^2rightarrow {0,1}$ is a $2$-coloring of pairs of natural numbers, then there is a $c$-homogeneous set $H$ (that is, $c({x,y})=c({x',y'})$ for all $xnot=y, x'not=y'$ in $H$) of the same size as $mathbb{N}$. This fails in general for uncountable sets: if $X$ is uncountable, there may be a $2$-coloring of pairs of elements of $X$ with no size-$X$ homogeneous set. In fact, this fails for most uncountable cardinalities in a precise sense (see below), and provably fails of $aleph_1$ (and indeed any uncountable $kappale 2^{aleph_0}$) in particular: fix an injection $i:aleph_1rightarrowmathbb{R}$, and consider the coloring $$c:[aleph_1]^2rightarrow{0,1}: c({x,y}=1iff (x<_{aleph_1}yiff i(x)<_mathbb{R}i(y)))$$ (with the two different orderings "decorated" for clarity). - it's not hard to show, using the separability (= countable dense subset) of $mathbb{R}$, that $c$ cannot have an uncountable homogeneous set.
$mathbb{N}$ satisfies Konig's lemma: any infinite-height, finitely-branching tree has an infinite path. The "$kappa$-version" of this property, for an arbitrary infinite cardinal $kappa$, should be: "Any $<kappa$-branching tree of height $kappa$ has a $kappa$-length branch," but this too breaks down in general for uncountable sets, and in particular is again provably false for $aleph_1$.
Combinatorial properties of $mathbb{N}$ in general are very special, and often correspond to large cardinal properties when lifted to the uncountable setting. For example, it is consistent with ZFC that only $aleph_0$ has the Ramsey property above.
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
$endgroup$
1
$begingroup$
Another special property of $aleph_0$ is that of being inaccessible in the sense that it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. The existence of inaccessible cardinals larger than $aleph_0$ cannot be proved in ZFC (assuming ZFC is consistent).
$endgroup$
– mlerma54
Dec 3 '18 at 20:09
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%2f3024543%2fwhat-are-the-properties-of-countably-infinite-sets-compared-to-sets-of-higher-ca%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$
There are a lot of combinatorial properties you lose. For example:
$mathbb{N}$ satisfies infinite Ramsey's theorem for pairs: if $c:[mathbb{N}]^2rightarrow {0,1}$ is a $2$-coloring of pairs of natural numbers, then there is a $c$-homogeneous set $H$ (that is, $c({x,y})=c({x',y'})$ for all $xnot=y, x'not=y'$ in $H$) of the same size as $mathbb{N}$. This fails in general for uncountable sets: if $X$ is uncountable, there may be a $2$-coloring of pairs of elements of $X$ with no size-$X$ homogeneous set. In fact, this fails for most uncountable cardinalities in a precise sense (see below), and provably fails of $aleph_1$ (and indeed any uncountable $kappale 2^{aleph_0}$) in particular: fix an injection $i:aleph_1rightarrowmathbb{R}$, and consider the coloring $$c:[aleph_1]^2rightarrow{0,1}: c({x,y}=1iff (x<_{aleph_1}yiff i(x)<_mathbb{R}i(y)))$$ (with the two different orderings "decorated" for clarity). - it's not hard to show, using the separability (= countable dense subset) of $mathbb{R}$, that $c$ cannot have an uncountable homogeneous set.
$mathbb{N}$ satisfies Konig's lemma: any infinite-height, finitely-branching tree has an infinite path. The "$kappa$-version" of this property, for an arbitrary infinite cardinal $kappa$, should be: "Any $<kappa$-branching tree of height $kappa$ has a $kappa$-length branch," but this too breaks down in general for uncountable sets, and in particular is again provably false for $aleph_1$.
Combinatorial properties of $mathbb{N}$ in general are very special, and often correspond to large cardinal properties when lifted to the uncountable setting. For example, it is consistent with ZFC that only $aleph_0$ has the Ramsey property above.
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
$endgroup$
1
$begingroup$
Another special property of $aleph_0$ is that of being inaccessible in the sense that it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. The existence of inaccessible cardinals larger than $aleph_0$ cannot be proved in ZFC (assuming ZFC is consistent).
$endgroup$
– mlerma54
Dec 3 '18 at 20:09
add a comment |
$begingroup$
There are a lot of combinatorial properties you lose. For example:
$mathbb{N}$ satisfies infinite Ramsey's theorem for pairs: if $c:[mathbb{N}]^2rightarrow {0,1}$ is a $2$-coloring of pairs of natural numbers, then there is a $c$-homogeneous set $H$ (that is, $c({x,y})=c({x',y'})$ for all $xnot=y, x'not=y'$ in $H$) of the same size as $mathbb{N}$. This fails in general for uncountable sets: if $X$ is uncountable, there may be a $2$-coloring of pairs of elements of $X$ with no size-$X$ homogeneous set. In fact, this fails for most uncountable cardinalities in a precise sense (see below), and provably fails of $aleph_1$ (and indeed any uncountable $kappale 2^{aleph_0}$) in particular: fix an injection $i:aleph_1rightarrowmathbb{R}$, and consider the coloring $$c:[aleph_1]^2rightarrow{0,1}: c({x,y}=1iff (x<_{aleph_1}yiff i(x)<_mathbb{R}i(y)))$$ (with the two different orderings "decorated" for clarity). - it's not hard to show, using the separability (= countable dense subset) of $mathbb{R}$, that $c$ cannot have an uncountable homogeneous set.
$mathbb{N}$ satisfies Konig's lemma: any infinite-height, finitely-branching tree has an infinite path. The "$kappa$-version" of this property, for an arbitrary infinite cardinal $kappa$, should be: "Any $<kappa$-branching tree of height $kappa$ has a $kappa$-length branch," but this too breaks down in general for uncountable sets, and in particular is again provably false for $aleph_1$.
Combinatorial properties of $mathbb{N}$ in general are very special, and often correspond to large cardinal properties when lifted to the uncountable setting. For example, it is consistent with ZFC that only $aleph_0$ has the Ramsey property above.
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
$endgroup$
1
$begingroup$
Another special property of $aleph_0$ is that of being inaccessible in the sense that it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. The existence of inaccessible cardinals larger than $aleph_0$ cannot be proved in ZFC (assuming ZFC is consistent).
$endgroup$
– mlerma54
Dec 3 '18 at 20:09
add a comment |
$begingroup$
There are a lot of combinatorial properties you lose. For example:
$mathbb{N}$ satisfies infinite Ramsey's theorem for pairs: if $c:[mathbb{N}]^2rightarrow {0,1}$ is a $2$-coloring of pairs of natural numbers, then there is a $c$-homogeneous set $H$ (that is, $c({x,y})=c({x',y'})$ for all $xnot=y, x'not=y'$ in $H$) of the same size as $mathbb{N}$. This fails in general for uncountable sets: if $X$ is uncountable, there may be a $2$-coloring of pairs of elements of $X$ with no size-$X$ homogeneous set. In fact, this fails for most uncountable cardinalities in a precise sense (see below), and provably fails of $aleph_1$ (and indeed any uncountable $kappale 2^{aleph_0}$) in particular: fix an injection $i:aleph_1rightarrowmathbb{R}$, and consider the coloring $$c:[aleph_1]^2rightarrow{0,1}: c({x,y}=1iff (x<_{aleph_1}yiff i(x)<_mathbb{R}i(y)))$$ (with the two different orderings "decorated" for clarity). - it's not hard to show, using the separability (= countable dense subset) of $mathbb{R}$, that $c$ cannot have an uncountable homogeneous set.
$mathbb{N}$ satisfies Konig's lemma: any infinite-height, finitely-branching tree has an infinite path. The "$kappa$-version" of this property, for an arbitrary infinite cardinal $kappa$, should be: "Any $<kappa$-branching tree of height $kappa$ has a $kappa$-length branch," but this too breaks down in general for uncountable sets, and in particular is again provably false for $aleph_1$.
Combinatorial properties of $mathbb{N}$ in general are very special, and often correspond to large cardinal properties when lifted to the uncountable setting. For example, it is consistent with ZFC that only $aleph_0$ has the Ramsey property above.
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
$endgroup$
There are a lot of combinatorial properties you lose. For example:
$mathbb{N}$ satisfies infinite Ramsey's theorem for pairs: if $c:[mathbb{N}]^2rightarrow {0,1}$ is a $2$-coloring of pairs of natural numbers, then there is a $c$-homogeneous set $H$ (that is, $c({x,y})=c({x',y'})$ for all $xnot=y, x'not=y'$ in $H$) of the same size as $mathbb{N}$. This fails in general for uncountable sets: if $X$ is uncountable, there may be a $2$-coloring of pairs of elements of $X$ with no size-$X$ homogeneous set. In fact, this fails for most uncountable cardinalities in a precise sense (see below), and provably fails of $aleph_1$ (and indeed any uncountable $kappale 2^{aleph_0}$) in particular: fix an injection $i:aleph_1rightarrowmathbb{R}$, and consider the coloring $$c:[aleph_1]^2rightarrow{0,1}: c({x,y}=1iff (x<_{aleph_1}yiff i(x)<_mathbb{R}i(y)))$$ (with the two different orderings "decorated" for clarity). - it's not hard to show, using the separability (= countable dense subset) of $mathbb{R}$, that $c$ cannot have an uncountable homogeneous set.
$mathbb{N}$ satisfies Konig's lemma: any infinite-height, finitely-branching tree has an infinite path. The "$kappa$-version" of this property, for an arbitrary infinite cardinal $kappa$, should be: "Any $<kappa$-branching tree of height $kappa$ has a $kappa$-length branch," but this too breaks down in general for uncountable sets, and in particular is again provably false for $aleph_1$.
Combinatorial properties of $mathbb{N}$ in general are very special, and often correspond to large cardinal properties when lifted to the uncountable setting. For example, it is consistent with ZFC that only $aleph_0$ has the Ramsey property above.
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
answered Dec 3 '18 at 19:58
Noah SchweberNoah Schweber
122k10149284
122k10149284
1
$begingroup$
Another special property of $aleph_0$ is that of being inaccessible in the sense that it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. The existence of inaccessible cardinals larger than $aleph_0$ cannot be proved in ZFC (assuming ZFC is consistent).
$endgroup$
– mlerma54
Dec 3 '18 at 20:09
add a comment |
1
$begingroup$
Another special property of $aleph_0$ is that of being inaccessible in the sense that it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. The existence of inaccessible cardinals larger than $aleph_0$ cannot be proved in ZFC (assuming ZFC is consistent).
$endgroup$
– mlerma54
Dec 3 '18 at 20:09
1
1
$begingroup$
Another special property of $aleph_0$ is that of being inaccessible in the sense that it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. The existence of inaccessible cardinals larger than $aleph_0$ cannot be proved in ZFC (assuming ZFC is consistent).
$endgroup$
– mlerma54
Dec 3 '18 at 20:09
$begingroup$
Another special property of $aleph_0$ is that of being inaccessible in the sense that it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. The existence of inaccessible cardinals larger than $aleph_0$ cannot be proved in ZFC (assuming ZFC is consistent).
$endgroup$
– mlerma54
Dec 3 '18 at 20:09
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%2f3024543%2fwhat-are-the-properties-of-countably-infinite-sets-compared-to-sets-of-higher-ca%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
