# $\aleph_0\times 2^{\aleph_0} = 2^{\aleph_0}$ requires the Axiom of Choice?

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?

## 2 Answers

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.

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

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.)

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