3
$\begingroup$

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?

$\endgroup$
9
  • 4
    $\begingroup$ You cannot suppose $\bigcup_iA_i=[0,\,1]$, as this set having cardinality $\aleph_1$ is equivalent to $\mathsf{CH}$. $\endgroup$
    – J.G.
    Commented Oct 4, 2022 at 15:54
  • $\begingroup$ 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. $\endgroup$ Commented Oct 4, 2022 at 16:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – shoteyes
    Commented Oct 4, 2022 at 16:10
  • $\begingroup$ Which axioms can you assume for this exercise? In particular, do they include choice? $\endgroup$
    – J.G.
    Commented Oct 4, 2022 at 16:48
  • $\begingroup$ The countable union of countable sets is countable, assuming some amount of Choice. $\endgroup$
    – BrianO
    Commented Oct 4, 2022 at 23:36

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .