The cardinality of a countable union of countable sets, without the axiom of choice
One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $aleph_2$. My solution shows that it does not have cardinality $aleph_n$, where $n$ is any non-zero ordinal (not necessarily finite). I have a sneaking suspicion that my solution is actually invalid, but I can't find any reference which invalidates my conclusion.
I have read that it is provable in ZF that there are no cardinals $kappa$ such that $aleph_0 < kappa < aleph_1$, but I believe the conclusion of my proof does not preclude the possibility that the cardinality is incomparable to $aleph_1$ or some such.
I think the weakest point in my solution is where I claim that the supremum of a countable set of countable ordinals is again countable. This is true, of course, but it sounds uncomfortably close to the claim "a countable union of countable sets is countable", which is well-known to be unprovable in ZF. Can anybody confirm that the ordinal version is provable in ZF though? If not, I think I can weaken the claim to "the supremum of any set of countable ordinals is at most $omega_1$", and this establishes the weaker result that the cardinality of a countable union of countable sets is not $aleph_n$ for any ordinal $n ge 2$.
set-theory cardinals axiom-of-choice ordinals
add a comment |
One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $aleph_2$. My solution shows that it does not have cardinality $aleph_n$, where $n$ is any non-zero ordinal (not necessarily finite). I have a sneaking suspicion that my solution is actually invalid, but I can't find any reference which invalidates my conclusion.
I have read that it is provable in ZF that there are no cardinals $kappa$ such that $aleph_0 < kappa < aleph_1$, but I believe the conclusion of my proof does not preclude the possibility that the cardinality is incomparable to $aleph_1$ or some such.
I think the weakest point in my solution is where I claim that the supremum of a countable set of countable ordinals is again countable. This is true, of course, but it sounds uncomfortably close to the claim "a countable union of countable sets is countable", which is well-known to be unprovable in ZF. Can anybody confirm that the ordinal version is provable in ZF though? If not, I think I can weaken the claim to "the supremum of any set of countable ordinals is at most $omega_1$", and this establishes the weaker result that the cardinality of a countable union of countable sets is not $aleph_n$ for any ordinal $n ge 2$.
set-theory cardinals axiom-of-choice ordinals
add a comment |
One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $aleph_2$. My solution shows that it does not have cardinality $aleph_n$, where $n$ is any non-zero ordinal (not necessarily finite). I have a sneaking suspicion that my solution is actually invalid, but I can't find any reference which invalidates my conclusion.
I have read that it is provable in ZF that there are no cardinals $kappa$ such that $aleph_0 < kappa < aleph_1$, but I believe the conclusion of my proof does not preclude the possibility that the cardinality is incomparable to $aleph_1$ or some such.
I think the weakest point in my solution is where I claim that the supremum of a countable set of countable ordinals is again countable. This is true, of course, but it sounds uncomfortably close to the claim "a countable union of countable sets is countable", which is well-known to be unprovable in ZF. Can anybody confirm that the ordinal version is provable in ZF though? If not, I think I can weaken the claim to "the supremum of any set of countable ordinals is at most $omega_1$", and this establishes the weaker result that the cardinality of a countable union of countable sets is not $aleph_n$ for any ordinal $n ge 2$.
set-theory cardinals axiom-of-choice ordinals
One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $aleph_2$. My solution shows that it does not have cardinality $aleph_n$, where $n$ is any non-zero ordinal (not necessarily finite). I have a sneaking suspicion that my solution is actually invalid, but I can't find any reference which invalidates my conclusion.
I have read that it is provable in ZF that there are no cardinals $kappa$ such that $aleph_0 < kappa < aleph_1$, but I believe the conclusion of my proof does not preclude the possibility that the cardinality is incomparable to $aleph_1$ or some such.
I think the weakest point in my solution is where I claim that the supremum of a countable set of countable ordinals is again countable. This is true, of course, but it sounds uncomfortably close to the claim "a countable union of countable sets is countable", which is well-known to be unprovable in ZF. Can anybody confirm that the ordinal version is provable in ZF though? If not, I think I can weaken the claim to "the supremum of any set of countable ordinals is at most $omega_1$", and this establishes the weaker result that the cardinality of a countable union of countable sets is not $aleph_n$ for any ordinal $n ge 2$.
set-theory cardinals axiom-of-choice ordinals
set-theory cardinals axiom-of-choice ordinals
asked Jan 3 '11 at 16:32
Zhen Lin
60.2k4108220
60.2k4108220
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
The ordinal $omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.
This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.
The result is that it is consistent with $mathsf{ZF}$ that ${mathbb R}$ is a countable union of countable sets. From this, it follows easily that $omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.
The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.
In fact, things can be worse: Gitik showed that it is consistent with $mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)
On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.
Let me add two comments about other things you say in your question: You write "I have read that it is provable in $mathsf{ZF}$ that there are no cardinals $kappa$ such that $aleph_0<kappa<aleph_1$". This is true, but it is stronger than that: By definition $aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $aleph_0$ and $aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $kappa$ and its successor $kappa^+$, by definition.
It is true, however, that a countable union of countable sets need not be comparable with $aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.
Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $omega_2$, we check more generally that if $kappa$ is a (well-ordered) cardinal, then a union of $kappa$ many sets, each of size at most $kappa$, cannot have size $kappa^{++}$: Let $S_0,S_1,dots,S_beta,dots$, $beta<kappa$, be sets of ordinals, each of size at most $kappa$. Let $S$ be their union and let $alpha={rm ot}(S)$, the order type of $S$. Similarly, let $o_iota={rm ot}(S_iota)$ for each $iota<kappa$. Each $o_iota$ is an ordinal below $kappa^+$ and therefore $o=sup_iota o_iotalekappa^+$. Use this to define a surjection $f$ from $kappatimes o$ onto $alpha$, from which it follows that there is an injection from $alpha$ into $kappatimes o$, and therefore a injection from $alpha$ into $kappa^+$:
Given $(iota,beta)in kappatimes o$, define $f(iota,beta)=0$ unless $beta<o_iota$ and, letting $gamma$ be the $beta$-th element in the increasing enumeration of $S_iota$, we have that $iota$ is least such that $gammain S_iota$. If this is the case, then set $f(iota,beta)=delta$, where $delta$ is defined so that $gamma$ is the $delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.
(It is perhaps clear, but let me remark that if $omega_1$ can be written as the countable union of countable sets, then any $alpha<omega_2$ can be written this way as well, so $omega_2$ cannot be replaced with any smaller bound.)
Thank you for the references and examples. I'm curious though — Can it be shown that the union of a countable family $S$ of countable unordered sets has cardinality at most $aleph_1$? This seems to be a stronger claim than the conclusion of my proof (that $|bigcup S| ne aleph_n$ for any $n ge 2$).
– Zhen Lin
Jan 3 '11 at 17:24
2
This result of Gitik is terrifying, wonderful!
– Asaf Karagila♦
Jan 3 '11 at 17:43
@Zhen: No, this cannot be shown. As I mentioned, a countable union of sets of size 2 needs not be comparable with $aleph_1$.
– Andrés E. Caicedo
Jan 3 '11 at 17:50
@Asaf: I agree. And there are some very interesting questions still left. Schindler and Busche have recently looked at the consistency strength of Gitik's result, and Ioanna M. Dimitriou, a student of Peter Koepke, has also been studying this model.
– Andrés E. Caicedo
Jan 3 '11 at 17:53
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%2f16246%2fthe-cardinality-of-a-countable-union-of-countable-sets-without-the-axiom-of-cho%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
The ordinal $omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.
This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.
The result is that it is consistent with $mathsf{ZF}$ that ${mathbb R}$ is a countable union of countable sets. From this, it follows easily that $omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.
The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.
In fact, things can be worse: Gitik showed that it is consistent with $mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)
On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.
Let me add two comments about other things you say in your question: You write "I have read that it is provable in $mathsf{ZF}$ that there are no cardinals $kappa$ such that $aleph_0<kappa<aleph_1$". This is true, but it is stronger than that: By definition $aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $aleph_0$ and $aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $kappa$ and its successor $kappa^+$, by definition.
It is true, however, that a countable union of countable sets need not be comparable with $aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.
Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $omega_2$, we check more generally that if $kappa$ is a (well-ordered) cardinal, then a union of $kappa$ many sets, each of size at most $kappa$, cannot have size $kappa^{++}$: Let $S_0,S_1,dots,S_beta,dots$, $beta<kappa$, be sets of ordinals, each of size at most $kappa$. Let $S$ be their union and let $alpha={rm ot}(S)$, the order type of $S$. Similarly, let $o_iota={rm ot}(S_iota)$ for each $iota<kappa$. Each $o_iota$ is an ordinal below $kappa^+$ and therefore $o=sup_iota o_iotalekappa^+$. Use this to define a surjection $f$ from $kappatimes o$ onto $alpha$, from which it follows that there is an injection from $alpha$ into $kappatimes o$, and therefore a injection from $alpha$ into $kappa^+$:
Given $(iota,beta)in kappatimes o$, define $f(iota,beta)=0$ unless $beta<o_iota$ and, letting $gamma$ be the $beta$-th element in the increasing enumeration of $S_iota$, we have that $iota$ is least such that $gammain S_iota$. If this is the case, then set $f(iota,beta)=delta$, where $delta$ is defined so that $gamma$ is the $delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.
(It is perhaps clear, but let me remark that if $omega_1$ can be written as the countable union of countable sets, then any $alpha<omega_2$ can be written this way as well, so $omega_2$ cannot be replaced with any smaller bound.)
Thank you for the references and examples. I'm curious though — Can it be shown that the union of a countable family $S$ of countable unordered sets has cardinality at most $aleph_1$? This seems to be a stronger claim than the conclusion of my proof (that $|bigcup S| ne aleph_n$ for any $n ge 2$).
– Zhen Lin
Jan 3 '11 at 17:24
2
This result of Gitik is terrifying, wonderful!
– Asaf Karagila♦
Jan 3 '11 at 17:43
@Zhen: No, this cannot be shown. As I mentioned, a countable union of sets of size 2 needs not be comparable with $aleph_1$.
– Andrés E. Caicedo
Jan 3 '11 at 17:50
@Asaf: I agree. And there are some very interesting questions still left. Schindler and Busche have recently looked at the consistency strength of Gitik's result, and Ioanna M. Dimitriou, a student of Peter Koepke, has also been studying this model.
– Andrés E. Caicedo
Jan 3 '11 at 17:53
add a comment |
The ordinal $omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.
This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.
The result is that it is consistent with $mathsf{ZF}$ that ${mathbb R}$ is a countable union of countable sets. From this, it follows easily that $omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.
The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.
In fact, things can be worse: Gitik showed that it is consistent with $mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)
On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.
Let me add two comments about other things you say in your question: You write "I have read that it is provable in $mathsf{ZF}$ that there are no cardinals $kappa$ such that $aleph_0<kappa<aleph_1$". This is true, but it is stronger than that: By definition $aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $aleph_0$ and $aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $kappa$ and its successor $kappa^+$, by definition.
It is true, however, that a countable union of countable sets need not be comparable with $aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.
Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $omega_2$, we check more generally that if $kappa$ is a (well-ordered) cardinal, then a union of $kappa$ many sets, each of size at most $kappa$, cannot have size $kappa^{++}$: Let $S_0,S_1,dots,S_beta,dots$, $beta<kappa$, be sets of ordinals, each of size at most $kappa$. Let $S$ be their union and let $alpha={rm ot}(S)$, the order type of $S$. Similarly, let $o_iota={rm ot}(S_iota)$ for each $iota<kappa$. Each $o_iota$ is an ordinal below $kappa^+$ and therefore $o=sup_iota o_iotalekappa^+$. Use this to define a surjection $f$ from $kappatimes o$ onto $alpha$, from which it follows that there is an injection from $alpha$ into $kappatimes o$, and therefore a injection from $alpha$ into $kappa^+$:
Given $(iota,beta)in kappatimes o$, define $f(iota,beta)=0$ unless $beta<o_iota$ and, letting $gamma$ be the $beta$-th element in the increasing enumeration of $S_iota$, we have that $iota$ is least such that $gammain S_iota$. If this is the case, then set $f(iota,beta)=delta$, where $delta$ is defined so that $gamma$ is the $delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.
(It is perhaps clear, but let me remark that if $omega_1$ can be written as the countable union of countable sets, then any $alpha<omega_2$ can be written this way as well, so $omega_2$ cannot be replaced with any smaller bound.)
Thank you for the references and examples. I'm curious though — Can it be shown that the union of a countable family $S$ of countable unordered sets has cardinality at most $aleph_1$? This seems to be a stronger claim than the conclusion of my proof (that $|bigcup S| ne aleph_n$ for any $n ge 2$).
– Zhen Lin
Jan 3 '11 at 17:24
2
This result of Gitik is terrifying, wonderful!
– Asaf Karagila♦
Jan 3 '11 at 17:43
@Zhen: No, this cannot be shown. As I mentioned, a countable union of sets of size 2 needs not be comparable with $aleph_1$.
– Andrés E. Caicedo
Jan 3 '11 at 17:50
@Asaf: I agree. And there are some very interesting questions still left. Schindler and Busche have recently looked at the consistency strength of Gitik's result, and Ioanna M. Dimitriou, a student of Peter Koepke, has also been studying this model.
– Andrés E. Caicedo
Jan 3 '11 at 17:53
add a comment |
The ordinal $omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.
This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.
The result is that it is consistent with $mathsf{ZF}$ that ${mathbb R}$ is a countable union of countable sets. From this, it follows easily that $omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.
The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.
In fact, things can be worse: Gitik showed that it is consistent with $mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)
On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.
Let me add two comments about other things you say in your question: You write "I have read that it is provable in $mathsf{ZF}$ that there are no cardinals $kappa$ such that $aleph_0<kappa<aleph_1$". This is true, but it is stronger than that: By definition $aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $aleph_0$ and $aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $kappa$ and its successor $kappa^+$, by definition.
It is true, however, that a countable union of countable sets need not be comparable with $aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.
Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $omega_2$, we check more generally that if $kappa$ is a (well-ordered) cardinal, then a union of $kappa$ many sets, each of size at most $kappa$, cannot have size $kappa^{++}$: Let $S_0,S_1,dots,S_beta,dots$, $beta<kappa$, be sets of ordinals, each of size at most $kappa$. Let $S$ be their union and let $alpha={rm ot}(S)$, the order type of $S$. Similarly, let $o_iota={rm ot}(S_iota)$ for each $iota<kappa$. Each $o_iota$ is an ordinal below $kappa^+$ and therefore $o=sup_iota o_iotalekappa^+$. Use this to define a surjection $f$ from $kappatimes o$ onto $alpha$, from which it follows that there is an injection from $alpha$ into $kappatimes o$, and therefore a injection from $alpha$ into $kappa^+$:
Given $(iota,beta)in kappatimes o$, define $f(iota,beta)=0$ unless $beta<o_iota$ and, letting $gamma$ be the $beta$-th element in the increasing enumeration of $S_iota$, we have that $iota$ is least such that $gammain S_iota$. If this is the case, then set $f(iota,beta)=delta$, where $delta$ is defined so that $gamma$ is the $delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.
(It is perhaps clear, but let me remark that if $omega_1$ can be written as the countable union of countable sets, then any $alpha<omega_2$ can be written this way as well, so $omega_2$ cannot be replaced with any smaller bound.)
The ordinal $omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.
This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.
The result is that it is consistent with $mathsf{ZF}$ that ${mathbb R}$ is a countable union of countable sets. From this, it follows easily that $omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.
The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.
In fact, things can be worse: Gitik showed that it is consistent with $mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)
On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.
Let me add two comments about other things you say in your question: You write "I have read that it is provable in $mathsf{ZF}$ that there are no cardinals $kappa$ such that $aleph_0<kappa<aleph_1$". This is true, but it is stronger than that: By definition $aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $aleph_0$ and $aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $kappa$ and its successor $kappa^+$, by definition.
It is true, however, that a countable union of countable sets need not be comparable with $aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.
Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $omega_2$, we check more generally that if $kappa$ is a (well-ordered) cardinal, then a union of $kappa$ many sets, each of size at most $kappa$, cannot have size $kappa^{++}$: Let $S_0,S_1,dots,S_beta,dots$, $beta<kappa$, be sets of ordinals, each of size at most $kappa$. Let $S$ be their union and let $alpha={rm ot}(S)$, the order type of $S$. Similarly, let $o_iota={rm ot}(S_iota)$ for each $iota<kappa$. Each $o_iota$ is an ordinal below $kappa^+$ and therefore $o=sup_iota o_iotalekappa^+$. Use this to define a surjection $f$ from $kappatimes o$ onto $alpha$, from which it follows that there is an injection from $alpha$ into $kappatimes o$, and therefore a injection from $alpha$ into $kappa^+$:
Given $(iota,beta)in kappatimes o$, define $f(iota,beta)=0$ unless $beta<o_iota$ and, letting $gamma$ be the $beta$-th element in the increasing enumeration of $S_iota$, we have that $iota$ is least such that $gammain S_iota$. If this is the case, then set $f(iota,beta)=delta$, where $delta$ is defined so that $gamma$ is the $delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.
(It is perhaps clear, but let me remark that if $omega_1$ can be written as the countable union of countable sets, then any $alpha<omega_2$ can be written this way as well, so $omega_2$ cannot be replaced with any smaller bound.)
edited Jun 24 '16 at 13:32
answered Jan 3 '11 at 17:01
Andrés E. Caicedo
64.8k8158246
64.8k8158246
Thank you for the references and examples. I'm curious though — Can it be shown that the union of a countable family $S$ of countable unordered sets has cardinality at most $aleph_1$? This seems to be a stronger claim than the conclusion of my proof (that $|bigcup S| ne aleph_n$ for any $n ge 2$).
– Zhen Lin
Jan 3 '11 at 17:24
2
This result of Gitik is terrifying, wonderful!
– Asaf Karagila♦
Jan 3 '11 at 17:43
@Zhen: No, this cannot be shown. As I mentioned, a countable union of sets of size 2 needs not be comparable with $aleph_1$.
– Andrés E. Caicedo
Jan 3 '11 at 17:50
@Asaf: I agree. And there are some very interesting questions still left. Schindler and Busche have recently looked at the consistency strength of Gitik's result, and Ioanna M. Dimitriou, a student of Peter Koepke, has also been studying this model.
– Andrés E. Caicedo
Jan 3 '11 at 17:53
add a comment |
Thank you for the references and examples. I'm curious though — Can it be shown that the union of a countable family $S$ of countable unordered sets has cardinality at most $aleph_1$? This seems to be a stronger claim than the conclusion of my proof (that $|bigcup S| ne aleph_n$ for any $n ge 2$).
– Zhen Lin
Jan 3 '11 at 17:24
2
This result of Gitik is terrifying, wonderful!
– Asaf Karagila♦
Jan 3 '11 at 17:43
@Zhen: No, this cannot be shown. As I mentioned, a countable union of sets of size 2 needs not be comparable with $aleph_1$.
– Andrés E. Caicedo
Jan 3 '11 at 17:50
@Asaf: I agree. And there are some very interesting questions still left. Schindler and Busche have recently looked at the consistency strength of Gitik's result, and Ioanna M. Dimitriou, a student of Peter Koepke, has also been studying this model.
– Andrés E. Caicedo
Jan 3 '11 at 17:53
Thank you for the references and examples. I'm curious though — Can it be shown that the union of a countable family $S$ of countable unordered sets has cardinality at most $aleph_1$? This seems to be a stronger claim than the conclusion of my proof (that $|bigcup S| ne aleph_n$ for any $n ge 2$).
– Zhen Lin
Jan 3 '11 at 17:24
Thank you for the references and examples. I'm curious though — Can it be shown that the union of a countable family $S$ of countable unordered sets has cardinality at most $aleph_1$? This seems to be a stronger claim than the conclusion of my proof (that $|bigcup S| ne aleph_n$ for any $n ge 2$).
– Zhen Lin
Jan 3 '11 at 17:24
2
2
This result of Gitik is terrifying, wonderful!
– Asaf Karagila♦
Jan 3 '11 at 17:43
This result of Gitik is terrifying, wonderful!
– Asaf Karagila♦
Jan 3 '11 at 17:43
@Zhen: No, this cannot be shown. As I mentioned, a countable union of sets of size 2 needs not be comparable with $aleph_1$.
– Andrés E. Caicedo
Jan 3 '11 at 17:50
@Zhen: No, this cannot be shown. As I mentioned, a countable union of sets of size 2 needs not be comparable with $aleph_1$.
– Andrés E. Caicedo
Jan 3 '11 at 17:50
@Asaf: I agree. And there are some very interesting questions still left. Schindler and Busche have recently looked at the consistency strength of Gitik's result, and Ioanna M. Dimitriou, a student of Peter Koepke, has also been studying this model.
– Andrés E. Caicedo
Jan 3 '11 at 17:53
@Asaf: I agree. And there are some very interesting questions still left. Schindler and Busche have recently looked at the consistency strength of Gitik's result, and Ioanna M. Dimitriou, a student of Peter Koepke, has also been studying this model.
– Andrés E. Caicedo
Jan 3 '11 at 17:53
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f16246%2fthe-cardinality-of-a-countable-union-of-countable-sets-without-the-axiom-of-cho%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