3
$\begingroup$

In a model solution it is stated that the cardinality of a set which is the countable union of sets of cardinality $2^{\aleph_0}$ is $\aleph_0\times 2^{\aleph_0}$, and, using the Axiom of Choice, $\aleph_0\times 2^{\aleph_0} = 2^{\aleph_0}$.

But, isn't the Cantor/Shroeder-Bernstein Theorem enough? I mean, given this:

$2^{\aleph_0}\le \aleph_0\times 2^{\aleph_0}\le 2^{\aleph_0}\times 2^{\aleph_0} = 2^{\aleph_0+\aleph_0} = 2^{\aleph_0}$

EDIT: so, the set in question is the set of all real-valued sequences $s = (s_0,s_1,\dots)$ such that for all but finitely many $n$, $s_n = 0$. And so I see that we have to get a countable union of sets of size $|\Bbb{R}^n|=2^{\aleph_0}$ for each $n$. Is there an (hand-wavy should be fine) way to set up the bijection needed with AC?

$\endgroup$

2 Answers 2

5
$\begingroup$

Your solution is fine, even without the Axiom of Choice.

Choice is needed in order to move from $|A|\cdot|B|=|\bigcup_{a\in A}B_a|$, where $B_a$ is some set of cardinality $B$. Namely, infinite unions are not necessarily the same as a product, not as freely as we take them when we assume AC.

If, however, $B_a=\{a\}\times B$, for example, then that's fine, as the union is exactly $A\times B$, which is by definition the set whose cardinality is $|A|\cdot|B|$.


So $\aleph_0\cdot2^{\aleph_0}$ is the cardinality of $\Bbb{N\times R}$. As you identify correctly, that is a subset of $\Bbb{R\times R}$, which without choice, has the same cardinality as $\Bbb R$ itself. And finally, Cantor–Bernstein is also choice-free, so we are done.

It's not true, however, that a countable union of sets of size $2^{\aleph_0}$ each is also of size $2^{\aleph_0}$. For example, if $A$ is a set which is a countable union of countable sets $A_n$, but it cannot be linearly ordered (e.g., it is a union of finite sets), then taking $R_n=\Bbb R\times\{n\}\cup A_n$. Since each $A_n$ is countable (or finite), we get that $R_n$ has size $2^{\aleph_0}$.

But $\bigcup R_n=\Bbb{R\times N}\cup A$, so it cannot be linearly ordered and thus has cardinality strictly bigger than $2^{\aleph_0}$.

However, if you can uniformly biject $R_n$ with $\Bbb R$, then you can turn this into a bijection into $\Bbb{R\times N}$, and the cardinality is again $2^{\aleph_0}$. This is indeed the case where $R_n$ is something like $\Bbb R^n$.

Perhaps easier, note that $|\Bbb{R^N}|=(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$. So any set that can be mapped into $\Bbb{R^N}$ has cardinality of at most $2^{\aleph_0}$. And indeed, any $\Bbb R^n$ can, as well as the eventually $0$ sequences.

$\endgroup$
1
  • $\begingroup$ Thanks Asaf, your proof with the injection into $\Bbb{R}^{\Bbb{N}}$ is much neater! $\endgroup$
    – davideleo
    May 15, 2019 at 19:15
4
$\begingroup$

You're right, the axiom of choice is not needed to show that $\aleph_0\cdot 2^{\aleph_0}=2^{\aleph_0}$. Note though that the axiom of choice may still be needed in the solution you refer to, specifically to say that since your set is a countable union of sets of cardinality $2^{\aleph_0}$, its cardinality is (at most) $\aleph_0\cdot 2^{\aleph_0}$. In general this requires choice, since you need to simultaneously pick bijections which witness that each of the countably many sets has cardinality $2^{\aleph_0}$. (In many cases, though, there is an easy way to construct such a family of bijections without the axiom of choice.)

$\endgroup$
2
  • $\begingroup$ Ooh, thanks, I was not focussing on the difficult bit of the question, then! I'll edit the question $\endgroup$
    – davideleo
    May 14, 2019 at 21:37
  • $\begingroup$ Actually, no choice is needed for anything here. But the product is not defined as an infinite sum. $\endgroup$
    – Asaf Karagila
    May 14, 2019 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.