# A question about sets and $2^{\aleph_0}$.

Let $$A_i(i=1,2\dots)$$ be a sequence of sets satisfying $$|\cup_{i=1}^{\infty}A_i|=2^{\aleph_0}$$, then $$\exists n_0\in\mathbb{N}$$, s.t. $$|A_{n_0}|=2^{\aleph_0}$$.

Clearly $$|A_i|\le2^{\aleph_0},\forall i$$, so it suffices to show that $$\exists n_0\in\mathbb{N}$$, s.t. $$|A_{n_0}|\ge2^{\aleph_0}$$. If $$\forall n\in \mathbb{N}$$, $$|A_{n_0}|<2^{\aleph_0}$$, I can't say that $$|A_{n_0}|\le\aleph_0$$. So how to solve this problem?

Any ideas?

• You cannot suppose $\bigcup_iA_i=[0,\,1]$, as this set having cardinality $\aleph_1$ is equivalent to $\mathsf{CH}$.
– J.G.
Commented Oct 4, 2022 at 15:54
• You seem to be using notation incorrectly. When you write $\aleph_1$, do you mean $\aleph_1$ or $2^{\aleph_0}$? Because some of the things you write don't make sense with the usual meaning of the symbols. Commented Oct 4, 2022 at 16:05
• @save123 The real interval $[0, 1]$ has cardinality $2^{\aleph_0}$. Saying that $2^{\aleph_0} = \aleph_1$ is what is known as the Continuum Hypothesis, or $\mathsf{CH}$, which is not necessary nor allowed (I would think) for this proof. Commented Oct 4, 2022 at 16:10
• Which axioms can you assume for this exercise? In particular, do they include choice?
– J.G.
Commented Oct 4, 2022 at 16:48
• The countable union of countable sets is countable, assuming some amount of Choice. Commented Oct 4, 2022 at 23:36

## 2 Answers

Surprisingly, I can't find this exact question asked at MSE before. So, well-prepared to delete in case this is a duplicate after all, here goes:

This is a beautiful argument! Rather than work on $$\mathbb{R}$$, it will be convenient instead to work on the set of infinite binary sequences, which (to avoid confusion) I'll call "$$\mathscr{B}$$" here.

The key fact about $$\mathscr{B}$$ is that we can "code" a sequence of infinitely many binary sequences as a single binary sequence: given a sequence $$\beta=(b_i)_{i\in\mathbb{N}}$$ of elements of $$\mathscr{B}$$ (so $$\beta$$ is an infinite sequence of infinite binary sequences), let $$[\beta]$$ be the infinite binary sequence whose $$\langle x,y\rangle$$th term is $$b_x(y)$$. Here "$$\langle \cdot,\cdot\rangle$$" is the Cantor pairing function - or any other pairing function you like (just some bijection $$\mathbb{N}^2\rightarrow\mathbb{N}$$).

We can also go the other direction: given a binary sequence $$b\in\mathscr{B}$$ and a natural number $$j$$, let $$b_{[j]}$$ be the binary sequence whose $$i$$th term is $$b(\langle i, j\rangle)$$.

What this lets you do is "perform infinitely many diagonal arguments simultaneously." Specifically, suppose $$A_i$$ is a sub-continuum-sized subset of $$\mathscr{B}$$ for each $$i\in\mathbb{N}$$. For each $$i$$ we can find a $$b_i$$ such that no $$a\in A_i$$ has $$a_{[i]}=b_i$$. Now let $$\beta(i)=b_i$$, and consider $$[\beta]$$. Assuming I haven't botched my indexing (exercise: fix my almost-certain mistake!), we get that $$[\beta]\not\in \bigcup_{i\in\mathbb{N}}A_i$$.

Amazingly, this is essentially all we can prove about the size of the continuum in $$\mathsf{ZFC}$$. For example, each of the following is consistent with $$\mathsf{ZFC}$$ (assuming the latter is consistent itself in the first place, of course):

• $$2^{\aleph_0}=\aleph_1$$. (This is the continuum hypothesis, CH.)

• $$2^{\aleph_0}=2^{\aleph_1}=2^{\aleph_2}=\aleph_{17}$$. (So the continuum function doesn't need to be injective!)

• $$2^{\aleph_0}=\aleph_{\omega+1}$$. (So we can "hop over" the forbidden value $$\aleph_\omega$$ - which is forbidden, by the above argument, since $$\aleph_\omega=\sum_{i\in\omega}\aleph_i$$.)

• $$2^{\aleph_0}=\aleph_{\omega_1}$$. (This case is especially interesting, since it means that $$\mathbb{R}$$ is a union of fewer-than-continuum smaller-than-continuum sets.)

We just can't have $$2^{\aleph_0}=\aleph_\omega$$, or $$\aleph_{\omega^2+\omega\cdot 42}$$, or $$\aleph_\alpha$$ for any $$\alpha$$ with countable cofinality. And this is all thoroughly generalized by Konig's theorem.

Let $$E=\bigcup_{n\in\mathbb N}E_n$$ where $$E_1,E_2,E_3,\dots$$ are pairwise disjoint sets of cardinality $$\aleph_0$$. The power set $$\mathcal P(E)=\{X:X\subseteq E\}$$ has cardinality $$2^{\aleph_0}$$. Now suppose $$\mathcal P(E)=\bigcup_{n\in\mathbb N}A_n$$; I claim that at least one of the sets $$A_n$$ has cardinality $$2^{\aleph_0}$$.

It will suffice to show that, for some $$n$$, the map $$X\mapsto X\cap E_n$$ is a surjection from $$A_n$$ to $$\mathcal P(E_n)$$; it will follow (by the axiom of choice) that $$|A_n|\ge|\mathcal P(E_n)|=2^{\aleph_0}$$, and of course we know that $$|A_n|\le|\mathcal P(E)|=2^{\aleph_0}$$.

Assume for a contradiction that none of those maps is surjective, i.e., for each $$n\in\mathbb N$$ we can choose a set $$X_n\subseteq E_n$$ such that $$X\cap E_n\ne X_n$$ for all $$X\in A_n$$. Let $$X=\bigcup_{n\in\mathbb N}X_n\subseteq E$$. Then $$X\in A_n$$ for some $$n$$, and $$X\cap E_n=X_n$$, a contradiction.