# Continuum set into aleph zero many subsets

How to prove that if a set with cardinality of continuum is divided into aleph zero many subsets, then at least one of them has cardinality of continuum? (Of course without assuming the Continuum hypothesis)

Edit: Not precise formulation.

• A countable union of countable sets is... Feb 1, 2017 at 23:01
• If all of them are countable so their sum is countable. But that indicates that the cardinality is not aleph zero. But I cannot infer from here that one of them is continuum. I infer that all of them are not countable. Feb 1, 2017 at 23:07
• So I guess it doesn't imply that one of them is uncountable. Feb 1, 2017 at 23:08
• At this point the question is precise, and quite interesting - surprisingly, the answer is yes, but not easily so! See my answer. Feb 1, 2017 at 23:16

EDIT: Now that you have clarified your question, I can answer it. The answer to this, perhaps surprisingly, is yes, regardless of whether CH holds! This follows from Koenig's Theorem, which implies that $cf(2^{\aleph_0})>\omega$: if $\mathbb{R}=\bigcup_{i\in\mathbb{N}}A_i$, let $\alpha_i=\vert A_1\cup A_2\cup . . . \cup A_i\vert$; then $\sup\alpha_i=2^{\aleph_0}$, but if each $A_i$ has size $<2^{\aleph_0}$, each $\alpha_i$ is $<2^{\aleph_0}$ (exercise), so the sequence of $\alpha_i$s is a length-$\omega$ sequence cofinal in $2^{\aleph_0}$ - a contradiction.

Note that choice is necessary here: in fact, without choice it is consistent that $\mathbb{R}$ is the union of two sets of strictly smaller cardinality!

EDIT 2: Here's a direct proof, without invoking Koeneig's theorem (although the argument below basically is the proof of Koenig's theorem):

Remember that the set $\mathbb{R}^\mathbb{N}$ of functions from $\mathbb{N}$ to $\mathbb{R}$ also has size continuum; we'll show that if we partition this set into countably many pieces, one must have size continuum.

Suppose otherwise. Let $A_i\subset \mathbb{R}^\mathbb{N}$ have size $<2^{\aleph_0}$, for $i\in\mathbb{N}$. Then for each $i$, there is some real $r_i$ such that whenever $s\in A_i$, we have $s(i)\not=r_i$. (Why not?) But now consider the function $$f(i)=r_i.$$ This $f$ is an element of $\mathbb{R}^\mathbb{N}$, but not in any $A_i$.

• Thanks for the your answer. But Is there any simpler solution? This was an exam question on one of the previous years, but we haven't covered the Koenig's Theorem. Feb 1, 2017 at 23:26
• @guser I've put up a solution not involving KT, but it really is just the proof of KT. Feb 2, 2017 at 0:16
• The result about splitting the reals into two parts is actually due to Monro, ams.org/mathscinet-getitem?mr=325394, and also if we talk about a failure of Koenig's theorem, then the Feferman-Levy model is probably the OG result from 1964 (no citation, as it was announced in Notices of the AMS). Feb 2, 2017 at 5:04
• (By the way, VanLierre's thesis does not cite Monro's work. I think that he just wasn't aware of it.) Feb 2, 2017 at 6:23

Here is a fairly direct argument (this is really the same as Noah's answer; I'm just implementing the proof of König's theorem in this particular case). Suppose $X=\bigcup_{n\in\mathbb{N}} X_n$ has cardinality $\mathfrak{c}$ but each $X_n$ has cardinality less than $\mathfrak{c}$. Since $\mathfrak{c}^{\aleph_0}=\mathfrak{c}$, there exists a bijection $f:X\to X^\mathbb{N}$. For each $n$, let $s_n\in X$ be some element which is not the $n$th coordinate of $f(x)$ for any $x\in X_n$ (such an $s_n$ exists since $|X_n|<|X|$). Now consider the sequence $s=(s_n)\in X^{\mathbb{N}}$. Since $f$ is surjective, $s=f(x)$ for some $x\in X$, and $x\in X_n$ for some $n$. But by construction, the $n$th coordinate of $s$ is then different from the $n$th coordinate of $f(x)$. This is a contradiction.